Path: utzoo!mnetor!uunet!husc6!bloom-beacon!gatech!mcnc!duke!srt
From: srt@duke.cs.duke.edu (Stephen R. Tate)
Newsgroups: sci.crypt
Subject: Re: Fermat's Last Theorem apparently proven
Message-ID: <11319@duke.cs.duke.edu>
Date: 17 Mar 88 15:25:13 GMT
References: <977@thumper.bellcore.com> <7440@brl-smoke.ARPA> <26797@linus.UUCP> <11288@duke.cs.duke.edu> <7738@alice.UUCP> <27072@linus.UUCP>
Reply-To: srt@duke.UUCP (Stephen R. Tate)
Organization: Duke University, Durham NC
Lines: 34

In article <27072@linus.UUCP> bs@gauss.UUCP (Robert D. Silverman) writes:
>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.

The algorithm I was referring to above and was commented on is different
from what you are saying.  The Goldwasser and Killian algorithm always
gives a (provably) correct certificate with no assumptions.  The running
time is probabalistic, and based on Cramer's conjecture (not RH, as I
originally stated).  Since the running time is probabalistic, even if
Cramer's conjecture is true, you would not know when to stop the algorithm
to disprove Cramer -- you could just be very unlucky.

I assume Bob is talking about Miller's algorithm which is based on ERH.
This does *not* produce a certificate of primality (only one of compositeness),
only a "prime" answer if it thinks the number is prime.  This could be
wrong as Bob pointed out.

-- 
Steve Tate			UUCP: ..!{ihnp4,decvax}!duke!srt
				CSNET: srt@duke
				ARPA:  srt@cs.duke.edu