Factorization Functions

Polynomial factorization algorithms and utilities in Giac

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)

modfactor.h:52

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.

q · const modpoly &

Square-free polynomial to factor modulo a prime

qmat · const std::vector<modpoly> &

Precomputed q-matrix for x^(p^i) mod q

env · environment *

Modular arithmetic environment

v · std::vector<facteur<modpoly>> &

Output: vector of (polynomial, degree) pairs

Q-Matrix Computation

modfactor.h:42

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.

Example

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

modfactor.h:54-55

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.

modfactor.h:55

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.

ddfactor · const modpoly &

Polynomial with all irreducible factors of degree i

i · int

Degree of each factor

v · std::vector<modpoly> &

Output: vector of irreducible factors

Root Finding

roots()

modfactor.h:46-47

bool roots(const modpoly & q, environment * env, 
           vecteur & v, std::vector<modpoly> & w);

Finds modular roots and corresponding linear factors of a polynomial.

v · vecteur &

Output: vector of roots

w · std::vector<modpoly> &

Output: vector of linear factors (x - root)

Linear Factor Extraction

modfactor.h:48-50

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

modfactor.h:65

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.

env · environment *

Modified to contain p^k after lifting (modulo is updated)

q · dense_POLY1 &

Polynomial to factor over integers

bound · gen &

Mignotte bound for coefficient size

v_in · std::vector<modpoly> &

Input: factorization modulo p

v_out · vectpoly &

Output: lifted factorization modulo p^k

combine()

modfactor.h:68

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.

Hensel Lifting Example

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

modfactor.h:71

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.

ithprime · int &

Index of prime to use (modified if prime is bad)

debug · int

Debug level for verbose output

modfactor_primes · int

Number of primes to try

Bounds and Estimates

Mignotte Bound

modfactor.h:60-61

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) * M

This determines how high to lift in Hensel’s lemma.

Factor Count Estimation

modfactor.h:57

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

modfactor.h:37

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

modfactor.h:38

int sigma(const std::vector<bool> & deg);

Counts the number of possible degrees.

xtoxpowerp()

modfactor.h:44

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

modfactor.h:73

gen _is_irreducible(const gen & args, GIAC_CONTEXT);

Tests whether a polynomial is irreducible.

C++ Usage

gen poly = /* polynomial expression */;
gen result = _is_irreducible(poly, context);
// Returns true if irreducible, false otherwise

Algorithm Overview

1. Modular Reduction

   Choose a prime p and reduce the polynomial modulo p

2. Square-Free Factorization

   Factor out repeated factors using GCD with derivative

3. Distinct Degree Factorization

   Use DDF to group factors by degree

4. Equal Degree Factorization

   Apply Cantor-Zassenhaus to split factors of same degree

5. Hensel Lifting

   Lift factorization to Z/p^k with k large enough

6. Factor Combination

   Try combinations to find true factors over Z

Performance Considerations

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