I vaguely know that prime numbers are very important in cryptography, but I assume for most encryption methods, they tend to stay rather 'small'. Are we really using massive prime numbers for encryption? Why would modern encryption start to fail if the set of prime numbers was finite?

  • $\begingroup$ I mean, that there is a maximum number of primes $\endgroup$
    – anon
    Commented Mar 1, 2015 at 22:08
  • 7
    $\begingroup$ Given that it's quite easy to prove that the number of primes isn't finite, this is sort of like asking "why would cryptography fall apart if 1 + 1 wasn't 2?" $\endgroup$ Commented Mar 1, 2015 at 22:29
  • 1
    $\begingroup$ 'Small' is an quite interesting and completely inadequate assumption. We use primes of certain length, where you could not iterate through them, if you put 1 prime into each atom of the universe, and store it for the shortest measurable amount of time, and keep doing that until the end of the universe. $\endgroup$
    – tylo
    Commented Mar 2, 2015 at 15:32

2 Answers 2


This question is really broad. I'll try to answer in a few sentences.

Of course, $\mathbb Z$ in its widely accepted definition has infinitely many primes. This means: the properties people usually expect from something we may rightly call "the integers" already imply that this thing contains infinitely many primes. Hence it is impossible to keep everything as is except there is only a finite number of primes — this is contradictory!

Therefore, if something contains only finitely many primes, it must lack some of the properties that $\mathbb Z$ has — and since, for instance, Euclid's proof uses only very basic and intuitive properties of divisibility, this means that almost everything we know about $\mathbb Z$ does not hold in this something.

But large areas of cryptography are based on certain properties of $\mathbb Z$ and especially phenomena related to primality! This means that most of cryptographic theory would break down if one tried to replace $\mathbb Z$ (containing infinitely many primes) by something "similar" (whatever this means) which has only a finite number of primes (and is therefore entirely different from $\mathbb Z$).

Trying to substitute something completely different for $\mathbb Z$ and expecting the same theorems to hold is just silly.

(However, structures which are somewhat like $\mathbb Z$ but finite are of course highly useful in cryptography — just not in $\mathbb Z$'s rôle.)


To answer your question about the size of primes: The current recommendation for RSA keys recommends using two 1024-bit keys. That means they're somewhat larger than $10^{300}$; Diffie-Hellman on the integers modulo $p$ is normally used with a single prime of at least 2048 bits (so, larger than $10^{600}$!) Even worse, these numbers tend to grow over time; as computers get faster, key sizes increase to compensate. If there were a largest prime, this wouldn't be generally possible.

More broadly: If the primes were finite, then the term "prime number" or the term "finite" or the term "natural number" has to mean something different than how we use it. The infinitude of primes is a very simple consequence of those definitions. So if they're finite, math can't look like we expect it to, and so we can't really say very much about what the consequences is without a lot more information (you can't have "everything is the same except primes are finite").