🚀 go-pugleaf

 
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