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?

  • 6
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Aug 21 '15 at 17:16

I'm not sure this is a statement about primes so much as it is a statement about secret key generation: if the method is deterministic (e.g. take the smallest prime larger than 10^20), then your adversary can simply reproduce the computation to find your secret key.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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