gmp prime testing

[Niels Möller]

Jason Moxham <J.L.Moxham@maths.soton.ac.uk> writes:

> I proposed the following user visible function
> 
> unsigned long mpz_trial_div(mpz_srcptr N , unsigned long start , unsigned long 
> stop)
> 
> Precondition is that N has no divisors less than start (excude 1)

That's too tough for my taste. It's fine if any guarantees on
returning the smallest prime divisor applies only if there are no
divosors smaller than start, but you should be able to call the
function with random start and end (start <= end), and get a well
defined answer back.

Exactly what you should get, I don't know, but it could be a number
between start and end that divides N, or a muber between start and end
that has some non-trivial factor comon with N. I don't know which is
most useful.

> "Returning the divisors in size order" make this function much easier to use  
> than if the divisors were returned out of order. The improvement in speed you 
> get from returning the divisors out of order is not a lot (perhaps <5%). The 
> precondition is also not a great restriction , and it enables the function to 
> guarentee primality.
> 
> I already have a effiecent implementation of this,

If I understood Torbjörn's concern, he want an implementation to be
able to do things like

  d = gcd(N, start * (start+1) * (start+2))

  if (d != 1)
    /* We have a factor. Done. */
    return something.

The problem is that d is not necessarily prime, so in order to return
the smallest factor you'd need to factorize d. It's small, so it's
probably not much work, but it is work that is totally unnecessary in
many cases, e.g. if all the caller really wants to know is if N is
prime or not.

Is it the facorization of d (or something similar) that give you the
5% slowdown?

That's why I proposed the compromise that the function, under certain
restrictions, should be specified to return a *multiple* of the
smallest factor.

Then callers that only want to know the existence of a factor get the
answer as quickly as possible, and callers that really want the
smallest factor can call some other function to get the smallest
factor of the returned value.

Finally, even my compromise may be too strict, as it rules out
implementations that compute gcd:s like

  d = gcd(N, start * (start + 1) * (end - 1) * end)

> Note : In the definition above , and in my implementation , if N <stop^2  or 
> N<stop then the "obvious" optimizations apply . So N can be returned if if 
> fits the exact definition above.

I'm thinking primarily of primetest applications (that's the only
things I've used trial division for, so far), and then it's quite
useless to return N. So I'd prefer that any "smallest prime factor of
N (in a given set)" is specified as returning either a *non-trivial*
factor of N, i.e. different from 1 and from N, or zero.

Are there any other applications where N is a useful answer?

/Niels