6 ms·

Dreaming of prime numbers in short intervals

77 points by heinrichf 9y ago

brianberns 9y ago
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.
- deleted 9y ago
  [deleted]
- deleted 9y ago
  [deleted]
- deleted 9y ago
  [deleted]
- mixedmath 9y ago
  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"). [1]: https://terrytao.wordpress.com/2016/03/14/biases-between-consecutive-primes/ https://terrytao.wordpress.com/2016/03/14/biases-between-con...
- osivertsson 9y ago
  Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics [1] is a nice read if that kind of question occupies your mind. [1] https://en.m.wikipedia.org/wiki/Prime_Obsession https://en.m.wikipedia.org/wiki/Prime_Obsession
  - fao_ 9y ago
    Non-mobile link: https://en.wikipedia.org/wiki/Prime_Obsession https://en.wikipedia.org/wiki/Prime_Obsession
  - heinrichf 9y ago
    And Marcus du Sautoy's "The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics" [1] is an even nicer one. [1] https://en.wikipedia.org/wiki/The_Music_of_the_Primes https://en.wikipedia.org/wiki/The_Music_of_the_Primes
- ThrustVectoring 9y ago
  Is 4 a random number?
sevenfive 9y ago
Their example uses log_10 instead of ln
- impendia 9y ago
  (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.
  - heinrichf 9y ago
    I didn't expect to see so many analytic number theorists on HN!
  - sevenfive 9y ago
    No, I mean they had a chart in the article that says Log(10) = 1. Looks like it's been removed.
    - impendia 9y ago
      Aha. Looks like the editors made (and caught) a mistake then.
mudil 9y ago
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?
- Retric 9y ago
  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.
- yathern 9y ago
  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.
  - wickawic 9y ago
    Up to a number x, there are approximately a = x/(log_2(x)) prime numbers. To a first approximation, we can assume that each of these numbers has b = log_2(x) bits. So to store all the prime numbers from 1 to x you need about a*b bits, or just 'x'. So to implement this approach you would need to store and search a space that grows linearly with the size of the largest number you expect to encounter. However, this is unnecessary because we have faster ways of telling a number is prime other than storing all the prime numbers up to that point.
mixedmath 9y ago
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.
seycombi 9y ago
Why prime numbers are usefull to Web Designers https://www.sitepoint.com/the-cicada-principle-and-why-it-matters-to-web-designers/ https://www.sitepoint.com/the-cicada-principle-and-why-it-ma...
- johansch 9y ago
  Gah.
tarre 9y ago
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.
- osivertsson 9y ago
  Interesting, can you give more context on when and where this was?
  - tarre 9y ago
    We were both in a very small school in the countryside and when I was on 5th and she on 6th grade, we had wonderful teacher, Harri Ketamo (Google him and you'll end up wondering, what on earth he was doing in that school). Harri was especially interested in teaching mathematics. As there was only about ten pupils in the class, he had possibility to teach more advanced pupils further covering among other things programming and prime numbers. I don't remember if it was in school or after school, when we had with Kaisa a debate over whether or not there was infinite number of prime numbers. The next day or so she presented, that it has been proven and here it is. Back in those days I didn't get it completely, but she was already there.
- soberhoff 9y ago
  I personally prefer Cantor's diagonal argument. Especially when considering how many useful results have come from it.
  - jacobolus 9y ago
    Can you define “useful”? Arguably anything requiring infinite steps is essentially a pure thought experiment with no physical-world ramifications. Any mathematical theory we can apply to physical-world science/engineering can be recast to not have anything to do with Cantor’s set theory. But maybe you mean useful to making analysis proofs... in which case fair enough.
    - 9y ago
deleted 9y ago
[deleted]

77 points by heinrichf 9y ago

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.

deleted 9y ago
[deleted]
deleted 9y ago
[deleted]
deleted 9y ago
[deleted]
mixedmath 9y ago
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"). [1]: https://terrytao.wordpress.com/2016/03/14/biases-between-consecutive-primes/ https://terrytao.wordpress.com/2016/03/14/biases-between-con...
osivertsson 9y ago
Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics [1] is a nice read if that kind of question occupies your mind. [1] https://en.m.wikipedia.org/wiki/Prime_Obsession https://en.m.wikipedia.org/wiki/Prime_Obsession
- fao_ 9y ago
  Non-mobile link: https://en.wikipedia.org/wiki/Prime_Obsession https://en.wikipedia.org/wiki/Prime_Obsession
- heinrichf 9y ago
  And Marcus du Sautoy's "The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics" [1] is an even nicer one. [1] https://en.wikipedia.org/wiki/The_Music_of_the_Primes https://en.wikipedia.org/wiki/The_Music_of_the_Primes
ThrustVectoring 9y ago
Is 4 a random number?

sevenfive 9y ago

Their example uses log_10 instead of ln

impendia 9y ago
(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.
- heinrichf 9y ago
  I didn't expect to see so many analytic number theorists on HN!
- sevenfive 9y ago
  No, I mean they had a chart in the article that says Log(10) = 1. Looks like it's been removed.
  - impendia 9y ago
    Aha. Looks like the editors made (and caught) a mistake then.

mudil 9y ago

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?

Retric 9y ago
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.
yathern 9y ago
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.
- wickawic 9y ago
  Up to a number x, there are approximately a = x/(log_2(x)) prime numbers. To a first approximation, we can assume that each of these numbers has b = log_2(x) bits. So to store all the prime numbers from 1 to x you need about a*b bits, or just 'x'. So to implement this approach you would need to store and search a space that grows linearly with the size of the largest number you expect to encounter. However, this is unnecessary because we have faster ways of telling a number is prime other than storing all the prime numbers up to that point.

mixedmath 9y ago

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.

seycombi 9y ago

Why prime numbers are usefull to Web Designers https://www.sitepoint.com/the-cicada-principle-and-why-it-matters-to-web-designers/ https://www.sitepoint.com/the-cicada-principle-and-why-it-ma...

johansch 9y ago
Gah.

tarre 9y ago

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.

osivertsson 9y ago
Interesting, can you give more context on when and where this was?
- tarre 9y ago
  We were both in a very small school in the countryside and when I was on 5th and she on 6th grade, we had wonderful teacher, Harri Ketamo (Google him and you'll end up wondering, what on earth he was doing in that school). Harri was especially interested in teaching mathematics. As there was only about ten pupils in the class, he had possibility to teach more advanced pupils further covering among other things programming and prime numbers. I don't remember if it was in school or after school, when we had with Kaisa a debate over whether or not there was infinite number of prime numbers. The next day or so she presented, that it has been proven and here it is. Back in those days I didn't get it completely, but she was already there.
soberhoff 9y ago
I personally prefer Cantor's diagonal argument. Especially when considering how many useful results have come from it.
- jacobolus 9y ago
  Can you define “useful”? Arguably anything requiring infinite steps is essentially a pure thought experiment with no physical-world ramifications. Any mathematical theory we can apply to physical-world science/engineering can be recast to not have anything to do with Cantor’s set theory. But maybe you mean useful to making analysis proofs... in which case fair enough.
  - 9y ago

deleted 9y ago

[deleted]