In general every public key cryptosystem ``has'' a probabilistic polynomial time algorithm $G$ such that $G(1^k)=(\textrm{public key}, \textrm{private key=trapdoor})$; $G$ is called the key generator. Now for the RSA cryptosystem the keys, can be found in the following way:

Bob decides the key length $k$, then $G(1^k)=((n,e), d)$ where $n=pq$ with $p$ and $q$ prime numbers, $n$ has length $k$ (as bit string), and $e\in\mathbb Z^\ast_{\phi(n)}$. The two primes $p$ and $q$ and are chosen in a random way, $\phi(n)$ is simply $(p-1)(q-1)$, $e\in\mathbb Z^\ast_{\phi(n)}$ is randomly chosen and finally $d$ is calculated in polynomial time with the extended Euclid algorithm. The couple $(n,e)$ is setted as the public key, whereas $d$ is the secret key.

I don't understand why this algorithm has probabilistic polynomial running time. Who ensures that I can find two random primes and $e$ in a reasonable time?

thanks in advance.

  • $\begingroup$ Basically, there are a lot of primes available to choose from. $\endgroup$ Commented May 2, 2014 at 20:12
  • $\begingroup$ Yes this is the intuition, but is there a formal proof aof this? $\endgroup$
    – Dubious
    Commented May 2, 2014 at 20:23
  • $\begingroup$ jstor.org/stable/2371291 $\;$ $\endgroup$
    – user991
    Commented May 2, 2014 at 21:12

1 Answer 1


Short version: All the cool kids are using Randomized Algorithm !

Boring version:

  1. Any deterministic (part of a) crypto system can be broken ! [Goldwasser Micali]

  2. Primes density is pretty high (higher than one intuitively expects) as we talk of big numbers. Prime No. Theorem : #of primes between $1$ and $x$, $\pi(x) = \frac{x}{ln(x)}$ , So if randomly picking no.s usually means you have a fairly high chance of getting a prime.. :)

  3. Primality checking with Rabin Miller (probabilistic) is way faster than AKS (deterministic)

  • 2
    $\begingroup$ "=" $\mapsto$ "$\approx$" $\;$ $\endgroup$
    – user991
    Commented May 3, 2014 at 5:15
  • $\begingroup$ yes, i could not find the latex code for that :P $\endgroup$
    – Subhayan
    Commented May 3, 2014 at 8:35

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.