Closed fingolfin closed 11 months ago
That's a good point. You are correct that it is deterministic below 2^64 (modulo bugs) and is probabilistic above 2^64, but still safe enough for cryptographic purposes (assuming you don't need constant time guarantees). Specifically there are conjectured to be infinitely many cases where it falsely returns true
, but they should be rare enough that finding one would require a fairly significant breakthrough in number theory.
I updated the documentation and added a pull request I looked at the code and made the same conclusions like you
For General Integer Types: If the integer is within the range of a 64-bit integer, the Int64 implementation is used. Otherwise, the BigInt implementation is used.
For Int64 (64-bit integers): The function first checks for even numbers and identifies 2 as the only even prime. For numbers less than a certain small limit (N_SMALL_FACTORS), it uses a lookup table to quickly determine primality. For larger numbers, the function uses a combination of trial division (to rule out small prime factors) and more advanced primality tests like the Miller-Rabin test and Lucas test. The Miller-Rabin test is an efficient probabilistic test for determining if a number is composite (not prime), and the Lucas test (deterministic) is used to further confirm the primality of the number. Different bases and witnesses are chosen for the Miller-Rabin test based on the size of the number being tested.
For BigInt (arbitrarily large integers): The function performs a probabilistic primality test with a configurable number of repetitions (reps). By default, it uses 25 repetitions, which is considered safe for cryptographic applications. This implementation uses the Miller-Rabin test with randomly chosen bases.
Right now the docstring just says:
"""