On splitting vs factoring 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 &lt; a &lt; n$ and $1 &lt; b &lt; 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.
Miller-Rabin has been known since at least 1980 (according to Wikipedia). Even though it's probabilistic, it's good enough. For example, openssl uses it$^\textrm{1}$. Chapter 4 of the handbook talks about various primality tests, which may gave you a better understanding of the authors' thoughts.



$^\textrm{1}$See the source code for bn_prime.c