I have some questions about cryptography that likely have simple answers, but I haven't found a good online resource:
1. I understand that cryptography depends in part on the difficulty of factoring the product of two (very) large prime numbers, but how are those large prime numbers generated in a relatively quick way? In other words, is it easier to find primes than to factor their products? And, if so, why?
2. This is a related question, but why is it that the product of two large primes is so difficult to factor?
3. Finally, I seem to remember that prime numbers become much rarer as numbers get larger  so how is it that there are enough primes to make cryptography secure?
Math/Cryptography Questions
Moderators: gmalivuk, Moderators General, Prelates
Re: Math/Cryptography Questions
1. yes, it is much easier to test if a number is prime (polynomial), than it is to factor a prime (unknown if polynomial). even though factoring a prime is not known to be NPcomplete, this is kind of like many other NPcomplete problems, where something like finding the shortest traveling salesman path is much harder than verifying that the path is legitimate. to answer your question we just try out a lot of numbers and test if each one is prime.
(for actual cryptographic application, there are other properties that a prime needs to be satisfy before it can be safely used)
2. because they are big numbers. and there are a lot of possible answers  if the number is n bits long, you need to consider 2^(n/2) possible candidates, which is a lot. i guess besides that, you could ask why multiplication is so easy!
3. they get rarer, but pretty slowly. on average one out of every log n (natural log) numbers is prime, if you are searching from 1 to n. therefore, if you want your prime to be exactly 2048 bits long, there are around 2^2048 / log(2^2048) primes of that size, which is something like 10^613  a lot. primes are kind of rare, but not that rare, and there are a lot of numbers, so it doesn't matter
(for actual cryptographic application, there are other properties that a prime needs to be satisfy before it can be safely used)
2. because they are big numbers. and there are a lot of possible answers  if the number is n bits long, you need to consider 2^(n/2) possible candidates, which is a lot. i guess besides that, you could ask why multiplication is so easy!
3. they get rarer, but pretty slowly. on average one out of every log n (natural log) numbers is prime, if you are searching from 1 to n. therefore, if you want your prime to be exactly 2048 bits long, there are around 2^2048 / log(2^2048) primes of that size, which is something like 10^613  a lot. primes are kind of rare, but not that rare, and there are a lot of numbers, so it doesn't matter
Last edited by >) on Mon May 01, 2017 2:09 am UTC, edited 1 time in total.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Math/Cryptography Questions
>) wrote:1. yes, it is much easier to test if a number is prime (polynomial), than it is to factor a prime (unknown if polynomial). even though factoring a prime is not known to be NPcomplete, this is kind of like many other NPcomplete problems, where something like finding the shortest traveling salesman path is much harder than verifying that the path is legitimate. to answer your question we just try out a lot of numbers and test if each one is prime.
(for actual cryptographic application, there are other properties that a prime needs to be satisfy before it can be used securely)
I don't understand what the reference to polynomial means. Does it mean processing time? If generating primes is easy, how do we know that various programs aren't using some flawed method to generate the same set of primes (pretend that the set is a million common primes) such that the encryption scheme could be broken without much trouble?
Re: Math/Cryptography Questions
polynomial means the running time grows polynomially in the size of the prime you want to generate. for example, if the polynomial were n^2, you could guarantee testing if a 4096 bit number is prime would take not more than 4^2 = 16 times as long as testing a 1024 bit number
factoring is not known to be polynomial time for any polynomial, so there is no such k for which you can say factoring a 4096 bit number takes at most 4^k times as long as factoring a 1024 bit number. (well there maybe some such algorithm, we just don't know it yet)
since we generate by picking random numbers and testing if each one is a prime, i don't think the scenario described by you could happen unless we are using the same flawed random number generators which only generate the same set of numbers.
of course, the NSA has been known to backdoor random number generators for pretty much that reason ...
factoring is not known to be polynomial time for any polynomial, so there is no such k for which you can say factoring a 4096 bit number takes at most 4^k times as long as factoring a 1024 bit number. (well there maybe some such algorithm, we just don't know it yet)
since we generate by picking random numbers and testing if each one is a prime, i don't think the scenario described by you could happen unless we are using the same flawed random number generators which only generate the same set of numbers.
of course, the NSA has been known to backdoor random number generators for pretty much that reason ...

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Math/Cryptography Questions
>) wrote:polynomial means the running time grows polynomially in the size of the prime you want to generate. for example, if the polynomial were n^2, generating a 4096 bit prime would take 4^2 = 16 times as long as generating a 1024 bit prime.
factoring is not known to be polynomial time for any polynomial, so there is no such k for which you can say factoring a 4096 bit number takes at most 4^k times as long as factoring a 1024 bit number. (well there maybe some such algorithm, we just don't know it yet)
since we generate by picking random numbers and testing if each one is a prime, i don't think the scenario described by you could happen unless we are using the same flawed random number generators which only generate the same set of numbers.
of course, the NSA has been known to backdoor random number generators for pretty much that reason ...
But how can it be that generating large primes is that much easier than factoring them? Don't you have to factor them at least in part in order to know whether they're prime in the first instance?
Re: Math/Cryptography Questions
no, it is possible to quickly prove that a number is prime without trying to factor it!
the first (and possible only known) deterministic algorithm for doing so is the AKS primality test
https://en.wikipedia.org/wiki/AKS_primality_test
for some intuition, suppose i randomly generate a function f which maps the integers from 1 to 2^1000 to integers from 1 to 2^1000, and don't allow myself access to the actual machine running the function. let set S be the domain of f
it is very easy to find a number in S: i just plug some arbitrary number into f and see what the output is
it is much more difficult to test if a number n is in S! i would need to randomly guess at what input caused n to be output
in particular, note that i don't have to try test if a number is in S to find a number in S, since i have access to the function f.
here's another example, in the same vein. suppose there are 1000 doors and there are 100 distinct animals, with each door having 0 or 1 animals behind it
then if i ask you to name one of the 100 animals, it is not that hard  you just open a few doors until you see an animal, and tell me the name
if i ask you to find which door has the pig behind it, then you will probably have to open several hundred doors before you find it
the first (and possible only known) deterministic algorithm for doing so is the AKS primality test
https://en.wikipedia.org/wiki/AKS_primality_test
for some intuition, suppose i randomly generate a function f which maps the integers from 1 to 2^1000 to integers from 1 to 2^1000, and don't allow myself access to the actual machine running the function. let set S be the domain of f
it is very easy to find a number in S: i just plug some arbitrary number into f and see what the output is
it is much more difficult to test if a number n is in S! i would need to randomly guess at what input caused n to be output
in particular, note that i don't have to try test if a number is in S to find a number in S, since i have access to the function f.
here's another example, in the same vein. suppose there are 1000 doors and there are 100 distinct animals, with each door having 0 or 1 animals behind it
then if i ask you to name one of the 100 animals, it is not that hard  you just open a few doors until you see an animal, and tell me the name
if i ask you to find which door has the pig behind it, then you will probably have to open several hundred doors before you find it

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Math/Cryptography Questions
>) wrote:no, it is possible to quickly prove that a number is prime without trying to factor it!
the first (and possible only known) deterministic algorithm for doing so is the AKS primality test
https://en.wikipedia.org/wiki/AKS_primality_test
for some intuition, suppose i randomly generate a function f which maps the integers from 1 to 2^1000 to integers from 1 to 2^1000, and don't allow myself access to the actual machine running the function. let set S be the domain of f
it is very easy to find a number in S: i just plug some arbitrary number into f and see what the output is
it is much more difficult to test if a number n is in S! i would need to randomly guess at what input caused n to be output
in particular, note that i don't have to try test if a number is in S to find a number in S, since i have access to the function f.
here's another example, in the same vein. suppose there are 1000 doors and there are 100 distinct animals, with each door having 0 or 1 animals behind it
then if i ask you to name one of the 100 animals, it is not that hard  you just open a few doors until you see an animal, and tell me the name
if i ask you to find which door has the pig behind it, then you will probably have to open several hundred doors before you find it
So the bottom line is as follows: (1) it's fairly easy to generate large primes through some method that's been proved to generate only prime numbers; (2) it's similarly easy to multiple those large primes; (3) one thing that's really difficult in mathematics is to factor the product of two prime numbers (unless one of the primes is two); and (4) we're reasonably certain that the method that we're using to generate large primes is doing so randomly such that the primes can't be guessed.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26412
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Math/Cryptography Questions
We don't have methods that generate only primes, but we can (relatively quickly) check if a number is prime, and we have methods that generate mostly primes.
Also, it's easy to factor out any small primes, not just 2. The difficulty is when the primes in question have hundreds of digits.
Also, it's easy to factor out any small primes, not just 2. The difficulty is when the primes in question have hundreds of digits.
Re: Math/Cryptography Questions
MathDoofus wrote:(1) it's fairly easy to generate large primes through some method that's been proved to generate only prime numbers;
Kind of: we just generate random* numbers until finding one that is prime.
(a simple method would be to start at 2^1024 and increment the number by one every time it turns out to be composite; though with that exact method you'd always end up with 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137859)
MathDoofus wrote:(4) we're reasonably certain that the method that we're using to generate large primes is doing so randomly such that the primes can't be guessed.
Speaking of *, it's easy to pick truly random numbers –you just need some truly random noise like atmospheric noise as initial values for a (cryptographically secure) random number generator. But like >) said in the first reply, the primes that are used for cryptography
Who is online
Users browsing this forum: No registered users and 13 guests