- On Sun, 29 Apr 2001 01:16:13 +0200

Marcel Martin wrote:

> Titanix 2.0.5 Beta is available.

<snip>

> What's up?

Is it known algorithm ? I want to know the new algorithm.

> ----------

> * New algorithm to split big polynomials (30% better, on average).

I had implmented Atkin-Morain ECPP. But it is slower than Titanix.

It takes heavy time to find a root of Hilbert class polynomial or

Weber polynomial mod N. I implemented factoring algoritm which is

explained in Cohen's book.

Satoshi TOMABECHI - On Wed, 02 May 2001 18:01:34 +0200

Marcel Martin wrote:

> way, i.e., GCD(P(X), (X+k)^((N-1)/2) - 1), it is better to use it this

Your explanation is enough to understand almost everything.

> way: GCD(P(X), (X+k)^((N-1)/D) - W^i) where D is a small divisor of

> N-1 and W is a D-th root of unity successively raised to the powers

> 0 <= i < D.

It is good idea to compute small power insted of large power.

It looks like factoring the polynomial X^n-1 into cyclotomic

polynomials over Z/NZ.

I thank you for your help and great soft.

Satoshi TOMABECHI