Frobenius Probable Prime Test

[Jason Moxham]

On Monday 12 May 2003 23:43, Kevin Ryde wrote:
> "Rick Lavoie" <coldfury@bu.edu> writes:
> > I noticed on the projects page it mentions the frobenius probable prime
> > test. If no-one is working on it, I can code it to be included with the
> > next release.
>
> Jason Moxham had proposed that, and was looking into it.  We're unsure
> at the moment quite where it would fit in.  It might be better to have
> various prime tests available individually instead of the current
> single entrypoint.  Some things like that could start off in the demos
> directory, if nothing else.

I wrote an implementation of the rqf test at the mpz level , and in pratice it 
was faster (than the strong probable prime test ) from about 2 to 4 limbs for 
a error of 1 in 10^10 . Note that in the paper the calculation of required 
lucas sequences can be easily improved . Also the common case when it's given 
a composite number can be also improved. You tweek the theorem so that any 
number that passes is also a strong probable prime and then do this part of 
the test first. This way you get a faster(x3) average time for most(nearly 
all) composite numbers , and the time for primes remains the same.

I kind of in the process of mpn'ifing it , but it will take some time because 
all the underlying functions need to mpn'ified 

I can send you the code if you want , but I warn you , It's not neat or 
commented , it should be correct though.... :)

Some(not a lot) of mpn'ified code is availible here

http://217.35.81.229/gmp/gmp_plus.html