Trial-division interface

[Niels Möller]

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.