gmp prime testing

[Jason Moxham]

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