tg at gmplib.org
Thu Apr 8 18:42:43 CEST 2010
nisse at lysator.liu.se (Niels Möller) writes:
Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:
> I strongly suggest you read Section 2.1 from
After a quick look, the trial division algorithm there looks quite very
similar to Torbjörn's implementation mpn/generic/trialdiv.c (except that
I think mod_1s_4p allows larger divisors (up to B/2) and does the final
reduction from 2 to 1 limb differently).
GMP is a useful source where many algorithms are published for the first
Both the algorithm in 2.1 and 2.2 come from GMP, but the algorithm in
2.2 was suggested to me by Montgomery in an old mail, except that that
algortihm allows divisors <= B / \ell (without the sqrt) and return the
reminder, not just an indication abut if the remainder vanishes for p.
More information about the gmp-devel