On 5/22/2015 at 12:03 PM, "Daniel Kahn Gillmor" <[email protected]> wrote:
>I think you're calculating the wrong thing. That same link points >out >that the number of primes less than x can be approximated as >pi(x) = x/(log(x)-1). > >Very rough approximation below, dealing with this stuff in integer >so i >don't have to worry about floating point precision: > >------------- >#!/usr/bin/python >import math >def pi(x): > return x//(int(math.log(x) - 1)) > >print(pi(2**2049) - pi(2**2047)) > >Produces: > >3414566770186655994404438379880237752289275853601443153843712876451 >7106455003913618433496010529759521130797881149503110281852350331307 >6748346315130154722343603670415899310676791001520948946303896102170 >4767238030738398330774862856393736234748500545533360423420463740160 >3112241209544524188755360669738591593193745235562705749858506233297 >2052480087122621997414717056433422819795492200612038244015831024661 >0014630770483358467188964179436800746042429708401186006929782110316 >9614694882157095281778056383498229906388753003349920901696154376284 >3548757751395862879269607910869512589725531458623570829193465282940 >49800053111 > >That's a lot of primes to choose from! :) ----- Ouch! ;-) my mistake (forgot it's exponential)! even using the n log(n) calculation, the interval is: 2^2049 [ 2049 log 2 ] - 2^2047 [2047 log 2] which is an infeasibly large interval to attack this way. ===== >> 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. Thanks, vedaal _______________________________________________ Gnupg-users mailing list [email protected] http://lists.gnupg.org/mailman/listinfo/gnupg-users
