🚀 go-pugleaf

In article <977@thumper.bellcore.com> karn@thumper.bellcore.com (Phil R. Karn) writes:
>I wonder what implications this might have for cryptography?

Probably just as many as a proof of the Riemann hypothesis.

In article <7440@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
:In article <977@thumper.bellcore.com> karn@thumper.bellcore.com (Phil R. Karn) writes:
:>I wonder what implications this might have for cryptography?
:
:Probably just as many as a proof of the Riemann hypothesis.


Sorry, this is not correct. The proof of FLT by Miyaoka has important
implications (it makes some of Falting's results effective, for example)
but they are not in cryptography. A proof of the RH would give important
cryptographic results. It would mean a fast, deterministic Polynomial
Time prime proving algorithm.

Bob Silverman

> [The theorem states that X^N + Y^N = Z^N, where X,Y,Z,N are all integer,
> has no solutions when N is greater than 2].

"Where X,Y,Z,N are all *positive* integer", please, or solutions are trivial.
-- 
Those who do not understand Unix are |  Henry Spencer @ U of Toronto Zoology
condemned to reinvent it, poorly.    | {allegra,ihnp4,decvax,utai}!utzoo!henry

In article <26797@linus.UUCP> bs@linus.UUCP (Robert D. Silverman) writes:
-In article <7440@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
-:In article <977@thumper.bellcore.com> karn@thumper.bellcore.com (Phil R. Karn) writes:
-:>I wonder what implications this might have for cryptography?
-:Probably just as many as a proof of the Riemann hypothesis.
-A proof of the RH would give important cryptographic results.
-It would mean a fast, deterministic Polynomial Time prime proving algorithm.

Something is wrong with this reasoning, Bob.  Since practically everyone
believes the RH is true, why not assume it is and produce the Polynomial-
Time algorithm you mention.  What advantage would a formal proof of RH
(that perhaps few could understand anyway) bring to that effort?

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:
:-In article <7440@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
:-:In article <977@thumper.bellcore.com> karn@thumper.bellcore.com (Phil R. Karn) writes:
:-:>I wonder what implications this might have for cryptography?
 
:-:Probably just as many as a proof of the Riemann hypothesis.
 
:-A proof of the RH would give important cryptographic results.
:-It would mean a fast, deterministic Polynomial Time prime proving algorithm.
:
 
:Something is wrong with this reasoning, Bob.  Since practically everyone
:believes the RH is true, why not assume it is and produce the Polynomial-
:Time algorithm you mention.  What advantage would a formal proof of RH
:(that perhaps few could understand anyway) bring to that effort?



Something is wrong with what reasoning? I said that proof of the RH yields
a fast deterministic algorithm for prime proofs. By your logic we should assume
that if most people believe a theorem is true we should just accept it even
if a proof is lacking. Mathematics doesn't work that way.

 
I think you are being deliberately obtuse and pedantic. What has BELIEF
in the RH got to do with primality PROOF? We have fast probabalistic 
tests now. RH makes those tests into proofs.
 
 
Bob Silverman

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.

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?

 
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

In article <26822@linus.UUCP> bs@linus.UUCP (Robert D. Silverman) writes:
>By your logic we should assume
>that if most people believe a theorem is true we should just accept it even
>if a proof is lacking. Mathematics doesn't work that way.
> 
>I think you are being deliberately obtuse and pedantic. What has BELIEF
>in the RH got to do with primality PROOF? We have fast probabalistic 
>tests now. RH makes those tests into proofs.


You know, that's my logic too, Bob.  A mathematical (even if we have to call
it mathematical) property is useful whether or not it is proven.  Supposing
I find some regularity in a mathematical system by induction (but in a case
where mathematical induction is not adequete proof) and decide to write a
program to do analysis based on that regularity.  Either the program will
succeed and be useful to me or it will fail, disproving my hypothesis.  The
point is that I win either way.

					Keith
					ln63wgq%sdemlab@sdcsvax

In article <1009@sdcc13.ucsd.EDU> ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer) writes:
>You know, that's my logic too, Bob.  A mathematical (even if we have to call
>it mathematical) property is useful whether or not it is proven.  Supposing
>I find some regularity in a mathematical system by induction (but in a case
>where mathematical induction is not adequate proof) and decide to write a
>program to do analysis based on that regularity.  Either the program will
>succeed and be useful to me or it will fail, disproving my hypothesis.  The
>point is that I win either way.
>
>					Keith
>					ln63wgq%sdemlab@sdcsvax


I think you're missing something here. Your program NEVER will succeed, 
because there is an infinity of cases. It can only fail. If you want to
prove something, you need a proof, not a 'convincing' number of tries.
Of course your program can fail, unproving your assumption (so you only
win if you make weird assumptions! :-))

