There are approximately 2^2038 primes in the 2048-bit space (source, https://www.wolframalpha.com/input/?i=log2%282**2049%2Fln%282**2049%29+-+2**2047%2Fln%282**2047%29+%29 ). Even allowing that the first bit is 1, that makes 2^2037. Given that, the chance of p and q having a difference of 2, at all (never mind actually being twin primes) is probably equal to about 1 in 2^ 2035 (due to the birthday paradox). If my math is wrong, please let me know.
On Fri, May 22, 2015 at 1:34 PM, Daniel Kahn Gillmor <[email protected]> wrote: > On Fri 2015-05-22 12:49:22 -0400, [email protected] wrote: > > On 5/22/2015 at 12:03 PM, "Daniel Kahn Gillmor" <[email protected]> > wrote: > [ vedaal wrote: ] > >>> does GnuPG automatically reject twin primes ( p, p+2) , and > >>> Sophie-Germain primes (p, 2p+1) ? > > > >> Why should GnuPG reject these primes? Surely, it wouldn't want to > >> both elements of a pair like that (i.e. for RSA you don't want q = > >> p+2 because it's a trivial test to factor that composite), but is > >> there a reason to reject using a p that meets these categories with > >> some other, unrelated q? > > > > Sorry, I meant does GnuPG automatically reject the PAIR since they are > > trivial to factor. > > there's no risk that GnuPG will choose a Sophie-Germain prime with its > corresponding safe prime, because as Werner said, it chooses the size of > the primes (in bits) and then sets the highest bits to 1. Since the > sizes are the same, the S-G/safe pair isn't possible (the safe prime is > always 1 bit longer than the S-G prime). > > That leaves the twin prime case. I don't know whether GnuPG rejects > that selection, but the chance of stumbling into a twin prime pair > during random prime selection seems staggeringly low to me. > > --dkg > > _______________________________________________ > Gnupg-users mailing list > [email protected] > http://lists.gnupg.org/mailman/listinfo/gnupg-users > >
_______________________________________________ Gnupg-users mailing list [email protected] http://lists.gnupg.org/mailman/listinfo/gnupg-users
