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: <26905@linus.UUCP>
Date: 14 Mar 88 19:38:04 GMT
References: <977@thumper.bellcore.com> <7440@brl-smoke.ARPA> <26797@linus.UUCP> <7449@brl-smoke.ARPA> <26822@linus.UUCP> <7453@brl-smoke.ARPA> <11288@duke.cs.duke.edu>
Reply-To: bs@linus.UUCP (Robert D. Silverman)
Organization: The MITRE Corporation, Bedford MA
Lines: 35


 
In article <11288@duke.cs.duke.edu> srt@duke.UUCP (Stephen R. Tate) writes:
 
etc.
>>=:-A proof of the RH would give important cryptographic results.
>>=:-It would mean a fast, deterministic Polynomial Time prime proving algorithm.
>>=:What advantage would a formal proof of RH
>>=:(that perhaps few could understand anyway) bring to that effort?
>>=I think you are being deliberately obtuse and pedantic.
>>No, somehow I must have had the mistaken impression that you were talking
>>about PRACTICAL cryptography, for example cryptanalysis (for which the
 
etc.
>
>First off, the results in primality proving are important in a practical
>sense.  I assume Bob is talking about Goldwasser and Kilians primality
 
No, the Goldwasser-Killian algorithm depends on a separate conjecture
known as Cramer's conjecture concerning the distribution of primes in
short intervals. Cramer's conjecture does not follow from RH.

What I am talking about is that if RH is true then a prime p must
have a primitive root less than 2 ln^2(p). This leads directly to a
deterministic algorithm that runs in time O(ln^4(p)).

An algorithm due to H. Cohen and H. Lenstra runs in time
O(ln(p)^ lnlnln(p)) and is computer practical for moderate p
(up to say 300 digits). A variation of Goldwasser-Killian that
depends on elliptic curves having complex multiplication (and hence
a pre-determined order of the Mordell-Weil group) has been 
implemented by Oliver Atkin at U. Ill./Chicago


Bob Silverman