The First 50M Prime Numbers (1975) [pdf](people.mpim-bonn.mpg.de)
people.mpim-bonn.mpg.de
The First 50M Prime Numbers (1975) [pdf]
https://people.mpim-bonn.mpg.de/zagier/files/doi/10.1007/BF03039306/fulltext.pdf
41 comments
On a Linux command line:
echo '2^255-19' | bcYou 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.
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.
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.
Yeah, although that's better than 19937 ones in a row.
https://oeis.org/A004023 "Indices of prime repunits: numbers k such that 11...111 (with k 1's) = (10^k - 1)/9 is prime."
OEIS says "19937 ones in a row" isn't prime, but "1031 ones in a row" is.
And "8177207 ones in a row" is at least a probable prime. (Which you can maybe remember as a seven-digit phone number, or as either BITTZOT or LOZLLIB depending on how you prefer to hold your calculator. But those mnemonics are wasted if (10^{81777207}-1)/9 turns out to be merely pseudoprime.)
OEIS says "19937 ones in a row" isn't prime, but "1031 ones in a row" is.
And "8177207 ones in a row" is at least a probable prime. (Which you can maybe remember as a seven-digit phone number, or as either BITTZOT or LOZLLIB depending on how you prefer to hold your calculator. But those mnemonics are wasted if (10^{81777207}-1)/9 turns out to be merely pseudoprime.)
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.
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.
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.
> 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.
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.
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”)
(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”)
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
[1] https://cr.yp.to/primegen.html
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).
"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).
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.
[deleted]
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?
When there's a new "largest prime" announced, does that mean we know all the primes below that number?
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.
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.
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 ?)
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?
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.
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.
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.
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.
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.
It's new so they are layering it up.
At https://pq.cloudflareresearch.com/ you can also see if your browser supports X25519MLKEM768, the X25519Kyber512Draft00 and X25519Kyber768Draft00 variants are deprecated ('obsolete'?)
We also have cryptography that uses elliptic curves rather than large primes.
Is this helpful for … RSA testing ?
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.
Maybe for teeny weeny keys -- the 50e6th prime number is ~30 bits?
The Psychology Calendar '78 sure has a cool cover.
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).
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?
What language did you use to write the code?
I also have another question, did you witness the transition from punched cards to terminals?
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.
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.
You just reminded me of when I bought my first PC in 1990 and one of my former professors, on learning I had bought it with a 200MB hard drive declared that I was crazy to buy such a large hard drive because I would never fill it up.¹
⸻
1. Reader, I filled it up.
⸻
1. Reader, I filled it up.
One of my more embarrassing memories (technical ones, anyway) was having an argument with a couple of friends in college in 1988/89. I felt that sure, an internal hard drive is a nice feature, but swapping floppies wasn't all that terrible.
You could have made a significant amount of money betting against my technical predictions over the last few decades.
You could have made a significant amount of money betting against my technical predictions over the last few decades.
[flagged]
You can produce such a PDF at home these days fairly easily.
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.
Well, you could build a pdf that does the calculation.
(PDF is actually an executable format and allows computation inside of it.)
(PDF is actually an executable format and allows computation inside of it.)
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. """
""" 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. """
And I love how he didn't really assume any prior knowledge for the reader. It was very accessibly written.
[deleted]
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.
2^255-19
This is where Curve 25519 and the associated cryptography (ed25519, x25519) gets its name from. Written out, 2^255-19=57896044618658097711785492504343953926634992332820282019728792003956564819949.