Zassenhaus algorithm for factoring polynomials over the rationals

E827382

computational algebra algorithm polynomial factorization algorithm symbolic computation method

The Zassenhaus algorithm for factoring polynomials over the rationals is a classical computational method that reduces rational polynomial factorization to modular factorization and then recombines the results using lifting techniques.

Try in SPARQL Jump to: Surface forms Statements Referenced by

Observed surface forms (1)

Surface form	Occurrences
Zassenhaus algorithm in computer algebra	1

Statements (46)

Predicate	Object
instanceOf	computational algebra algorithm ⓘ polynomial factorization algorithm ⓘ symbolic computation method ⓘ
appliesTo	univariate polynomials over the rationals ⓘ
assumes	polynomial is squarefree over the rationals or has been squarefree decomposed ⓘ
basedOn	Hensel lifting NERFINISHED ⓘ modular factorization ⓘ
category	exact polynomial algorithms ⓘ
complexityDependsOn	degree of the polynomial ⓘ size of coefficients ⓘ
contrastWith	probabilistic factorization algorithms over finite fields ⓘ
domain	computational algebra ⓘ computer algebra systems ⓘ
goal	reduce rational polynomial factorization to modular factorization ⓘ
historicalPeriod	20th century ⓘ
improvesOn	naive integer factor search for polynomial factorization ⓘ
input	polynomial with rational coefficients ⓘ
involves	content-primitive factorization of integer polynomials ⓘ squarefree factorization as a preprocessing step ⓘ
mathematicalField	algebra ⓘ algorithmic algebra ⓘ number theory ⓘ
namedAfter	Hans Zassenhaus NERFINISHED ⓘ
output	factorization into irreducible polynomials over the rationals ⓘ
property	deterministic ⓘ exact arithmetic algorithm ⓘ
relatedTo	Berlekamp algorithm NERFINISHED ⓘ Cantor–Zassenhaus algorithm NERFINISHED ⓘ Kronecker factorization method NERFINISHED ⓘ
requires	bound on coefficients of factors for recombination step ⓘ
step	choose a suitable prime not dividing the content or discriminant ⓘ clear denominators to obtain an integer polynomial ⓘ factor the polynomial modulo the chosen prime ⓘ lift modular factors to higher powers of the prime using Hensel lifting ⓘ recombine lifted factors to obtain rational factors ⓘ
typicalImplementationLanguage	computer algebra system kernels such as Maple, Mathematica, or SageMath ⓘ
usedFor	computing algebraic number fields defined by polynomial equations ⓘ finding irreducible decomposition of rational polynomials ⓘ simplifying algebraic expressions ⓘ
usedIn	implementation of factor() in computer algebra systems ⓘ symbolic integration and simplification routines ⓘ
uses	Chinese remainder techniques ⓘ combinatorial search over lifted factors ⓘ reduction modulo a prime ⓘ
worksOver	field of rational numbers ⓘ ring of integers via content-primitive decomposition ⓘ

Referenced by (2)

Full triples — surface form annotated when it differs from this entity's canonical label.

Hans Zassenhaus → notableWork → Zassenhaus algorithm for factoring polynomials over the rationals ⓘ

Hans Zassenhaus → notableConcept → Zassenhaus algorithm for factoring polynomials over the rationals ⓘ

this entity surface form: Zassenhaus algorithm in computer algebra