# Frobenius Probable Prime Test

**Jason Moxham
**
j.l.moxham@maths.soton.ac.uk

*Tue, 13 May 2003 04:09:38 +0100*

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