gmp prime testing
Paul Leyland
pleyland@microsoft.com
Fri, 8 Nov 2002 03:05:27 -0800
> 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