The First 50M Prime Numbers (1975) [pdf] • Hacker News Board

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

#31

Post by bux93 » Mon, Dec 16, 2024, 9:18 AM UTC

jdewerd wrote: post #16

fragmede wrote: post #14

Earlier quoted context omitted.

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 independen…

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

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

#32

Post by lordnacho » Mon, Dec 16, 2024, 9:32 AM UTC

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?

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

#33

Post by bloak » Mon, Dec 16, 2024, 9:49 AM UTC

lordnacho wrote: post #32

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?

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.

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

#34

Post by ndsipa_pomu » Mon, Dec 16, 2024, 9:49 AM UTC

lordnacho wrote: post #32

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?

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.

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

#35

Post by ndsipa_pomu » Mon, Dec 16, 2024, 9:51 AM UTC

spacemonkey92 wrote: post #13

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?

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

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

#36

Post by thrance » Mon, Dec 16, 2024, 10:50 AM UTC

lIl-IIIl wrote: post #28

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

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.

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

#37

Post by [deleted] » Mon, Dec 16, 2024, 11:02 AM UTC

lIl-IIIl wrote: post #28

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

[deleted]

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

#38

Post by vouaobrasil » Mon, Dec 16, 2024, 11:31 AM UTC

486sx33 wrote: post #3

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.

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

#39

Post by lifthrasiir » Mon, Dec 16, 2024, 1:24 PM UTC

Someone wrote: post #30

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

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

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

#40

Post by cbm-vic-20 » Mon, Dec 16, 2024, 2:38 PM UTC

lordnacho wrote: post #32

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?

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