<p>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.</p>

CC BY-SA 3.0
2015-08-21T17:18:00.960Z
2015-08-21T17:18:00.960Z
cody
<p>In <a href="http://blog.computationalcomplexity.org/2009/08/finding-primes.html" rel="nofollow">http://blog.computationalcomplexity.org/2009/08/finding-primes.html</a>, 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?</p>

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

CC BY-SA 3.0
2015-08-21T17:16:59.320Z
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.
Emil Jeřábek
<complexity-classes><nt.number-theory><factoring><primes><probabilistic-computation>
A curious statement in an old blog
Turbo
# A curious statement in an old blog

(Asked by: username_0 on 2015-08-21)

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?

**Tags:** complexity-classes, nt.number-theory, factoring, primes, probabilistic-computation
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2015-08-21. Score: 9 | Accepted answer

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.


---

