--- 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