Quote:
|
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.