Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
Basically, there are a lot of primes available to choose from. – Paŭlo Ebermann May 2 '14 at 20:12
Yes this is the intuition, but is there a formal proof aof this? – Dubious May 2 '14 at 20:23 $\;$ – Ricky Demer May 2 '14 at 21:12

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)

share|improve this answer
"=" $\mapsto$ "$\approx$" $\;$ – Ricky Demer May 3 '14 at 5:15
yes, i could not find the latex code for that :P – Subhayan May 3 '14 at 8:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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