I still remember Kaisa telling in primary school, that Euclid's proof of infinite number of prime numbers is often considered as the most beautiful proof in mathematics.
I like many of quanta's articles on mathematicians and scientists, and I appreciate their contributions to science journalism. I would like to add one aspect that I think this article downplays, but which is understandable to a large audience.
Kaisa and Maksym study multiplicative functions, i.e. functions which satisfy f(ab) = f(a)f(b) if a and b are relatively prime. A big part in Kaisa and Maksym's fundamental technique boils down to understanding completely the behavior of f on small primes, and giving somewhat loose bounds on the rest. Central to their success is their ability to make quantitative the intuitive statement that "most numbers have lots of small primes as factors". This required a few new ideas, but the nugget is quite simple, I think.
As a layman, I wonder about the connection between primes and random numbers. Obviously, the primes are not actually random, but they seem to exhibit a lot similarity to random numbers in that they are chaotic over short intervals, but seem smoother and better behaved over long intervals.
I would say that this is one of the things that have inspired many mathematicians to study and try to understand the primes. Many results in classical analytic number theory measure things which deviate away from the assumption of randomness. And mathematicians are often very interested in recognizing new times when things are not as random as they appear (such as [1] recently, where it turns out that there are biases between congruence classes of consecutive primes, even though in the limit things are "random").
Can anyone explain to me why primes are so important in cryptography?
I understand that they are used for factorization, where it is easy to multiply two primes and get a number, but it is difficult from a big number to find what two primes were used to get it. So, the question is why not to have a big database of primes, and when we have that big factorized number we try to divide that number by each prime from the database and see if the result is another prime from the database? Wouldn't that work?
They are not that important in cryptography. They are important for particular types of cryptography.
Cryptography often involves finding algebraic structures that have certain properties, that can be used to implement a particular security property. For example, only someone who knows a particular value, can perform operations on these other values.
Many algebraic structures include prime numbers as special members. Other algebraic structures do not. Yet other algebraic structures don't even have "number" as members, but something else.
An algebraic structure is roughly, a collection of abstract objects (numbers, vectors over numbers, etc) and operations (add, multiply, etc) that follow a particular set of associated laws. You can make up your own, but throughout the centuries, mathematicians, scientists and engineers, have discovered that certain structures are very useful for various tasks. e.g. groups, rings, fields, etc etc.
So, why primes show up so often in cryptography is not due to them specifically being "primes", but due to them having special properties within many common algebraic structures. Other things show up in many parts of mathematics as well, like pi, e, i, etc etc etc. There is nothing particularly special about primes in cryptography in general. For example AES does not directly use prime numbers (apart from the number 2).
These numbers are simply huge, so there are far to many primes to check.
But the idea is you find a large random number and see if it's prime, and repeat until you find 2 primes. There are shortcuts but let's assume you simply try to factor them. 2,3,5... up to the square root of the number this is W(Work) checks. Now not every random number is prime so let's assume you do this 1,000times. You did 1000 W work to get two prime numbers. But when you multiply them someone needs to check not W numbers but W * W numbers. Now let's say W = 1,000,000,000. You did 1000 W or 1,000,000,000,000 but to break it would take a million times the effort. Further, anything that makes it take less effort to factor a number, means you can just factor larger numbers to start with.
That's the basic idea. However, you just care if something is prime which takes even less effort so it's not 10^6 W, but 10^50 or more W.
It is standard to take two primes that each have at least 100 digits or so. There are approximately 10^100 / 230 primes of of this size (this is the Prime Number Theorem). There is simply not enough space or time to store or interpret 10^100 numbers.
And like the other people responded, there are just wayyyy to many primes to make that feasible. Though it is a common Challenge in security competitions to find the factors to a public key through factordb. Or having two bad keys sharing one same prime - then you can use Euclidean algorithm (greates common divisor).
which is nominally about a particular vulnerability (common factor attacks), but actually if you're interested in this topic, I suggest that you read this piece and try to solve the puzzle, because you will really get a sense of the size of the numbers involved, and what particular kinds of arithmetic operations you have to do when using RSA. I even have a section about estimating the number of prime numbers of a particular size (e.g. 512-bit primes, which are the secrets associated with 1024-bit RSA public keys). As other people have said, the size of the numbers involved will make it impractical to list all of them or crack keys by brute force. My puzzle and the associated discussion might make that a little more concrete for you!
(Although tptacek might also want you to know that RSA is obsolescent, and more modern cryptography does not actually use prime factorization, but rather other kinds of arithmetic problems.)
I think because once you get into the range of 20-digit prime numbers, there become quite a lot, such that it's infeasible to test all permutations to find the prime factors.
(Professional mathematician and analytic number theorist here.)
This is not correct. When mathematicians (at least analytic number theorists) use the notation "log", it always means to base e, i.e., ln.
Natural logarithms come up all the time in math, and in analytic number theory in particular; base 10 is an artifact of how many fingers we evolved with.
[+] [-] tarre|8 years ago|reply
[+] [-] osivertsson|8 years ago|reply
[+] [-] soberhoff|8 years ago|reply
[+] [-] zem|8 years ago|reply
[+] [-] mixedmath|8 years ago|reply
Kaisa and Maksym study multiplicative functions, i.e. functions which satisfy f(ab) = f(a)f(b) if a and b are relatively prime. A big part in Kaisa and Maksym's fundamental technique boils down to understanding completely the behavior of f on small primes, and giving somewhat loose bounds on the rest. Central to their success is their ability to make quantitative the intuitive statement that "most numbers have lots of small primes as factors". This required a few new ideas, but the nugget is quite simple, I think.
[+] [-] brianberns|8 years ago|reply
[+] [-] mixedmath|8 years ago|reply
[1]: https://terrytao.wordpress.com/2016/03/14/biases-between-con...
[+] [-] osivertsson|8 years ago|reply
[1] https://en.m.wikipedia.org/wiki/Prime_Obsession
[+] [-] unknown|8 years ago|reply
[deleted]
[+] [-] unknown|8 years ago|reply
[deleted]
[+] [-] unknown|8 years ago|reply
[deleted]
[+] [-] ThrustVectoring|8 years ago|reply
[+] [-] mudil|8 years ago|reply
I understand that they are used for factorization, where it is easy to multiply two primes and get a number, but it is difficult from a big number to find what two primes were used to get it. So, the question is why not to have a big database of primes, and when we have that big factorized number we try to divide that number by each prime from the database and see if the result is another prime from the database? Wouldn't that work?
[+] [-] infinity0|8 years ago|reply
Cryptography often involves finding algebraic structures that have certain properties, that can be used to implement a particular security property. For example, only someone who knows a particular value, can perform operations on these other values.
Many algebraic structures include prime numbers as special members. Other algebraic structures do not. Yet other algebraic structures don't even have "number" as members, but something else.
An algebraic structure is roughly, a collection of abstract objects (numbers, vectors over numbers, etc) and operations (add, multiply, etc) that follow a particular set of associated laws. You can make up your own, but throughout the centuries, mathematicians, scientists and engineers, have discovered that certain structures are very useful for various tasks. e.g. groups, rings, fields, etc etc.
So, why primes show up so often in cryptography is not due to them specifically being "primes", but due to them having special properties within many common algebraic structures. Other things show up in many parts of mathematics as well, like pi, e, i, etc etc etc. There is nothing particularly special about primes in cryptography in general. For example AES does not directly use prime numbers (apart from the number 2).
[+] [-] Retric|8 years ago|reply
But the idea is you find a large random number and see if it's prime, and repeat until you find 2 primes. There are shortcuts but let's assume you simply try to factor them. 2,3,5... up to the square root of the number this is W(Work) checks. Now not every random number is prime so let's assume you do this 1,000times. You did 1000 W work to get two prime numbers. But when you multiply them someone needs to check not W numbers but W * W numbers. Now let's say W = 1,000,000,000. You did 1000 W or 1,000,000,000,000 but to break it would take a million times the effort. Further, anything that makes it take less effort to factor a number, means you can just factor larger numbers to start with.
That's the basic idea. However, you just care if something is prime which takes even less effort so it's not 10^6 W, but 10^50 or more W.
[+] [-] mixedmath|8 years ago|reply
[+] [-] LiveOverflow|8 years ago|reply
And like the other people responded, there are just wayyyy to many primes to make that feasible. Though it is a common Challenge in security competitions to find the factors to a public key through factordb. Or having two bad keys sharing one same prime - then you can use Euclidean algorithm (greates common divisor).
[+] [-] schoen|8 years ago|reply
http://www.loyalty.org/~schoen/rsa/
which is nominally about a particular vulnerability (common factor attacks), but actually if you're interested in this topic, I suggest that you read this piece and try to solve the puzzle, because you will really get a sense of the size of the numbers involved, and what particular kinds of arithmetic operations you have to do when using RSA. I even have a section about estimating the number of prime numbers of a particular size (e.g. 512-bit primes, which are the secrets associated with 1024-bit RSA public keys). As other people have said, the size of the numbers involved will make it impractical to list all of them or crack keys by brute force. My puzzle and the associated discussion might make that a little more concrete for you!
(Although tptacek might also want you to know that RSA is obsolescent, and more modern cryptography does not actually use prime factorization, but rather other kinds of arithmetic problems.)
[+] [-] yathern|8 years ago|reply
[+] [-] seycombi|8 years ago|reply
[+] [-] johansch|8 years ago|reply
[+] [-] unknown|8 years ago|reply
[deleted]
[+] [-] sevenfive|8 years ago|reply
[+] [-] impendia|8 years ago|reply
This is not correct. When mathematicians (at least analytic number theorists) use the notation "log", it always means to base e, i.e., ln.
Natural logarithms come up all the time in math, and in analytic number theory in particular; base 10 is an artifact of how many fingers we evolved with.