Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin2!goblin.stu.neva.ru!newsfeed1.swip.net!uio.no!news.tele.dk!news.tele.dk!small.news.tele.dk!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <drsalists@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.066
X-Spam-Evidence: '*H*': 0.87; '*S*': 0.00; 'subject: [': 0.09; 'things,': 0.09; 'cc:addr:python-list': 0.11; 'algorithm.': 0.16; 'cc:name:python list': 0.16; 'subject:Prime': 0.16; 'sat,': 0.16; 'wrote:': 0.18; 'pfxlen:0': 0.19; 'slightly': 0.19; '>>>': 0.22; 'tests': 0.22; 'cc:addr:python.org': 0.22; 'test.': 0.24; 'cc:2**0': 0.24; 'header:In-Reply-To:1': 0.27; 'am,': 0.29; 'quickly': 0.29; 'message-id:@mail.gmail.com': 0.30; 'url:wiki': 0.31; 'usually': 0.31; "d'aprano": 0.31; 'division': 0.31; 'sep': 0.31; 'steven': 0.31; 'url:wikipedia': 0.31; "can't": 0.35; 'beyond': 0.35; 'no,': 0.35; 'test': 0.35; 'but': 0.35; 'received:google.com': 0.35; '+0200,': 0.36; 'url:org': 0.36; 'subject:]': 0.38; 'that,': 0.38; 'how': 0.40; 'even': 0.60; 'numbers': 0.61; 'simple': 0.61; 'field': 0.63; 'more': 0.64; 'different': 0.65; 'prime': 0.74; 'trial': 0.83; 'actually,': 0.84; 'composite': 0.91
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=5q8KgvsgCcbUOrZDsGdzeVFhBsXDSmXWT61W1Qe5cyQ=; b=skReOqEZvAOmaJ3tffABLS6UJxa7dOiisKX1OBaGJD2WgoFpDK5iS1k6X4DBFWIGZj nVXqvdNlt6c3zTVww3dPUvrPhWp7SWCGio9NaKOaVCPujrEHouxfO8bOxaAcFhH2hpOB Zsu7f4ca1mN2CPzH3ZHE0xRw8y9UPE/+3TcFYtuFkpT+Ugsz0pySZ6s06PKdpklvhLtg 9visjyRRHNp3XYKs/SKXU8IH9nAdX5TZ73xhKYMdG69kvMFkG1Xc18XF94nWi2NP9VBW 8Lg0vThumVFugCQhnc9RKvYWmLQALgLstqtEhzxgdcEYBlboBMFRZDM5Uf+5uCZALpcA bMFA==
MIME-Version: 1.0
X-Received: by 10.152.179.226 with SMTP id dj2mr14264302lac.40.1410146610858; Sun, 07 Sep 2014 20:23:30 -0700 (PDT)
In-Reply-To: <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> <c73nsiFcp8eU1@mid.individual.net>
Date: Sun, 7 Sep 2014 20:23:30 -0700
Subject: Re: Prime testing [was Re: My backwards logic]
From: Dan Stromberg <drsalists@gmail.com>
To: Peter Pearson <pkpearson@nowhere.invalid>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: Python List <python-list@python.org>
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.13860.1410146613.18130.python-list@python.org>
Lines: 30
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1410146613 news.xs4all.nl 2882 [2001:888:2000:d::a6]:48347
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:77692

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=C3=ADnez 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 whe=
ther
>>> (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 =
=3D=3D 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.