Newsgroups: sci.math
From: pmontgom@cwi.nl (Peter L. Montgomery)
Subject: Re: Roots of a polynomial in GF(2^64). Algorithm needed.
Date: Fri, 3 Apr 1998 09:40:34 GMT

In article <35208648.777E@pacbell.net> mazurov@pacbell.net writes:
>What is the state-of-the-art algorithm for finding a root
>(if exists) of a polynomial with coefficients from 
>GF(2^n). I understand that when n is rather small an
>exhaustive search can be used. I'm interested in
>a fast algorithm for n = 64, 128, 256. The degree of
>the polynomial can be small ( <= 32 ).
>It all has something to do with decoding of Reed-Solomon
>codes, so it can be assumed that an m-degree polynomial to
>be factored has exactly m roots.

	Use the same methods as when factoring over GF(p) where p is prime.  
Let q = 2^n, and assume you have a univariate polynomial f in GF(q)[X].
Test for a nontrivial GCD(f(X), f'(X)) over GF(q), to 
remove repeated factors.  

        Now do distinct-degree factorization.
Test  GCD(f(X), X^q - X)  to get the product of all linear
factors of f(X).   While doing this computation,
you need only X^q (mod f(X)), even though q = 2^n is 2^64 or more;
this is n squarings mod f(X).  After removing linear factors
from  f(X), test GCD(f(X), X^(q^2) - X) to get the product of the
quadratic factors.  Continue to cubic factors, ..., until
you reach half the degree of f.

       It remains to factor polynomials g(X) where
g is known to split into distinct factors of degree d
If d = 1, also assume g(0) <> 0, since otherwise X is a factor.
If deg(g) = d, you are done.  To factor over GF(q)
where q is an odd prime, use Cantor-Zassenhaus, testing
GCD(h(X)^((q^d - 1)/2) - 1, g(X)) for random h(X).
In characteristic 2, (q^d - 1)/2 is not an integer,
so we need another technique.  Given an integer k < q, compute a trace
tr(X^k) = X^k + X^(qk) + X^(q^2 k) + ... + X^(q^(d-1) k) mod g(X).
The trace should be 0 or 1 -- 
testing GCD(g(X), tr(X^k)) should give a factor at least half of the time.

	In your case, where q is a power of 2^64,
you know q == 1 (mod 3).  You also know d = 1 (only linear factors)
You can use a variation of Cantor-Zassenhaus, with denominator 3 
rather than 2.  Let omega3 be a primitive cube root of unity in GF(q).
Given random alpha in GF(q), compute G(X) == (X + alpha)^((q - 1)/3) mod g(X).
Test g(X) for a non-trivial GCD with
G(X), G(X) - 1, G(X) - omega3, or G(X) - omega3^2.

>Any references?
>
	Knuth, Seminumerical Algorithms.
-- 
        Peter-Lawrence.Montgomery@cwi.nl    San Rafael, California

Q: Why will historians view El Nino as a dignitary?
A (backwards): .gnikaerb sdnuorg yreve ta tneserp neeb sah ti esuaceB
==============================================================================

From: bobs@rsa.com
Newsgroups: sci.math.symbolic
Subject: Polynomial Factorization
Date: Thu, 07 May 1998 18:54:07 GMT

In article <6iq983$fbe$1@agate.berkeley.edu>,
  fateman@peoplesparc.cs.berkeley.edu (Richard J. Fateman) wrote:
>
> In article <6iq754$ev1$1@nntp.ucs.ubc.ca>,
> Robert Israel <israel@math.ubc.ca> wrote:
>
> >Actually that should be Factor( x^(2^16)+x) mod 2.  Otherwise it first
> >tries to factor over the rationals, then takes the result mod 2.
>
> thanks, Factor is actually what I tried.
>
> >But even with Factor, the "object too large" error occurs (Release 5
> >on a Sun).  A sum or product is only allowed to have at most 2^16-1
> >terms or factors.  I'm pretty sure that in this case the error is caused
> >by an intermediate expression rather than the final result.  Maple does
> >successfully handle x^(2^15)+x mod 2: the result has 2192 factors.
>
> I find this reasonably fast x^(2^15)+x factorization "off the shelf"
> to be an impressive result.  The "too large" object may not be the
> ordinary expression, but the matrix used by the Berlekamp factoring
> algorithm, which appears to be  2^16 by 2^16  integers.  The problem
> with Macsyma was the underlying lisp's refusal to allocate such
> an array.
>

Yep.  Which is why they should be using Cantor-Zassenhaus for factorization
over finite fields.  For large degree (especially for sparse polynomials) it
is much faster and requires only O(degree log(degree)) space instead of
O(degree^2) space.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading