# gmp prime testing

**Jason Moxham
**
J.L.Moxham@maths.soton.ac.uk

*Wed, 6 Nov 2002 20:59:06 +0000*

On Wednesday 06 Nov 2002 5:01 pm, Niels M=F6ller wrote:
>* Torbjorn Granlund <tege@swox.com> writes:
*>* > > > ul=09mpz_trial_div(mpz_srcptr N , ul start , ul stop)
*>* > >
*>* > > Sounds fair to me, if Torbjorn likes it.
*>* >
*>* > Might make sense. What is it supposed to return?
*>* > Any factor, or 1 (or 0?) if no factor is found.
*>*
*>* If any reasonable implementation will compute a factor, I'd say return
*>* that factor or 0 if none was found. I think the trivial factors, i.e.
*>* 1 and N, should never be returned.
*>*
*>* If it's easy to make some additional guarantees (say, that if ul =3D=3D=
* 2,
>* then the returned factor will be a multiple of the smallest prime
*>* factor) then that would be nice too, but I don't know if a
*>* smallest-primefactor-of function is really useful.
*>*
*>* /Niels
*
The users of GMP should have a say , so this is going to gmp-discuss
I proposed the following user visible function
unsigned long mpz_trial_div(mpz_srcptr N , unsigned long start , unsigned=
long=20
stop)
Precondition is that N has no divisors less than start (excude 1)
mpz_trial_div returns the smallest prime divisor of N that is greater tha=
n or=20
equal to start and less than or equal to stop.If there does not exist a=20
divisor in this range then 0 is returned.
"Returning the divisors in size order" make this function much easier to =
use =20
than if the divisors were returned out of order. The improvement in speed=
you=20
get from returning the divisors out of order is not a lot (perhaps <5%). =
The=20
precondition is also not a great restriction , and it enables the functio=
n to=20
guarentee primality.
I already have a effiecent implementation of this , and also a possible=20
unsigned long ui_trial_div(unsigned long N , unsigned long start , unsign=
ed=20
long stop)
Note : In the definition above , and in my implementation , if N <stop^2 =
or=20
N<stop then the "obvious" optimizations apply . So N can be returned if i=
f=20
fits the exact definition above.
jason