Prime testing [was Re: My backwards logic]

Peter Pearson pkpearson at nowhere.invalid
Sun Sep 7 20:53:06 CEST 2014

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](

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.

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.

To email me, substitute nowhere->runbox, invalid->com.

More information about the Python-list mailing list