The First 50M Prime Numbers (1975) [pdf]

[jdewerd]

The 50 000 000th prime is 982451653, but fun fact: you may have already memorized a prime much larger than this without even realizing you have done so!

2^255-19

This is where Curve 25519 and the associated cryptography (ed25519, x25519) gets its name from. Written out, 2^255-19=57896044618658097711785492504343953926634992332820282019728792003956564819949.

[lifthrasiir]

You could have memorized even large one if you are familiar with the full name of the Mersenne Twister PRNG: MT19937 is named so because its period is 2^19937-1 which is a prime number (in fact, the largest known one at the time of Zigler's writing). In my knowledge any larger prime number hasn't been used for the practical purpose.

[ape4]

On a Linux command line:

    echo '2^255-19' | bc

[hackerknew]

I like how the feeling of the author's excitement about the topic is embedded in the text

""" upon looking at these numbers one has the feeling of being in the presence of one of the inexplicable secrets of creation. """

""" I hope that with this and the other pictures I have shown, I have communicated a certain impression of the immense beauty of the prime numbers and of the endless surprises which they have in store for us. """

[fracus]

And I love how he didn't really assume any prior knowledge for the reader. It was very accessibly written.

[worldvoyageur]

Of note that even then, for the seemingly impossibly large prime numbers, they gave dual credit to the researcher and the computer used. So, credit for the largest prime in 1963 went to Gillies and ILIAC 2. When that record was broken in 1972, credit went to Tuckerman and IBM 360.

[johnklos]

It's simply amazing what people did with the limited computing they had available to them at the time. Even when it was available, you only got an allotment of it and had to figure out how to do everything you wanted within that allotment.

Here we are with many orders of magnitude of computing power that we have to ourselves, 24/7, and mostly we're using all that power to browse the Internet :P

Calculating the first 50,000,000 primes takes less than ten minutes (using no memory - that is, not a sieve). The 50,000,000th prime, BTW, is 982,451,653. I wonder what the author of this paper would've been able to do with the kind of processing available to us.

[dhosek]

The IBM mainframe I had access to in the 80s at University of Illinois of Chicago had quotas of compute time (that reset on a weekly basis). Since I worked in the computer center, I had an account that had a larger quota (or possibly unlimited, I don’t remember now, perhaps the unlimited was when I advanced to a staff level?). One of the more entertaining things was when one class started having people code in Ada. Unfortunately, the Ada compiler was a CPU hog and a single compilation was enough to use up a week’s quota. As a result, students had to work in teams and share access to their online disks (VM/CMS did allow different modes that allowed privacy for things like email to be kept even while allowing read access to the rest of the stuff on the disk—also noteworthy was the lack of subdirectories). The team members had to switch to a different account after each day‘s work since they would exhaust each account’s quota. If you inadvertently logged out too soon, it was possible that a homework assignment could not be completed.

[Someone]

> Even when it was available, you only got an allotment of it and had to figure out how to do everything you wanted within that allotment.

IIRC computing primes was a popular way to test hardware; it’s fairly easy to compare results between machines, and both having a faster CPU, more CPUs and having more memory (simple example: if you do trial division, you can keep a larger table of ‘small’ primes around to quickly weed out most integers)) will speed up computations.

It then sort-of became a marketing goal to beat your competitors, so cleverer and cleverer algorithms were developed.

Because of that, those records had less trouble with resource allotments.

[Someone]

For those who want the data: https://t5k.org/lists/small/millions/

(Only useful if you have a large disk but not a fast CPU. As that page says “Usually it is faster to run a program on your own computer than to download them”)

[lifthrasiir]

Should have generated all these files in JavaScript! :-p Something like primegen [1], which took 4.1s in my particular box for all fifty files, or any reasonable Rust sieve-of-Atkin implementation should be easy to compile to wasm.

[1] https://cr.yp.to/primegen.html

[lIl-IIIl]

Pedantic correction:

"You certainly all know what a prime number is: it is a natural number bigger than 1 which is divisible by no other natural number except for 1."

By that definition, the set of prime numbers is an empty set. (All natural numbers greater than 1 are divisible by at least two other numbers: 1 and itself).

[thrance]

I think the definition is correct, they say "divisible by no other natural number". Which implies we don't count the number itself as a divisor.

[lordnacho]

I had a question about these prime number announcements you hear now and again.

When there's a new "largest prime" announced, does that mean we know all the primes below that number?

[ndsipa_pomu]

No - it's common to try to find large Mersenne Primes (https://en.wikipedia.org/wiki/Mersenne_prime) which are primes that are one less than a power of 2. This will miss out a lot of non-Mersenne primes.

[bloak]

No. The "largest prime" announcements generally refer to a Mersenne prime, which is one that is one less than a power of two. There is a faster primality test for such numbers.

[cbm-vic-20]

Corollary: given two numbers a and b, is it possible to prove there are no prime numbers between them? (ie, does there exist a prime p such that a < p < b ?)

[philiplu]

Back in the 70s, when I was a teen, we had a set of Encyclopedia Britannica. It came with a service where you could send off for various pamphlets for more focused information. I sent away for a paper listing pi to 10k or maybe 100k digits. By the late 70s/early 80s, that was outdated, as I wrote code to find those for myself (though e to many places was far easier).

[anditherobot]

That's a very cool accomplishment.

What language did you use to write the code?

I also have another question, did you witness the transition from punched cards to terminals?

[spacemonkey92]

I wonder what would happen if someone discovered an efficient algorithm for finding or predicting prime numbers or their factors. It would put the fundamentals of internet security at risk and likely much more. Has anyone ever considered a plan B for such a scenario?

[eru]

I'm not sure what you mean by predicting prime numbers?

It's very, very easy to find big prime numbers: you generate a random number in the range that you are interested in, and then check whether it's prime. Repeat until you find a prime; they are fairly dense (a random number `n` has about a 1/log(n) chance of being prime) so you don't have to try too often.

In fact, that's how we find big primes for creating things like RSA key-pairs.

Testing a number for primality can also be done fairly quick. In general, much, much faster than finding the factors of a composite number. See https://en.wikipedia.org/wiki/Primality_test

> Has anyone ever considered a plan B for such a scenario?

Yes, quantum resistance cryptography is a thing. See the other comments.

[fragmede]

Yes. Shor's algorithm on quantum computers represents such a theoretical possibility, so the industry is moving to resistant algorithms that aren't based on products of large primes such as elliptic curve cryptography.

[ndsipa_pomu]

We also have cryptography that uses elliptic curves rather than large primes.

[mulhoon]

The Psychology Calendar '78 sure has a cool cover.

[volemo]

[flagged]

[eru]

You can produce such a PDF at home these days fairly easily.

[486sx33]

Is this helpful for … RSA testing ?

[vouaobrasil]

No, it's not. Too small. If generating a list of primes helped in RSA testing then RSA would be useless since generating primes is about the slowest sort of factoring algorithm in the world.

[kkylin]

Maybe for teeny weeny keys -- the 50e6th prime number is ~30 bits?