5 ms·
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 h
by nonfamous 5y ago
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?
- 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