# A curious statement in an old blog

In http://blog.computationalcomplexity.org/2009/08/finding-primes.html, a statement is added which reads "Oddly enough we would usually prefer a probabilistic over the deterministic method to find primes. Otherwise the adversary can use the same deterministic procedure and factor your number as easily as you put it together". As I understand, this seems to state polynomial time deterministic prime finding implies integer factorization can be done in polynomial time. Am I right? How to see this?

Is there analogous statement to factorization in $\Bbb Z[x]$? Is there an analogous statement to discrete logarithms?

• Not at all. What it means is that when we are looking for primes to serve as e.g. a private RSA key, the entropy of the key comes from randomness of the prime search procedure, hence we need the latter to be randomized. Aug 21 '15 at 17:16