A Multi-level Blocking Distinct-degree Factorization Algorithm
230. R. P. Brent and P. Zimmermann,
A multi-level blocking distinct-degree factorization algorithm,
in Finite Fields and Applications (edited by Gary L. Mullen,
Daniel Panario and Igor E. Shparlinski),
Contemporary Mathematics, Vol. 461, 2008, 47-58.
Presented at the Eighth International Conference on
Finite Fields and
Melbourne, 9-13 July 2007.
Also INRIA Tech. Report
Oct. 2007, 16 pp.
We give a new algorithm for performing the distinct-degree factorization of
a polynomial P(x) over GF(2), using a multi-level
blocking strategy. The coarsest level of blocking replaces GCD computations
by multiplications, as suggested by Pollard (1975), von zur Gathen and Shoup
(1992), and others.
The novelty of our approach is that
a finer level of blocking replaces multiplications by squarings,
which speeds up the computation
in GF(2)[x]/P(x) of certain interval polynomials
when P(x) is sparse.
As an application we give a fast
algorithm to search for all irreducible trinomials
xr + xs + 1 of degree
r over GF(2), while producing a certificate that can be checked
in less time than the full search.
Naive algorithms cost O(r2) per trinomial,
thus O(r3) to search
over all trinomials of given degree r.
Under a plausible assumption about the
distribution of factors of trinomials, the new algorithm has
complexity O(r2 (log
for the search over all trinomials of degree r.
Our implementation achieves a speedup of greater than a factor
of 560 over the naive algorithm
in the case r = 24036583 (a Mersenne exponent).
Using our program, we have found two new primitive trinomials
of record degree 24036583 over GF(2) (the
previous record degree was
6972593). The two new primitive trinomials of degree 24036583 are
x24036583 + x8412642 + 1
x24036583 + x8785528 + 1.
For more recent results, see
For earlier, related results see
For software, see the gf2x
Go to next publication
Return to Richard Brent's index page