Jason Moxham <J.L.Moxham@maths.soton.ac.uk> writes:
> if mpz_trial_div can return 3*5 say , then it gets very complicated
> (and SLOW) , see my previous email on it , I recomend only returning
> prime factors in order .
I'm not sure what it is that will be slow. There are several ways to
use the small trial division function:
1. Testing if a number has a small factor. Here's 3*5 is a perfectly
good way of answering "yes".
2. Dividing out all small factors. For this, 3*5 is *also* a perfectly
good answer. Given n, do as follows:
A. Find a small factor of n, say d = 3*5.
B. Divide n = dq + r. While r == 0, set n = q and divide again.
C. Compute d = gcd(r,d) (= gcd(n,d)). (In our example, d will now
be 1, 3 or 5). If d > 1, go back to B.
D. Go back to A to find a new small factor. Here we need an
interface to the trial division function so that it can
continue without repeating the work done during the previous
call.
3. Enumerate all small prime factors.
Do as in B, and keep track of the factors divided out. Furthermore,
you need a factorization algorithm in order to split all d:s
occuring above into prime factors (note that you'll get some
splitting for free in step C).
I'm assuming d will always be bounded by 2^32 or some such. I don't
know how much work it is to factor numbers of that size. You may
get some help from knowing more about the order in which you get
factors from the trial division routine.
I'd say 2 is fairly trivial. 3 seems a little hairy to do efficiently.
I'd suggest writing some separate gmp function for that specific task,
and build it upon the trial division routine.
Regards,
/Niels