Article View: alt.security.pgp
Article #6Re: Prime generation, a possible weakness in PGP?
From: Richard Pinch
Date: Thu, 08 Oct 1992 09:15
Date: Thu, 08 Oct 1992 09:15
18 lines
1339 bytes
1339 bytes
In article <WARLORD.92Oct8004937@m66-080-20.mit.edu>, warlord@MIT.EDU (Derek Atkins) writes: > > [...] > >In all the numbers less than 10^12 (or something like that), >the Fermat test using b=2 will fail (i.e., give a false positive >reading) for only 15000 numbers. Thats 15000 out of 10^12! Thats >like 1 in 10^8, which are worse odds than you winning the lottery! > In fact there are 101629 Fermat base 2 pseudoprimes up to 10^12, and 37607912018 primes. The chance of getting a composite is thus 101629 / (37607912018 + 101629), which is about 2.7 in 10^6. There are only 22407 strong (Miller/Rabin) pseudoprimes base 2, which improves your chances to about 0.6 in 10^6. Richard Pinch, Dept of Pure Mathematics, University of Cambridge
Technical Details
Message-ID:
<1992Oct8.091540.28943@infodev.cam.ac.uk>Path:
arc1-ca.pugleaf.net!sparky!uunet!mcsun!uknet!pavo.csi.cam.ac.uk!emu.pmms.cam.ac.uk!rgepReferences:
<ARI.HUTTUNEN.92Sep27174550@laphroaig.cs.hut.fi> <WARLORD.92Oct8004937@m66-080-20.mit.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!mcsun!uknet!pavo.csi.cam.ac.uk!emu.pmms.cam.ac.uk!rgep From: rgep@emu.pmms.cam.ac.uk (Richard Pinch) Newsgroups: alt.security.pgp,sci.crypt Subject: Re: Prime generation, a possible weakness in PGP? Message-ID: <1992Oct8.091540.28943@infodev.cam.ac.uk> Date: 8 Oct 92 09:15:40 GMT References: <ARI.HUTTUNEN.92Sep27174550@laphroaig.cs.hut.fi> <WARLORD.92Oct8004937@m66-080-20.mit.edu> Sender: news@infodev.cam.ac.uk (USENET news) Distribution: alt Organization: DPMMS University of Cambridge Lines: 18 Nntp-Posting-Host: emu.pmms.cam.ac.uk