Hacker News Reader

Comment by shric | Hacker News Reader

No, at the cryptographic scale of prime numbers the lookup table would need to be far too big in terms of both time to generate and storage required.

For smaller numbers see various prime sieves (Atkin, Eratosthenes)

View on HN

Time to generate I get, but you could always augment the table over time and fall back to standard methods otherwise (and store the result).

Storage I have a harder time wrapping my head around. Aren’t primes quite sparse at cryptographic magnitudes? And are the primes used for (say) 256-bit encryption about the same magnitude, narrowing the dimension of storage required?

The primes are quite dense. There are roughly n/log(n) primes below n. Meaning 1 in 256 numbers with 256 bits are prime. That's 2^(248) primes.

For RSA one typically use 2048 or 4096 bit primes.

Natural logarithm (base e, not base 2, so one in 177.4 for 256 bit numbers), but that doesn't change your general point.

If your question is purely "is the value prime" the Fermat primaility test is very fast, probably about as fast as a hash table lookup on a table that large. Running Baillie–PSW to eliminate false positives isn't a huge deal either as it will only need to run if Fermat passes. It's not a horrible idea on its face and may indeed be a little faster, at the cost of lots of memory. I don't know of a use case where it would be worth it.

https://en.wikipedia.org/wiki/Prime_number_theorem

Reply on news.ycombinator.com