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=
> 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.
which implies d=3D18.104.22.168=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 =
> 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
> 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=
>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=
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=
>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