Path: utzoo!mnetor!uunet!husc6!linus!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: <11288@duke.cs.duke.edu>
Date: 14 Mar 88 17:38:59 GMT
References: <977@thumper.bellcore.com> <7440@brl-smoke.ARPA> <26797@linus.UUCP> <7449@brl-smoke.ARPA> <26822@linus.UUCP> <7453@brl-smoke.ARPA>
Reply-To: srt@duke.UUCP (Stephen R. Tate)
Organization: Duke University, Durham NC
Lines: 33

In article <7453@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
>In article <26822@linus.UUCP> bs@linus.UUCP (Robert D. Silverman) writes:
>=In article <7449@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
>=:In article <26797@linus.UUCP> bs@linus.UUCP I wrote:
>=:-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
>proof of the pudding is in the eating), rather than some academic exercise.

First off, the results in primality proving are important in a practical
sense.  I assume Bob is talking about Goldwasser and Kilians primality
test/prover.  This algorithm was implemented by some people (U. of Chi., I
think), and is quite practical.  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.

And yes, if people didn't assume RH and that it would work, I doubt that
they ever would have implemented it.

Also, if you don't see the usefulness of pure theory and mathematical work,
then open your eyes....  We don't just sit around doing stuff for "academic
exercise" (even though it is kinda fun at times...  at times).

Incidentally, I think some other people (possibly the people in Chicago)
used something other than elliptic curves, and their results did *not*
depend on the RH.  Anyway, I seem to remember Shafi saying something like
that when she visited duke -- anybody know more?