Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Peter Pearson <pkpearson@nowhere.invalid>
Newsgroups: comp.lang.python
Subject: Re: Prime testing [was Re: My backwards logic]
Date: 7 Sep 2014 18:53:06 GMT
Lines: 18
Message-ID: <c73nsiFcp8eU1@mid.individual.net>
References: <1enj0att6bkrnvb81rhma5dbuk3h28agl8@4ax.com> <lueeat$rdu$1@dont-email.me> <540ae440$0$29995$c3e8da3$5496439d@news.astraweb.com> <mailman.13838.1410025280.18130.python-list@python.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Trace: individual.net yoYR6jawz+uWCqjJrLdjDAARZCkLq+048hZhT29dTcEb9MKGfM
Cancel-Lock: sha1:CG/KPscoeGZvjX7P1GYA85uX7JY=
User-Agent: slrn/pre1.0.0-18 (Linux)
Xref: csiph.com comp.lang.python:77680

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.

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.