Trial-division interface

Niels Möller nisse at lysator.liu.se
Thu Apr 8 11:56:06 CEST 2010


Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

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

How costly is it? Say we have computed ppp as a balanced multiplication
tree from the prime list, and at the top level we have ppp = A B with A
and B coprime. And we have computed g = gcd(N, ppp) > 0, and want to
split g in prime factors.

One, possibly naive, approach is to compute gcd(g, A). Then we can
either rule out the factors of A or B, or g splits, and we can then
continue using a known split of A or B or both. Somewhat like a binary
search over the prime list.

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