14287Re: Modification of PFGW
- Dec 29, 2003Hi all,
I agree with you that for huge N, computing b^((N-1)/2)%N instead of
b^(N-1)%N result in a negligible time gain.
But what if you consider the accuracy of the test itself rather than
the time it takes : why just doing a basic fermat prp test ?
Maybe I'm missing something but I believed that a strong probable
prime test (rabin-miller's prp test) was more accurate than the
simple fermat's test (and not much difficult to implement). Am I
--- In email@example.com, mikeoakes2@a... wrote:
> In a message dated 23/12/03 22:00:27 GMT Standard Time,
> > I've been asking of Chris Nash ( I presume that he is very busy)
> > PFGW to check for Carol/Kynea numbers for a while now....Can
> > PFGW to do b^((N-1)/2)%N rather than b^(N-1)%N? There is even a
faster way (I
> > think) I can let it calculate b^((N-1)/2)%N (with a basic for
> You do realize, do you, that for N = 2^1000000-1 (for example), "to
> b^((N-1)/2)%N rather than b^(N-1)%N" takes 999999 rather than
1000000 FFTs; in other
> words, there is a negligible difference in execution time.
> PFGW is already a highly optimized and efficient program; so if you
> simple ideas involving "a basic for loop" are going to make it
faster, you are
> probably mistaken.
> The proper forum for this discussion is really the primeform group,
> implementation issues, openpfgw.
> -Mike Oakes
> [Non-text portions of this message have been removed]
- << Previous post in topic Next post in topic >>