Dreaming of prime numbers in short intervals | Hacker News Reader

Dreaming of prime numbers in short intervals

quantamagazine.org

77 pointsheinrichf39 comments

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.

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

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.

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

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.

every result about undecidability uses Cantor's diagonalization.

I think infinities also have use in the real world. Take the insolubility of the quintic. You can reword this as saying that none of the infinitely many candidate solutions for quintics work. Its real world utility is straightforward: there's no point to continue looking for a solution.

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

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

[1]: https://terrytao.wordpress.com/2016/03/14/biases-between-con...

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

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

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

Is 4 a random number?

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?

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.

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.

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.

Why log_2? It should be natural logarithm.

It only differs by a constant factor, so in the end it doesn't matter when you want the asymptotic complexity of storing all primes up to x.

Sure, you would still get that the space needed grows linearly, but you're off by almost 50% in your storage requirements. More importantly, you're confusing people with explicitly wrong statement for no benefit, people who might not realize that it's actualy ln, not log_2, and spread the mistake to other people.

The bound we have is apparently: https://en.wikipedia.org/wiki/Prime-counting_function#Inequa...

x/log x < π(x) < 1.25506x/log x

If you want to rewrite that using log2, you get:

1.44270x/log2 x < π(x) < 1.81067x/log2 x

I would hardly call the previous poster’s comment an “explicitly wrong statement for no benefit”. We’re talking about number of bits here.

You're missing the point. Asymptotically, we have much better bound than 1.25506 -- the asymptotic bound is indeed 1+e for any e > 0, as the prime number theorem explicitly says that lim pi(n)/(n/log n)) = 1. The constant 1.25506... = 30 * log(113)/113 is only relevant because that's the the smallest global bound, which is there to take care of n = 113.

If you rewrite it to log_2, you get the 1.442... constant, which throws your calculations off by "almost 50%" I mentioned in my comment above. And yeah, it doesn't change anything in the qualititative analysis of storage needs, but that's not my point -- my point is that in math, you should avoid saying things that are explicitly wrong, unless there are very good reasons to do so.

You're totally right, I was stuck in CS world and write log_2 instead of ln absent mindedly

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.

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

The parent asked why we don't just search through all candidate primes. Phrased differently, my response is that there are too many. This remains true if you replace "primes" by "indices" --- there are still too many.

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

> 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/

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

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

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

Gah.

Their example uses log_10 instead of ln

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

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

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

Aha. Looks like the editors made (and caught) a mistake then.

Reply on news.ycombinator.com