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?


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.

  • 1
    $\begingroup$ See pages 135-142 for probabilistic and 142-145 for true primality tests. You can also download the index of the book. Indexes always are very helpful. $\endgroup$
    – kelalaka
    Commented Jun 14, 2020 at 19:00
  • 1
    $\begingroup$ AKS was the first known deterministic algorithm to test primality that ran in polynomial time; we knew a number of fast tests, but they are all probabilistic (either always running in polynomial time, but having a bounded probability of giving an incorrect result, or terminating quickly with high probability and always giving the correct result). In fact, in practice we hardly ever use AKS; there is almost always some probabilistic algorithm that is better suited $\endgroup$
    – poncho
    Commented Jun 14, 2020 at 19:11
  • 1
    $\begingroup$ You seem to be using a different definition of reduction than the book. The definition never states that either algorithm needs to be successful with probability $1$, nor that their success probabilities need to be equal. $\endgroup$
    – Maeher
    Commented Jun 15, 2020 at 8:30
  • 2
    $\begingroup$ If the book (as it should) uses Turing reductions, then there's no issue whatsoever. If they do use Karp reductions (which would be highly non-standard in the context and pretty pointless) then your objection might have merit, but that blurp from the definition does not sound like they're talking about Karp reductions. $\endgroup$
    – Maeher
    Commented Jun 15, 2020 at 8:33
  • 1
    $\begingroup$ You say that Miller-Rabin doesn't apply because the results are not guaranteed. ECPP (section 4.3.4) was also known, and always gives correct results. $\endgroup$
    – poncho
    Commented Jun 15, 2020 at 11:33

1 Answer 1


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

  • $\begingroup$ Thanks for your answer, I edited my question as I still have an objection to the stated proof. $\endgroup$
    – 3nondatur
    Commented Jun 14, 2020 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.