Jason Moxham
Fri, 8 Nov 2002 20:05:12 +0000

The name of fn mpz_trial_div implies a specific algorithm , which in futu=
could restrict the optimization possibilitys. Perhaps it should be called=
mpz_find_small_prime_factors ? or some such .

At present my code uses a prime table and/or a wheel to reduce the number=
possible divisors and groups these divisors together to increase the spee=
So it really is trial division.
I know of two ways to use gcd to increase speed (possibly ?)

After we group together a small number of our trial divisors , then we ta=
the gcd of this product (which is small) with N , and see if we get a=20
non-unit gcd. This would still be trial division.

We multiply together lots of trial divisors mod N  and then take GCD with=
( this may require sub-quadratic gcd) . This is really nothing like trial=
division. It could take the same time to discover that 23 is a divisor th=
it take to discover 100093 is a divisor.

I have yet to try either of these methods to see if they offer any=20

> I proposed the following user visible function
> unsigned long mpz_trial_div(mpz_srcptr N , unsigned long start , unsign=
> stop)
> Precondition is that N has no divisors less than start (excude 1)

I originally didn't have this precondition , but added it later to simpli=
things. Some reasons why I changed it are

1) With this precondition it is easy to guarentee that the returned divis=
are prime , without this precondition , any divisor found may be prime or=
composite and you would still have to run trial_div again to split the=20
returned divisor up further.

2) Without insisting that the returned divisors are prime you can not red=
the number of trial divisors by using a prime table.

let N=3D3.5.7.11.(2^31-1)
which implies d=3D3.5.7.11=3D1155
so our set of trial divisors must include non-primes

I couldn't think of any situation where this is in any way a serious prob=

Uses for mpz_trial_div

1)To prove that N has no factor less than 10000
2)To find easy factors of N , before more expensive tests like probable p=
tests or factoring
3) to factorize N

Why would anyone want to call mpz_trial_div (as proposed) with random sta=
and end ?

When I say the function is undefined , I mean that it returns garbage in =
resonable time , it does not crash or loop forever , or format you hard d=
:) . Technically the answer returned is well defined , just not useful.

consider mpz_divexact which will return garbage with random parameters.

All the uses to which I have put my mpz_trial_div , do not require the=20
divisors in order or to be prime or even what that divisor is. All I have=
needed to know (so far) is that , does a divisor exist or not .

The problem with these GCD methods is that smaller divisors are found no=20
quicker than larger ones . So prove existence or not they are great (assu=
they are faster) . But for eliminating common composites before a probabl=
prime test , they are much slower on average (because small divisors are =

Perhaps a seperate fn (internal?) for this type of existence of divisors =
mpz_exist_div(N,start,stop) ?

> I would argue that it should have a "unsigned long *expt" argument whic=
> returns the multiplicity of the factor returned.

Possible , although I think it is unneccessairy (as we have the mpz fn=20
mpz_remove_ui) , consider


to cover the multiplicity case

=46rom Paul
> Almost all the time when I want to find small factors (and by definitio=
>anything that fits into an unsigned long is small) I want all the factor=
s, I=20
>want them to be prime and I want them in order.  Having to write complic=
>control structures to find them all, test for primality and sort them in=
>order is a real PITA.   If I have to go to all that trouble, I may just =
>well code the trial division myself and avoid all the complexity.  It's=20
>likely to runs faster as well, just because I don't have to go through a=
>the post-processing.  The whole point of a library is to remove the need=
>rewrite frequently used code.

I couldn't agree more , What is PITA ?

I don't what to count the number of times I have writen various trial div=
routines , because I never had one that was general enough.

mpz_trial_div is also a very low-level fn , perfectly suited to gmp's man=
y cpu=20
optimizations (far more so than mpz_powm , say ) .

>> 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*
>My application has been almost exclusively integer factorization.  Given=
>integer, or class of integers, I first filter out all the small prime=20
>factors with trial division, then run a few thousand iterations of Polla=
>rho or squfof.  That flushes out everything up to 8 digits or so and I c=
>turn to ECM, QS or NFS as appropriate.  Trial division is a good candida=
>for a library and the other two possibly so.  QS and NFS are very likely=
>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 gi=
ves a=20
>simple test to see whether factorization is complete.

I hope this answers all your objections ?
If not let me know=20
It was/is the best way I could think of to do this generally