2009/11/15 William Stein <[email protected]> > > On Sat, Nov 14, 2009 at 4:31 PM, gerrob <[email protected]> wrote: > > > > I've uploaded a new code on google group. It is using remainder tree > > to speedup the sieving, and now it is sieving up to about log2(n)^2. > > It means a speedup by a factor of two for large "random" input (here > > random means that nextprime(n) isn't very close to n). For totally > > random inputs it is faster than the currently code from approximately > > 1300 bits numbers. > > Quick naive question -- is this command finding the next pseudoprime, > or is it really the next prime (provably correctly)? A time of 131 > seconds for finding the next prime (not pseudoprime) after 10^2000 > would I think be very, very impressive to me. > > William > > > > > Just two inputs, on my PC: (the input numbers are special, but neither > > of codes recognize/use this) > > > > N=10^2000 > > mpir's time=229 sec. > > my method's time=131 sec. > > diff=0,nextprime(N)-N=4561 > > > > N=10^4000 > > mpir's time=4551 sec. > > my method's time=2281 sec. > > diff=0,nextprime(N)-N=16483 > > > > > > > > > -- > William Stein > Associate Professor of Mathematics > University of Washington > http://wstein.org > > > > No, my code gives "only" a pseudoprime. But note that the gmp's nextprime function gives also a pseudoprime (the naming isn't perfect).
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en -~----------~----~----~----~------~----~------~--~---
