View Single Post
Old 2006-07-28, 04:48   #29
Citrix's Avatar
Jun 2003

158810 Posts

Originally Posted by geoff
Thanks for the links, I will have a look at this sometime. I have a feeling the mathematics behind it is more difficult than that behind baby-steps-giant-steps though, it might take me a while.

In srsieve version 0.3.14 I have made the code recognise numbers of the form A^(2^y)+B^(2^y) as generalised Fermats, and there is a bug fix to properly handle cases where the base is a square.

The alogrithm is the same as baby-steps-giant-steps algorithm only done in groups of factors of p-1, than based on sqrt of the range of n's.

so if p-1=2*a*b

then running time is sqrt(a)+sqrt(2)+sqrt(b) than sqrt(nmax-nmin)

Let me know if you have any questions.
Citrix is offline   Reply With Quote