On page 89 Remark 3.5 in the Handbook of Applied Cryptography the following is written:
A non-trivial factorization of $n$ is a factorization of the form $n = ab$ where $1 < a < n$ and $1 < b < n$; $a$ and $b$ are said to be non-trivial factors of $n$. Here a and b are not necessarily prime. To solve the integer factorization problem, it suffices to study algorithms that split $n$, that is, find a non-trivial factorization $n = ab$. Once found, the factors $a$ and $b$ can be tested for primality. The algorithm for splitting integers can then be recursively applied to $a$ and/or $b$, if either is found to be composite. In this manner, the prime factorization of $n$ can be obtained.
I think that this argumentation is flawed. At the time the book was written there were no efficient primality tests available (or at least none are given in the book, but to my knowledge the first of these test was the AKS algorithm back in 2002), so the statement
Once found, the factors $a$ and $b$ can be tested for primality.
does not make sense to me, as a primality test can not be done efficiently in the context of this book. Am I getting something wrong?
EDIT:
I am aware that probabilistic primality test like Solovay-Strassen or Miller-Rabin were already around at the time, they are also covered in the book. But I do not see why the existence of Miller-Rabin should be an argument that a primality test can be done efficiently, since said tests have an error bound when returning "n is prime". And by the definition of polynomial reduction (again taken from the book on page 88:
Definition Let $A$ and $B$ be two computational problems. $A$ is said to polytime reduce to $B$, written $A \le_P B$, if there is an algorithm that solves $A$ which uses, as a subroutine, a hypothetical algorithm for solving $B$, and which runs in polynomial time if the algorithm for $B$ does.
If I understand this definition correctly we can not use Miller Rabin as a primality test in the argument $\text{factoring} \le_p \text{splitting}$ above, since then we can not be certain that the factors we found are indeed primes. (If I am not mistaken an algorithm is said to solve a problem if it can give 100% accurate answers.)
I hope it is clear what I mean, if not please let me know and I will reformulate my question.
