Trial-division interface

Torbjorn Granlund tg at gmplib.org
Thu May 27 17:44:49 CEST 2010


The first question we might ask is, should we support trial dividing by
arbitrarly large divisors, or should we allow it up to some arbitrary
limit?

An arbitrary limit could be a limb (which is of course different for
different machines), or some resonable limit beyond which nobody in his
right mind should ever use trial division.

Are there uses for trial dividing by a range of divisors starting not at
3, but at some larger bound?  I suppose it might be possible that some
algorithm first performs a little trial dividing, then does something
else ("is it a prime?") then resumes trial dividing.

A related problem turned up when Martin Boij last summer rewrite the
prime power code; he needed to find out the multiplicity of primes.  If
a number is of the form t*3^c for a large c, then one really do not want
to call a mpz_trialdiv to get one 3 factor per call.

-- 
Torbjörn


More information about the gmp-devel mailing list