Loading ...
Sorry, an error occurred while loading the content.
 

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

Expand Messages
  • Phil Carmody
    ... 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.