## Re: [PrimeNumbers] A new twist on a PRP test

Expand Messages
• ... Which seems to make it a strongly weak test, rather than a weakly strong test! :-) I shall go and inform Mr. E.P. of your discovery. ... Indeed, thanks.
Message 1 of 3 , Jun 25, 2002
--- Marcel Martin <znz@...> wrote:
> Phil Carmody wrote (May 7th, 2002):
> >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
> it
> >from all the other probable prime varieties).
>
> >How 'strong' is this as a PRP test? It has slightly ( lg(k) )
> fewer
> >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?

Which seems to make it a strongly weak test, rather than a weakly
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 to
> the
> list. That's done.

Indeed, thanks.

Phil

=====
--
"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
http://fifaworldcup.yahoo.com
Your message has been successfully submitted and would be delivered to recipients shortly.