Trial-division interface

[Paul Zimmermann]

       Niels,

> From: nisse at lysator.liu.se (Niels =?iso-8859-1?Q?M=F6ller?=)
> Date: Thu, 08 Apr 2010 11:56:06 +0200
> 
> > 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.

yes asymptotically this seems to be the best approach. However in the quadratic
range the gcd's will be costly, and maybe dividing out by smaller ppp's might
be faster. It also depends on the probability of N having small primes. For
few small primes you will only visit a few nodes of the product tree,
but for many small primes you will visit all the tree.

Paul