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

Re: PFGW

Expand Messages
  • andrew_j_walker
    ... On this theme, I remember seeing several years ago in Mathematics of Compuation (?) where someone had computed upper limits on random integers passing a
    Message 1 of 4 , May 30, 2006
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "Paul Underwood"
      <paulunderwood@...> wrote:
      >
      > --- In primenumbers@yahoogroups.com, "Paul Underwood"
      > <paulunderwood@> wrote:
      > >
      > > --- In primenumbers@yahoogroups.com, "Kermit Rose" <kermit@> wrote:
      > > >
      > > >
      > > >
      > > > How or where may I get the algorithm or source code for
      > > >
      > > > PFGW or proth prime number testing algorithms.
      > > >
      > > > I've written my own prime number testing subroutine, and do not know
      > > over
      > > > what range it is valid.
      > > >
      > > > My algorithm is :
      > > >
      > > > to test if z is prime,
      > > >
      > > > for B = 2 to 101
      > > >
      > > > c = mod(B^ [ ( z-1)/2 ] , z )
      > > >
      > > > if c = 0 return composite
      > > > if c = 1 continue loop
      > > > if c = -1 continue loop
      > > > else return composite
      > > >
      > > > next B
      > > >
      > > > return probably prime
      > > >
      > >
      > > The OpenPFGW source code is available here:
      > > http://groups.yahoo.com/group/primeform/
      > >
      > > Your algorithm looks a little bit like a "strong PRP" test. There are
      > > composite numbers that will pass your test.
      > >
      > > See:
      > > http://primes.utm.edu/glossary/page.php?sort=StrongPRP
      > >
      > > HTH
      > >
      >
      > Also see: http://primes.utm.edu/glossary/page.php?sort=Pseudoprime
      >
      > where it states: "Arnault found a 337 digit number which passed strong
      > PRP tests for each of the first 200 primes [Arnault95]."
      >

      On this theme, I remember seeing several years ago in Mathematics of
      Compuation (?) where someone had computed upper limits on random
      integers passing a certaing number of prp tests (probably was
      Miller-Rabin) for various bit sizes. The key point was that for
      general numbers this quickly becomes *much* smaller than the 1/4
      tests passed by some numbers. Does anyone know if these bounds have
      been improved or extended on in recent years?

      Andrew
    Your message has been successfully submitted and would be delivered to recipients shortly.