Trial-division interface

Paul Zimmermann Paul.Zimmermann at
Thu Apr 8 10:53:29 CEST 2010

> When n is large enough to live in main memory, repeated use of mod_1_4
> should be avoided, and instead one should accumulate a large number of
> primes into a product P, for which gcd(n,P) is computed.  There is
> nothing asymptotically clever about this, just locality issues.

one problem with that approach (that I've tried) is that if one needs to
split the individual primes afterwards, it will add another cost. Thus
maybe one needs two functions: one which only removes the small primes,
and one that also splits the product of small primes.

By the way, Alexander Kruppa has written quite efficient trial division code
in CADO-NFS. The algorithm is described in,
section 2.

Paul Zimmermann

More information about the gmp-devel mailing list