Re: [PrimeNumbers] A new twist on a PRP test
- --- Marcel Martin <znz@...> wrote:
> Phil Carmody wrote (May 7th, 2002):Which seems to make it a strongly weak test, rather than a weakly
> >Let p=k.2^n+1 , k odd, n>2.
> >Form k^(2^i), for i=1..n-1, or until the result is -1.
> >If it's never -1, reject the candidate as composite.
> >Otherwise call the candidate an EP-probable prime (to distinguish
> >from all the other probable prime varieties).
> >How 'strong' is this as a PRP test? It has slightly ( lg(k) )
> >steps than a traditional PRP or SPRP test. Is there any way of
> >evaluating its strength, even approximately, apart apart from just
> >running millions of tests?
> Weakly strong. According to this test 97 is a composite number.
> Since 97 = 3 * 2^5 + 1,
> 3^(2^1) = 3^2 mod 97 = 9
> 3^(2^2) = 3^4 mod 97 = 81
> 3^(2^3) = 3^8 mod 97 = 62
> 3^(2^4) = 3^16 mod 97 = 61
> Which power gives -1?
strong test! :-)
I shall go and inform Mr. E.P. of your discovery.
> If I remember rightly, up to now, nobody pointed out the error toIndeed, thanks.
> list. That's done.
"One cannot delete the Web browser from KDE without
losing the ability to manage files on the user's own
hard disk." - Prof. Stuart E Madnick, MIT.
So called "expert" witness for Microsoft. 2002/05/02
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup