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

https://people.mpim-bonn.mpg.de/zagier/files/doi/10.1007/BF03039306/fulltext.pdf

by quickfox • 2 years ago

93 39 2 years ago

people.mpim-bonn.mpg.de

mulhoon• 2 years ago

The Psychology Calendar '78 sure has a cool cover.

486sx33• 2 years ago

Is this helpful for … RSA testing ?

kkylin• 2 years ago

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

vouaobrasil• 2 years ago

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.

philiplu2• 2 years ago

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• 2 years ago

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?

philiplu2• 2 years ago

This would have been assembly code, probably 6809 or 68000 system I had back then. 6809 would have required dumping intermediate data to a disk. I don't recall just when I first got a hard-disk, which would probably have been a massive 10 megabytes in size.

And yes, I saw that transition. I learned to program using Fortran IV and IBM 11/30 assembly in the mid-70s, using punched cards. Wrote a MIXAL assembler and simulator for the minicomputer at the local college around 1976; it was about 7000 punched cards in length, all assembly. Got a Commodore PET in 1978, moved on to SS-50 based 6809 and 68008 systems in the late 70s/early 80s, with a serial terminal.

volemo• 2 years ago

[flagged]

eru3• 2 years ago

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

dhosek3• 2 years ago

But if you want to go really hard core, the thing to do is to build a mechanical Babbage-style machine that will calculate those 50,000,000 primes and print them letterpress.

hackerknew• 2 years ago

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• 2 years ago

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

worldvoyageur• 2 years ago

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.

jdewerd3• 2 years ago

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.

lifthrasiir2• 2 years ago

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.

jdewerd3• 2 years ago

Cool, I hadn't run into it before so thanks for introducing me!

I was going to include the digits for comparison, but yes, on second thought 6002 digits is probably too much for polite inclusion in a HN post.

ape4• 2 years ago

On a Linux command line:

    echo '2^255-19' | bc

spacemonkey92• 2 years ago

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?

fragmede• 2 years ago

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.

jdewerd3• 2 years ago

I thought Shor's algorithm could attack ECC too and the lattice crypto with the sci-fi crystal names (Kyber and Dilithium) was the response?

If I go to https://www.google.com using Chrome and Inspect > Security, I see it is using X25519Kyber768Draft00 for key exchange. X25519 is definitely ECC and and Kyber is being used for key encapsulation (per a quick google). I don't know to what extent it can be used independently vs it's new so they are layering it up until it has earned the right to stand on its own.

eru3• 2 years ago

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.

ndsipa_pomu2• 2 years ago

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

johnklos• 2 years ago

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.

dhosek3• 2 years ago

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.

Someone2• 2 years ago

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.

lIl-IIIl• 2 years ago

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• 2 years ago

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.

Someone2• 2 years ago

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

lifthrasiir2• 2 years ago

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

lordnacho• 2 years ago

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?

bloak• 2 years ago

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.

ndsipa_pomu2• 2 years ago

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.

cbm-vic-20• 2 years ago

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

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

Related Stories