If you want to be sure, PROVE. You can assume things, but this will only
partially sovle your problems. If I use the Riemann Hypothesis in an 
article, I will clearly say that I use an unproven hypothesis.
	-- Jurjen
-- 
  -- Jurjen N.E. Bos (jurjen@cwi.nl)

 >  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.

> Your program NEVER will succeed because there are an infinite number of
> cases, it can only fail.

Ahh!  This points up the exact problem we're having in communicating here.
I'm not a mathematician, I don't write papers, and I feel no urge to know
for sure whether my hypothetical regularity is universal or not.  My point
is that, although a hypothesis may or may not be true, if it's a little bit
useful then it's worth implementing in an algorithm.  So, perhaps one day
the algorithm flails.  I can take note of that and know that the hypothesis
is incorrect, or at least needs refinement.  By "winning either way," I don't
mean proving the hypothesis, I mean getting some value out of using it to
develop algorithms that may be valid in the specific cases I'm interested in,
though they may bomb if taken generally. :-)

There seem to be a lot of mathematically-minded people here, so I'll ask
some questions that have been on my mind.  If a general result of
quantificantion theory is that set theory and number theory contain contra-
dictions (ie. It's possible to construct a proof for a statement and one for
its negation for certain statements), how can we expect to get meaningful
results from these things?  Essentially what this says is that number theory
and set theory are not valid, so that proofs in number and set theory may
not be true.  To some extent, this problem extends into other mathematical
fields.  On one hand I want to know how we can put so much emphasis on proof,
if it is known that our postulates are contradictory (and therefore not
representative of reality either), and on the other hand I'm curious as to
why, assuming that our math is formal enough to be used mechanically, one of
you sharp mathematicians out there don't write a proof machine to construct
and prove every theorem in every field of mathematics.  Doubtless there are
a lot of them, but I'd think you could narrow the range of output with some
reasonable formal criterion like the number of mathematical "words" in the
theorem and the number of postulates and logical inferences used to construct
the shortest possible proof.  Perhaps this would take a lot of cpu time, but
it might well be worth tying up someone's cray for ever to learn more about
the formalistic "coding" of reality.  Is there a reason this isn't possible?

						Keith Messer
						messer%emlab@sdcsvax.ucsd.edu

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

To clarify the discussion about proving and assuming hypotheses:
It is NOT true that there are theorems in any system that can be proven
together with their negation.
It IS true, however, that there are statements that are true, and cannot
be proven, and their negation (which is false) of course cannot be proven
also. This is called "Godel's Theorem". (with an umlaut on the o)
(See, for example, "Godel, Escher, Bach" by Hofstadter).

-- 
  -- Jurjen N.E. Bos (jurjen@cwi.nl)

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

In article <11288@duke.cs.duke.edu> srt@duke.UUCP (Stephen R. Tate) writes:
>This also has practical considerations -- what if there are times
>when the algorithm will not stop?

What if it was proven theoretically that it would eventually stop but
in a particulare case it's still taking too long?  In practice there
will be some watchdog timer used to abort an operation that takes too
long.

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

That was my original point.  A proof of RH wouldn't seem to have made
any practical difference.

In article <1009@sdcc13.ucsd.EDU> ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer) writes:
>Supposing
>I find some regularity in a mathematical system by induction (but in a case
>where mathematical induction is not adequete proof) and decide to write a
>program to do analysis based on that regularity.  Either the program will
>succeed and be useful to me or it will fail, disproving my hypothesis.  The
>point is that I win either way.

Unless your program fails without you realizing it, in which case you may
lose *big*.  I hope you warn people about any hidden conjectures your programs
rely on, before they have the opportunity to bet their money, their data, or
their lives that your hypothesis won't fail at the most inopportune moment...

Factoring is *probably* hard, but crypto aficionados still take pains to
characterize their algorithms as "secure if factoring is hard", rather
than "secure".  Otherwise, a lot of people might be SOL if factoring
*does* turn out to be easier than we thought...  The same pains should
be taken with ALL other unverified conjuctures, like RH, FLT(?), or
P <> NP.  

-- Jim Lewis
   U.C. Berkeley

In article <27072@linus.UUCP> bs@gauss.UUCP (Robert D. Silverman) writes:
>Your understanding of algorithms and proof of their correctness is somewhat
>limited I would say. 

Hey, no need to insult Tom Duff, who is an extremely clever person.

I'm not sure why Bob seems to be so offended by this discussion,
which started with my remark to the effect that I didn't think a
proof of Fermat's lost theorem would have any more practical
consequences for cryptology than a proof of RH.  I still believe
that, even though RH does seem to be more relevant, but it isn't
worth getting nasty about.  I think there is a communication failure.