Overview Giac provides comprehensive polynomial factorization capabilities, including modular factorization, distinct degree factorization, and multivariate factorization using various algorithms.
Modular Factorization Distinct Degree Factorization (DDF) bool ddf ( const modpoly & q , const std :: vector < modpoly > & qmat , environment * env , std :: vector < facteur < modpoly > > & v );
Decomposes a square-free polynomial into factors grouped by degree. Uses the qmat (q-matrix) for efficient computation.
Square-free polynomial to factor modulo a prime
qmat
const std::vector<modpoly> &
Precomputed q-matrix for x^(p^i) mod q
Modular arithmetic environment
v
std::vector<facteur<modpoly>> &
Output: vector of (polynomial, degree) pairs
Q-Matrix Computation void qmatrix ( const modpoly & q , environment * env , std :: vector < modpoly > & v , int jstart = 0 );
Computes v[i] = x^(p*i) mod q for use in factorization algorithms. Essential for efficient DDF and Cantor-Zassenhaus.
modpoly q = { 1 , 0 , 1 , 1 }; // x^3 + x + 1 environment env; env . modulo = 5 ; env . moduloon = true ; std ::vector < modpoly > qmat; qmatrix (q, & env, qmat); std ::vector < facteur < modpoly >> factors; ddf (q, qmat, & env, factors);
Cantor-Zassenhaus Algorithm bool cantor_zassenhaus ( const modpoly & ddfactor , int i , const std :: vector < modpoly > & qmat , environment * env , std :: vector < modpoly > & v );
Splits a polynomial known to have factors of degree i into irreducible factors using random polynomial powering.
bool cantor_zassenhaus ( const std :: vector < facteur < modpoly > > & v_in , const std :: vector < modpoly > & qmat , environment * env , std :: vector < modpoly > & v );
Processes all factors from DDF output.
Polynomial with all irreducible factors of degree i
Output: vector of irreducible factors
Root Finding roots() bool roots ( const modpoly & q , environment * env , vecteur & v , std :: vector < modpoly > & w );
Finds modular roots and corresponding linear factors of a polynomial.
Output: vector of linear factors (x - root)
int do_linearfind ( const polynome & q , environment * env , polynome & qrem , vectpoly & v , vecteur & croots , int & i ); int linearfind ( const polynome & q , environment * env , polynome & qrem , vectpoly & v , int & ithprime );
Extracts linear factors from polynomials over Z or Z[i].
Hensel Lifting liftl() bool liftl ( environment * env , dense_POLY1 & q , gen & bound , std :: vector < modpoly > & v_in , vectpoly & v_out );
Lifts a factorization from Z/pZ to Z/p^kZ using Hensel’s lemma, where k is chosen large enough based on Mignotte bound.
Modified to contain p^k after lifting (modulo is updated)
Polynomial to factor over integers
Mignotte bound for coefficient size
Input: factorization modulo p
Output: lifted factorization modulo p^k
combine() void combine ( const dense_POLY1 & q , const std :: vector < modpoly > & v_in , environment * env , vectpoly & v_out , std :: vector < bool > & possible_degrees , int k = 1 );
Combines modular factors to find true factorization over Z. Tests combinations of k or more factors.
dense_POLY1 q = /* polynomial */ ; environment env; env . modulo = 101 ; env . moduloon = true ; std ::vector < modpoly > mod_factors; // ... compute modular factorization ... gen bound = mignotte_bound (q); vectpoly true_factors; liftl ( & env, q, bound, mod_factors, true_factors); std :: vector < bool > possible_deg ( q . size (), true ); vectpoly final_factors; combine (q, mod_factors, & env, final_factors, possible_deg);
Square-Free Factorization factorunivsqff() bool factorunivsqff ( const polynome & q , environment * env , vectpoly & v , int & ithprime , int debug , int modfactor_primes );
Factors a square-free univariate polynomial over Z using modular methods.
Index of prime to use (modified if prime is bad)
Debug level for verbose output
Bounds and Estimates Mignotte Bound gen mignotte_bound ( const dense_POLY1 & p ); gen mignotte_bound ( const polynome & p );
Computes the Mignotte bound: an upper bound on the absolute values of coefficients in any factor of p.
The Mignotte bound for a polynomial of degree n with coefficients bounded by M is: bound = 2^n * sqrt(n+1) * MThis determines how high to lift in Hensel’s lemma.
Factor Count Estimation int nfact ( const std :: vector < facteur < modpoly > > & v , bool * possible_degrees , int maxdeg );
Estimates the number of factors from DDF output and updates possible degree information.
Utility Functions intersect() void intersect ( std :: vector < bool >:: iterator tab , std :: vector < bool >:: iterator othertab , int size );
Computes intersection of two boolean arrays (for tracking possible factor degrees).
sigma() int sigma ( const std :: vector < bool > & deg );
Counts the number of possible degrees.
xtoxpowerp() void xtoxpowerp ( const modpoly & r , const std :: vector < modpoly > & v , environment * env , int qsize , modpoly & s );
Computes s(x) = r(x^p) mod q using precomputed q-matrix.
Irreducibility Testing gen _is_irreducible ( const gen & args , GIAC_CONTEXT );
Tests whether a polynomial is irreducible.
gen poly = /* polynomial expression */ ; gen result = _is_irreducible (poly, context); // Returns true if irreducible, false otherwise
Algorithm Overview
Modular Reduction
Choose a prime p and reduce the polynomial modulo p
Square-Free Factorization
Factor out repeated factors using GCD with derivative
Distinct Degree Factorization
Use DDF to group factors by degree
Equal Degree Factorization
Apply Cantor-Zassenhaus to split factors of same degree
Hensel Lifting
Lift factorization to Z/p^k with k large enough
Factor Combination
Try combinations to find true factors over Z
Prime Selection : Bad primes (where the polynomial has repeated factors modulo p) must be avoided. The algorithm automatically tries different primes if needed.
Q-Matrix Reuse : When factoring multiple polynomials with the same modular reduction, reuse the q-matrix computation for better performance.
See Also
Polynomial API Core polynomial operations
Algebraic Extensions Work with algebraic number fields
