On Sun, Sep 7, 2014 at 11:53 AM, Peter Pearson <pkpearson@nowhere.invalid> wrote: > On Sat, 6 Sep 2014 12:53:16 +0200, Manolo Martínez wrote: >> On 09/06/14 at 08:38pm, Steven D'Aprano wrote: >>> But even that's not how the specialists do it. If you want to check whether >>> (say) 2**3000+1 is prime, you don't want to use trial division at all... >> >> When I was interested in these things, specialists would use the [number >> field sieve](https://en.wikipedia.org/wiki/General_number_field_sieve). > > No, one uses the number field sieve to *factor* large numbers. To > test for primality, one uses simple tests like Fermat's test (x**(n-1)%n == 1, > for many different x) or the slightly more complex Miller-Rabin test.
Usually you'd preceed a Miller-Rabin test with trial division by some small primes, as division by small primes identifies a lot of composites more quickly than Miller-Rabin. > These probabilistic primality tests can prove that a number is composite, > but they can't actually *prove* that a number is prime. For that, you > need a more complex test that is beyond my ken as a cryptologist. Actually, smallish numbers are always correctly identified as prime or composite by Miller-Rabin. It's the big ones that aren't. For a deterministic primality test that works on large numbers, check out the AKS algorithm. -- https://mail.python.org/mailman/listinfo/python-list
