Trial-division interface

Niels Möller nisse at lysator.liu.se
Thu Apr 8 17:49:02 CEST 2010


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).

I don't quite understand the comments in the introduction of Sec. 2 (top
of page 6) about strategies for different sizes of the prime base, and
about sieving and "re-sieving". Maybe I'll understand if I read the
first pages of the report more carefully. (I'm not so familiar with the
NFS; I've skimmed the description in Cohen's book a few times but
without understanding it very well).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.


More information about the gmp-devel mailing list