mpz_trial_div

Niels Möller nisse@lysator.liu.se
14 Nov 2002 20:49:48 +0100


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