gmp prime testing

[Paul Leyland]

> From: Niels M=F6ller [mailto:nisse@lysator.liu.se]=20
> Jason Moxham <J.L.Moxham@maths.soton.ac.uk> writes:
>=20
> > I proposed the following user visible function
> >=20
> > unsigned long mpz_trial_div(mpz_srcptr N , unsigned long=20
> start , unsigned long=20
> > stop)
> >=20
> > Precondition is that N has no divisors less than start (excude 1)
>=20
> That's too tough for my taste. It's fine if any guarantees on

I concur: too restrictive.

> 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 <=3D end), and get a well
> defined answer back.

Agreed.

>=20
> 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.

I would say that it should return the smallest prime factor of N, if =
any, in the given range, and 0 otherwise.  Note that if N is prime, and =
start <=3D N <=3Dend it should return N.

I would argue that it should have a "unsigned long *expt" argument which =
returns the multiplicity of the factor returned.

> > "Returning the divisors in size order" make this function=20
> > much easier to use than if the divisors were returned out
> > of order. The=20

Strongly agree...

> > precondition is also not a great restriction , and it=20
> > enables the function to guarentee primality.

... mostly for this reason.

> That's why I proposed the compromise that the function, under certain
> restrictions, should be specified to return a *multiple* of the
> smallest factor.
>=20
> 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.

Almost all the time when I want to find small factors (and by =
definition, anything that fits into an unsigned long is small) I want =
all the factors, I want them to be prime and I want them in order.  =
Having to write complicated control structures to find them all, test =
for primality and sort them into order is a real PITA.   If I have to go =
to all that trouble, I may just as well code the trial division myself =
and avoid all the complexity.  It's likely to runs faster as well, just =
because I don't have to go through all the post-processing.  The whole =
point of a library is to remove the need to rewrite frequently used =
code.

> 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.

My application has been almost exclusively integer factorization.  Given =
an integer, or class of integers, I first filter out all the small prime =
factors with trial division, then run a few thousand iterations of =
Pollard rho or squfof.  That flushes out everything up to 8 digits or so =
and I can turn to ECM, QS or NFS as appropriate.  Trial division is a =
good candidate for a library and the other two possibly so.  QS and NFS =
are very likely not candidates.  ECM is borderline but I'd put it =
outside the border.

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

N, if prime, is useful in the factorization scenario given above.  It =
gives a simple test to see whether factorization is complete.


Paul