Prime testing [was Re: My backwards logic]

[Dan Stromberg]

On Sun, Sep 7, 2014 at 11:53 AM, Peter Pearson
<pkpearson at 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.