Trial-division interface

Torbjorn Granlund tg at
Thu Apr 8 18:42:43 CEST 2010

nisse at (Niels Möller) writes:

  Paul Zimmermann <Paul.Zimmermann at> 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 mailing list