Path: utzoo!mnetor!uunet!husc6!linus!bs
From: bs@linus.UUCP (Robert D. Silverman)
Newsgroups: sci.crypt
Subject: Re: Fermat's Last Theorem apparently proven
Message-ID: <27072@linus.UUCP>
Date: 16 Mar 88 13:22:54 GMT
References: <977@thumper.bellcore.com> <7440@brl-smoke.ARPA> <26797@linus.UUCP> <11288@duke.cs.duke.edu> <7738@alice.UUCP>
Reply-To: bs@gauss.UUCP (Robert D. Silverman)
Organization: The MITRE Corporation, Bedford MA
Lines: 40

In article <7738@alice.UUCP> td@alice.UUCP writes:
>
> >  The proof of the running time cannot
> >show that the algorithm will always stop in polynomial time unless the RH
> >is known to be true.  This also has practical considerations -- what if
> >there are times when the algorithm will not stop?  Then you sit there
> >waiting and waiting for your primality certificate that will never come.
>
>personally, i wouldn't sit waiting and waiting.  as soon as the run-time exceeded
>the bound implied by the Reimann Hypothesis, i'd start writing up my proof of ~RH.

All of the above sophistry is nonsense. The prime testing algorithms we
are discussing ALL stop in a time which is a polynomial function of the
logarithm of the number being tested. The difficulty is that the certificate
DOES come, but it can be WRONG if RH IS FALSE.

Here is the algorithm. By Euler's criteria we have [where (p/q) is the Legendre symbol]


If (a,p) = 1 and p is prime then

a^(p-1)/2  = (a/p) mod p.


If RH is true then there must exist a primitive root r < 2ln^2(p). Thus, if
the above test succeeds for all a less than 2ln^2(p) then p is prime. 
If RH is false it is possible that some composite p can satisfy the above
relationship for all of the relevent a's. Such composite integers would
be extremely rare, but they can exist. Your algorithm would report such
an integer to be prime when it is not and you would never know it was wrong.

Your understanding of algorithms and proof of their correctness is somewhat
limited I would say. 


The above scenario is unlikely because any number passing the probabalistic 
test is very likely to be prime.  It CAN, however, happen.

 
Bob Silverman