Re: [PrimeNumbers] Titanix 2.0.5 Beta
- 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 thisYour 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.