AngouriMath

Symbolics for .NET


Table of contents

AngouriMath

Navigation
Home Quick start Wiki Almanac Research What's new Try Use Angouri.org GitHub Report a bug Donate Contacts

PrimeFieldFactorization

← Back to list of classes

Description

Summary

Factorisation of a monic square-free polynomial over the prime field F_p into
monic irreducibles, by Berlekamp's algorithm.

Remarks

The algorithm rests on one observation. Raising to the p-th power is a field
automorphism fixing F_p pointwise, so on the quotient ring F_p[x]/(f) it is a linear map, and the polynomials it fixes — the Berlekamp subalgebra{ v : v^p = v mod f } — form a vector space. By the Chinese remainder theorem
F_p[x]/(f) is the product of the fields F_p[x]/(f_i) over the
irreducible factors of f, and in each of those the fixed elements are exactly
the constants. So the subalgebra is a product of r copies of F_p, its
dimension is r, and that dimension is the number of irreducible
factors — which is what gives the loop below an exact termination test rather than a
heuristic one. Knuth, TAOCP vol. 2, §4.6.2, algorithm B; von zur Gathen and
Gerhard, Modern Computer Algebra, §14.8.
 Given a v in that subalgebra, v^p - v = prod_{s in F_p} (v - s) vanishes modulo f, and the factors on the right are pairwise coprime, so
f = prod_s gcd(f, v - s). A v that is not constant takes different
values in different components and therefore separates them; running over a basis of
the subalgebra separates all of them.
 Berlekamp rather than Cantor–Zassenhaus, and the reason is not speed — for a large
modulus Cantor–Zassenhaus wins, because it replaces the O(p) sweep over
s with a random probe. It is that Cantor–Zassenhaus is randomised, and design
principle 3 of
#746 requires
the same input to give the same answer on every platform and in every thread count.
Berlekamp is deterministic by construction: the matrix, its null space and the sweep
over s are all fixed by the input.
 The price is that the sweep costs O(p n^3) field operations in the worst case,
linear in the modulus, so this is only sensible for a small one — hence
MaxPrime. That is not a restriction in practice, because the caller
chooses the modulus: factoring over the integers means picking a prime at which the
polynomial stays square-free and lifting the result, and there is no reason for that
prime to be large.

Members

























Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4378 pages online