4 ms·
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 small
by shric 5y ago
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)
- nonfamous 5y agoTime 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?
- thomasahle 5y agoThe 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.
- not2b 5y agoNatural logarithm (base e, not base 2, so one in 177.4 for 256 bit numbers), but that doesn't change your general point.
- willcipriano 5y agoIf 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.
- deleted 5y ago[deleted]
- not2b 5y agohttps://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem