Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

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?

share|improve this question

closed as primarily opinion-based by Ilmari Karonen, DrLecter, tylo, K.G., cpast Mar 3 '15 at 5:51

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise.If this question can be reworded to fit the rules in the help center, please edit the question.

I mean, that there is a maximum number of primes – anon Mar 1 '15 at 22:08
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?" – Ilmari Karonen Mar 1 '15 at 22:29
'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. – tylo Mar 2 '15 at 15:32

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.)

share|improve this answer

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").

share|improve this answer