Menu
Using the probabilistic version of the Miller-Rabin test, I have generated a list of medium-large (200-300 digit) probable primes. But probable ain't good enough! I need to know these numbers are prime. Is there a library -- preferably wrapped or wrappable in Python -- that implements one of the more efficient primality proving algorithms?
Alternatively, does anyone know where I can find a clear, detailed, and complete description of ECPP (or a similarly fast algorithm) that does not assume a great deal of prior knowledge?
Update: I've found a Java implementation of another test, APRT-CLE, that conclusively proves primality. It verified a 291-digit prime candidate in under 10 minutes on an atom processor. Still hoping for something faster, but this seems like a promising start.
852
The most elementary approach to primality proving is trial division: attempt to divide N by every integer p ≤ √ N. If no such p divides N, then N is prime. This takes O( √ N M(log N)), which is impractical for large N, but it serves as a useful base case for more sophisticated recursive methods that we will consider.
To find individual small primes trial division works well. To test n for primality (to see if it is prime) just divide by all of the primes less than the square root of n. For example, to show is 211 is prime, we just divide by 2, 3, 5, 7, 11, and 13.
For large integers, the most efficient primality tests are pro- babilistic. However, for integers with a small fixed number of bits the best tests in practice are deterministic. Currently the best known tests of this type involve 3 rounds of the Miller-Rabin test for 32-bit integers and 7 rounds for 64-bit integers.
To find whether a larger number is prime or not, add all the digits in a number, if the sum is divisible by 3 it is not a prime number. Except 2 and 3, all the other prime numbers can be expressed in the general form as 6n + 1 or 6n - 1, where n is the natural number.
As an algorithm that gives a reliable polynomial primality test, consider AKS. There is an older SO article referencing implementations and presentations of the algorithm.
73
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
