Article View: sci.crypt
Article #1755Re: Cryptography and P=NP
From: Keith Ramsay
Date: Mon, 16 Nov 1992 06:43
Date: Mon, 16 Nov 1992 06:43
16 lines
1308 bytes
1308 bytes
In article <PHR.92Nov15203840@napa.telebit.com> phr@telebit.com (Paul Rubin) writes: >It is true that if P=NP then all cryptography everywhere (not just RSA) >is dead; but at this point I wouldn't take Swart's claims seriously >without seeing some consensus among complexity efforts that unlike >his previous attempts, his latest effort is free of bugs. Mathematics would also be placed in a surprising position by P=NP. P=NP implies that there is an algorithm which, given a theorem expressed formally in ZF, say, and a number n, either gives a formal proof of the theorem of length at most n, or shows that there is none, and which would take time bounded by some polynomial in n. It wouldn't *necessarily* put us all out of the math research business, but.... Keith Ramsay ramsay@unixg.ubc.ca
Technical Details
Message-ID:
<1e7fvdINN87s@iskut.ucs.ubc.ca>Path:
arc1-ca.pugleaf.net!sparky!uunet!van-bc!cs.ubc.ca!unixg.ubc.ca!ramsayReferences:
<1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!van-bc!cs.ubc.ca!unixg.ubc.ca!ramsay From: ramsay@math.ubc.ca (Keith Ramsay) Newsgroups: sci.crypt,sci.math,comp.theory Subject: Re: Cryptography and P=NP Date: 16 Nov 1992 06:43:57 GMT Organization: University of British Columbia, Vancouver, B.C., Canada Lines: 16 Distribution: inet Message-ID: <1e7fvdINN87s@iskut.ucs.ubc.ca> References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com> NNTP-Posting-Host: riemann.math.ubc.ca