Trial-division interface

[Torbjorn Granlund]

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
  > hal.inria.fr/inria-00419094/en/
  
  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
time!

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.

-- 
Torbjörn