Dreaming of prime numbers in short intervals

https://www.quantamagazine.org/kaisa-matomaki-dreams-of-primes-20170720/

by heinrichf • 9 years ago

77 39 9 years ago

brianberns• 9 years 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.

mixedmath4• 9 years 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-con...

osivertsson2• 9 years 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

fao_• 9 years ago

Non-mobile link: https://en.wikipedia.org/wiki/Prime_Obsession

heinrichf2• 9 years 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

ThrustVectoring• 9 years ago

Is 4 a random number?

sevenfive2• 9 years ago

Their example uses log_10 instead of ln

impendia2• 9 years 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.

heinrichf2• 9 years ago

I didn't expect to see so many analytic number theorists on HN!

sevenfive2• 9 years ago

No, I mean they had a chart in the article that says Log(10) = 1. Looks like it's been removed.

mudil• 9 years 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• 9 years 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• 9 years 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.

wickawic2• 9 years 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.

mixedmath4• 9 years ago

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.

dalore• 9 years ago

yes but you don't store the number, you store the index to the prime and a function to generate it.

LiveOverflow• 9 years ago

There is a database for prime factorisation: https://factordb.com/

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

schoen2• 9 years ago

Or having two bad keys sharing one same prime - then you can use Euclidean algorithm (greates common divisor).

I wrote a puzzle in 2012 to help people understand this issue:

http://www.loyalty.org/~schoen/rsa/

schoen2• 9 years ago

I posted further down in this thread about my puzzle

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

infinity0• 9 years ago

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

mixedmath4• 9 years 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• 9 years ago

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

johansch• 9 years ago

Gah.

tarre2• 9 years 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.

osivertsson2• 9 years ago

Interesting, can you give more context on when and where this was?

tarre2• 9 years 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.

soberhoff2• 9 years ago

I personally prefer Cantor's diagonal argument. Especially when considering how many useful results have come from it.

jacobolus2• 9 years 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.

zem• 9 years ago

millay would agree: https://genius.com/Edna-st-vincent-millay-euclid-alone-has-l...

Dreaming of prime numbers in short intervals

Related Stories