Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork1.9k
Description
The website for helping people select few Miller-Rabin bases,https://miller-rabin.appspot.com/, has a small section on "Hashing". There a hash function is used to link the input number to a certain base (or set of bases) where it is known beforehand that all numbers that can hash to this bucket are not a pseudoprime of this base. In other words, dynamic base selection to reduce the number of bases used.
The current state of this work is on Berg's website,https://www.techneon.com/. I quote from the website:
These primality tests extend Steve Worley's 32 bit primality test. They improve onJim Sinclair's test that uses 7 SPRP tests. 32 bit numbers are checked with a single SPRP test, two are used for 49 bit numbers, and three for 64 bit numbers.
Numbers under 2^32 can be tested using the SPRP bases in: [is.prime.32.base.data](https://www.techneon.com/download/is.prime.32.base.data)Numbers from 2^32 to 2^64 can be tested using the base pairs in: [is.prime.64.base.data](https://www.techneon.com/download/is.prime.64.base.data)[...]
The sprp test can be substantially sped up with negligible overhead by interleaving it with trial division over small primes. A modulus by a small prime is computed in each iteration of the loop for Base ^ D mod N.
Numbers with 49 or fewer bits fit in a floating point double. The modulus can be computed by multiplying by the reciprocal of small primes that are pre-computed and stored in an array. Division is avoided and processors can perform floating point operations in parallel with integer operations.
I don't know who needs this thing (for one thing, nobody is memorizing this!), but if anyone really wants that bit of speed, adding a small link would tell them where to look.