karn@thumper.bellcore.com (Phil R. Karn) (03/10/88)
An article on the AP wire reports that Japanese mathematician Yoichi Miyaoka at the Max Planck Institute in Bonn has apparently proven Fermat's Last Theorem. [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]. I wonder what implications this might have for cryptography? Phil
gwyn@brl-smoke.ARPA (Doug Gwyn ) (03/12/88)
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.
bs@linus.UUCP (Robert D. Silverman) (03/13/88)
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
henry@utzoo.uucp (Henry Spencer) (03/13/88)
> [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
gwyn@brl-smoke.ARPA (Doug Gwyn ) (03/13/88)
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?
bs@linus.UUCP (Robert D. Silverman) (03/13/88)
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
gwyn@brl-smoke.ARPA (Doug Gwyn ) (03/14/88)
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.
srt@duke.cs.duke.edu (Stephen R. Tate) (03/15/88)
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?
bs@linus.UUCP (Robert D. Silverman) (03/15/88)
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
ln63wgq@sdcc13.ucsd.EDU (Keith Messer) (03/15/88)
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
jurjen@cwi.nl (Jurjen N.E. Bos) (03/15/88)
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)
td@alice.UUCP (03/15/88)
> 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.
ln63wgq@sdcc13.ucsd.EDU (Keith Messer) (03/16/88)
> 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
bs@linus.UUCP (Robert D. Silverman) (03/16/88)
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
bs@linus.UUCP (Robert D. Silverman) (03/16/88)
In article <1010@sdcc13.ucsd.EDU: ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer) writes:
:
:> 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
If you see my previous aritcle the problem is that you would never KNOW
if it failed. It might report a composite number as being prime and you
would have no way of knowing otherwise. (unless you used a different
algorithm).
: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. :-)
You have no way of verifying whether the algorithm is correct for your
'specific cases I'm interested in'.
:
: 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
Number theory does NOT contain contradictions. CERTAIN set theories can be
constructed which are formally inconsistent but that is irrelevent to the
discussion about number theory.
: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
see above. Go take a formal course in logic and Goedel's theorem. You
might learn something.
: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
I suggest you look at what is known as the halting problem.
Bob Silvermanln63wgq@sdcc13.ucsd.EDU (Keith Messer) (03/17/88)
In article <27073@linus.UUCP> bs@gauss.UUCP (Robert D. Silverman) writes: [In my message, I write:] >: 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 > >Number theory does NOT contain contradictions. CERTAIN set theories can be >constructed which are formally inconsistent [...] Ok, remember that I'm >not< claiming to be knowledgable about these things, but I >am< trying to learn about them, so here is my source, and a quote from a book I'm reading on the subject: "...the sharp question of completeness has led to sharp answers. Godel's famous theorem establishes the conclusion that the usual formal systems for number theory, analysis and set theory are incomplete unless they contain contradictions. Moreover, given any consistent formal system for one of these theories, a sentence of the system can be constructed which is demonstrably indemonstrable." -- Wang Hao, _A_Survey_of_Mathematical_Logic_, Science Press Now, while I realize that Wang Hao may have been wrong when he wrote that in his book, you and he >are< in direct contradiction with one another if number theory is complete. However, I don't get off on talking about the completeness and validity of mathematical systems. Applied cryptology is more interesting, and I did wrong to post a math question on the crypto board in the first place, but I had hoped you might have some light to shed on the subject.. Why do you keep ragging on people? But, to change the subject, what is your favorite one-way transformation.. I mean the one you feel most secure about being one-way? And what are your favorite books in areas of math that are useful in cryptology/cryptoanalysis? Keith
srt@duke.cs.duke.edu (Stephen R. Tate) (03/17/88)
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
gwyn@brl-smoke.ARPA (Doug Gwyn ) (03/19/88)
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.
jwl@ernie.Berkeley.EDU (James Wilbur Lewis) (03/20/88)
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
gwyn@brl-smoke.ARPA (Doug Gwyn ) (03/20/88)
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.
csrrc@daisy.warwick.ac.uk (R M Howarth) (03/28/88)
In article <7521@boring.cwi.nl> jurjen@cwi.nl (Jurjen N.E. Bos) writes: >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. > >I think you're missing something here. Your program NEVER will succeed, >because there is an infinity of cases. It can only fail. I think you're missing something here. Keith is talking about a result being USEFUL not about PROVING it. > If you want to >prove something, you need a proof, not a 'convincing' number of tries. Sure, but we don't, do we? After all, we're computer scientists, not mathematicians :-) Bob and Jurjen are of course right that a proper mathmatical proof is intellectually satisfying and essential to make a hypothesis respectable no matter how many examples in favour of it you find. But that isn't what Steven Tate and Keith were talking about. If I am 99.99% confident in the validity of the Rieman hypothesis and write a program which depends on it to work, then I can be *reasonably* confident in my program even without a "proof". Hell, even if the hypothesis were proven there would still be a > 0.01% (to say the least!) chance of a bug in my program, so in a practical sense the proof of the hypothesis does nothing to increase confidence in my program. OK, so next I try to prove my program is correct, but then where's the proof that my "proof" is correct ... ? Humans are fallible beings, so we have to accept the fact that in principle any hypothesis/program/aeroplane engine etc may fail in some situation. While this may not be very satisfying, it doesn't stop us making use of the thing concerned. We learn to live with this possibity of failure (though of course this doesn't prevent us from trying to keep the probability of failure down as low as possible). -Rolf P.S. Apologies if this article is less than topical for most people. Our news connection is abysmally slow.
srt@duke.cs.duke.edu (Stephen R. Tate) (03/31/88)
In article <507@sol.warwick.ac.uk> rolf@flame.warwick.ac.uk writes: >Bob and Jurjen are of course right that a proper mathmatical proof is >intellectually satisfying and essential to make a hypothesis respectable >no matter how many examples in favour of it you find. But that isn't what >Steven Tate and Keith were talking about. If I am 99.99% confident in >the validity of the Rieman hypothesis and write a program which depends >on it to work, then I can be *reasonably* confident in my program even >without a "proof". Well.... that's *sort of* what I said, anyway. It's true that unproven hypotheses can provide useful results, just be careful how you use them. I seemed to be lumped in with people who underestimate the power of proofs above -- this just isn't true. Basically, in my work, if I can't prove something, it's just as bad as if it wasn't true. *But*, that doesn't contradict what I said about useful programs being possible -- it's just that I generally don't write programs. Lastly, I hope that if you're doing work using unproven hypotheses (even something as plausable as the RH) that you're not working on something critical... I can just see someone working on this SDI stuff saying "Well, it looks like it works", and then when the real test comes that one case they didn't consider fails. -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt@cs.duke.edu