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 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