Trial-division interface

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

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

The applications I have seen are related to prime generation. There an
arbitrary limit (say, 10000 smallest primes, or all primes that fit in
16 or 20 bits or so) would be good enough. The limit should be exported
in some way, so callers know what to expect. I'm fairly confident that a
smoothness bound of 2^20 is overkill.

For next_prime-style sieving, one would also want a way to iterate over
the primes in the list (and any associated precomputed inverses and the
like), and a function to compute x mod p_k for a given x and all the
primes p_k in the list (this can use the same tables as mpn_trial_div,
and in addition I think it will need the prime inverses for truncating
division).

Factoring algorithms may have very different requirements, I don't know.

> Are there uses for trial dividing by a range of divisors starting not at
> 3, but at some larger bound?

One trivial use: Say you want to divide by a large number of primes, and
update some progress bar for every 200 primes tried.

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

In this case, I think one should use something like mpn_trialdiv to get
the prime factors, and something else for dividing them out. I imagine
one could have some heuristics similar to binary search for the
multiplicity. E.g., try dividing out 3, 3^2, 3^4, 3^8, ... until
division fails, and then divide out the remaining power by trying the
same sequence of powers in reverse order. I think that should be
reasonably efficient for both small and large multiplicities.

/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.