Article View: sci.crypt
Article #1043Re: pgp2.0 - what is an appropriate key length?
From: D. J. Bernstein
Date: Tue, 29 Sep 1992 00:06
Date: Tue, 29 Sep 1992 00:06
19 lines
1440 bytes
1440 bytes
In article <1992Sep27.202153.11858@colnet.cmhnet.org> res@colnet.cmhnet.org (Rob Stampfli) writes: > You are correct in that the "pseudo-primes" used in such systems have not > been proven to be true primes by an exhaustive, theroretically 100% accurate, > analysis. Any known algorithm that would accomplish this would require so > much computer time as to make it infeasible to run. No. For theoretical purposes, there exists an algorithm which tests p for primality in time log^5 p. If the algorithm says ``it's prime'' for a non-prime, then the generalized Riemann hypothesis is false. Actually that algorithm isn't too slow in practice, but for practical purposes what you really want to use is Morain's ECPP. ECPP gives you a _proof_ that your number is prime, no assumptions necessary. Theory doesn't guarantee that ECPP is polynomial-time, but that doesn't stop it from being very, very fast. ---Dan
Technical Details
Message-ID:
<29473.Sep2900.06.1392@virtualnews.nyu.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!cis.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!ucbvax!virtualnews.nyu.edu!brnstndReferences:
<Bv6Izu.Aoq@newcastle.ac.uk> <Bv7ID5.BHw@ibmpcug.co.uk> <1992Sep27.202153.11858@colnet.cmhnet.org>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!cis.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!ucbvax!virtualnews.nyu.edu!brnstnd From: brnstnd@nyu.edu (D. J. Bernstein) Newsgroups: sci.crypt,alt.security,alt.security.pgp Subject: Re: pgp2.0 - what is an appropriate key length? Message-ID: <29473.Sep2900.06.1392@virtualnews.nyu.edu> Date: 29 Sep 92 00:06:13 GMT References: <Bv6Izu.Aoq@newcastle.ac.uk> <Bv7ID5.BHw@ibmpcug.co.uk> <1992Sep27.202153.11858@colnet.cmhnet.org> Organization: IR Lines: 19