[HN Gopher] The First 50M Prime Numbers (1975) [pdf]
___________________________________________________________________
The First 50M Prime Numbers (1975) [pdf]
Author : quickfox
Score : 87 points
Date : 2024-12-15 22:11 UTC (1 days ago)
(HTM) web link (people.mpim-bonn.mpg.de)
(TXT) w3m dump (people.mpim-bonn.mpg.de)
| mulhoon wrote:
| The Psychology Calendar '78 sure has a cool cover.
| 486sx33 wrote:
| Is this helpful for ... RSA testing ?
| kkylin wrote:
| Maybe for teeny weeny keys -- the 50e6th prime number is ~30
| bits?
| vouaobrasil wrote:
| 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.
| philiplu wrote:
| 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 wrote:
| 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?
| philiplu wrote:
| 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.
| dhosek wrote:
| 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
|
| [?]
|
| 1. Reader, I filled it up.
| macintux wrote:
| 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.
| volemo wrote:
| [flagged]
| eru wrote:
| You can produce such a PDF at home these days fairly easily.
| dhosek wrote:
| 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.
| eru wrote:
| Well, you could build a pdf that does the calculation.
|
| (PDF is actually an executable format and allows
| computation inside of it.)
| hackerknew wrote:
| 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 wrote:
| And I love how he didn't really assume any prior knowledge for
| the reader. It was very accessibly written.
| worldvoyageur wrote:
| 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.
| jdewerd wrote:
| 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=57896
| 04461865809771178549250434395392663499233282028201972879200395656
| 4819949.
| lifthrasiir wrote:
| 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.
| jdewerd wrote:
| 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.
| shric wrote:
| Yeah, although that's better than 19937 ones in a row.
| quuxplusone wrote:
| 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.)
| ape4 wrote:
| On a Linux command line: echo '2^255-19' | bc
| spacemonkey92 wrote:
| 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 wrote:
| 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.
| jdewerd wrote:
| 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.
| bux93 wrote:
| 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'?)
| eru wrote:
| 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_pomu wrote:
| We also have cryptography that uses elliptic curves rather than
| large primes.
| johnklos wrote:
| 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 wrote:
| 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 wrote:
| > 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 wrote:
| 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 wrote:
| 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.
| Someone wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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_pomu wrote:
| 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 wrote:
| 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 ?)
___________________________________________________________________
(page generated 2024-12-16 23:02 UTC)