gmp prime testing

Niels Möller
06 Nov 2002 18:01:02 +0100

Torbjorn Granlund <> writes:

>   > > ul	mpz_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 == 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.