Introduction

Factoring a big integer into primes is famously hard — it's the assumption behind RSA. So it is a pleasant shock that a cousin problem, factoring a polynomial into irreducible pieces, is easy when you work modulo a prime pp.

Take a polynomial like x4+x2+3x^4 + x^2 + 3 over the finite field F5\mathbb{F}_5 (arithmetic mod 5). Multiplying it out from smaller pieces is trivial. Going the other way — starting from the expanded polynomial and finding its irreducible factors — looks like it should require guesswork, the same way integer factoring does.

In 1967, mathematician Elwyn Berlekamp showed it doesn't. His algorithm turns polynomial factorization over a finite field into a problem about matrices: build one specific matrix from the polynomial, find its null space, and the null space hands you the factors — no guessing, no brute force over candidate roots.

Try It

Below is the polynomial f(x)=x4+x2+3f(x) = x^4 + x^2 + 3 over F5\mathbb{F}_5. Press Build the matrix to see the Berlekamp matrix computed from x5i mod f(x)x^{5i} \bmod f(x), then Find the factors to solve (Q−I)v⃗=0(Q - I)\vec{v} = 0 and split f(x)f(x) into its irreducible pieces.

<p class="hint">Berlekamp's algorithm factors a polynomial over a finite field by finding the null space of a matrix built from it. Follow the two steps below.</p>
<div class="poly-box">
  <span class="poly-label">Polynomial:</span>
  <span class="poly">f(x) = x<sup>4</sup> + x<sup>2</sup> + 3</span>
  <span class="poly-field">over the field F5 (mod 5)</span>
</div>
<div class="btns">
  <button id="build" type="button">Build the matrix</button>
  <button id="solve" type="button" disabled>Find the factors</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div id="matrix" class="matrix-wrap"></div>
<div class="status" id="status">Press "Build the matrix" to begin.</div>
<div id="factors" class="factors"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.poly-box { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap;
            background: #eef2f6; border: 1px solid #d3dde6; border-radius: 8px;
            padding: .5rem .8rem; margin-bottom: .7rem; font-size: .95rem; }
.poly-label { font-weight: 700; color: #1d3557; }
.poly { font: 600 1.05rem ui-monospace, monospace; color: #1d3557; }
.poly-field { margin-left: auto; font-size: .82rem; color: #556; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }
.matrix-wrap { overflow-x: auto; margin-bottom: .6rem; }
table.matrix { border-collapse: collapse; font: 600 .95rem ui-monospace, monospace; }
table.matrix caption { caption-side: top; text-align: left; font: 700 .82rem system-ui, sans-serif;
                        color: #1d3557; margin-bottom: .3rem; }
table.matrix td { width: 2.2rem; height: 2.2rem; text-align: center; border: 1px solid #cdd9e3;
                   background: #f6f8fa; }
table.matrix td.diag { background: #e8eef3; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.factors { display: flex; gap: .5rem; flex-wrap: wrap; }
.factor-chip { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px;
               padding: .35rem .7rem; font: 600 .95rem ui-monospace, monospace; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Fixed demo polynomial f(x) = x^4 + x^2 + 3 over the finite field F5 (arithmetic mod 5).
const P = 5;
const F = [3, 0, 1, 0, 1]; // coefficients ascending by degree: 3 + 0x + 1x^2 + 0x^3 + 1x^4
const mod = (a, p) => ((a % p) + p) % p;

// Polynomial arithmetic mod p, arrays indexed by ascending degree.
function polyDeg(a){ for(let i=a.length-1;i>=0;i--) if(mod(a[i],100000)!==0) return i; return -1; }
function trim(a,p){ a=a.map(c=>mod(c,p)); let d=a.length-1; while(d>0&&a[d]===0) d--; return a.slice(0,d+1); }
function polySub(a,b,p){ const n=Math.max(a.length,b.length); const r=new Array(n).fill(0);
  for(let i=0;i<n;i++) r[i]=mod((a[i]||0)-(b[i]||0),p); return trim(r,p); }
function polyMul(a,b,p){ const r=new Array(a.length+b.length-1).fill(0);
  for(let i=0;i<a.length;i++) for(let j=0;j<b.length;j++) r[i+j]=mod(r[i+j]+a[i]*b[j],p); return trim(r,p); }
function inv(a,p){ a=mod(a,p); for(let x=1;x<p;x++) if(mod(a*x,p)===1) return x; return 1; }
function polyDivMod(a,b,p){
  let rem=a.slice(); const db=polyDeg(b); const lcInv=inv(b[db],p);
  const q=new Array(Math.max(0,rem.length-db)).fill(0);
  while(polyDeg(rem)>=db && polyDeg(rem)>=0){
    const dr=polyDeg(rem); const coeff=mod(rem[dr]*lcInv,p); const shift=dr-db;
    q[shift]=mod((q[shift]||0)+coeff,p);
    for(let i=0;i<=db;i++) rem[i+shift]=mod(rem[i+shift]-coeff*b[i],p);
    rem=trim(rem,p); if(polyDeg(rem)<0) break;
  }
  return { q: trim(q,p), r: trim(rem,p) };
}
function polyMod(a,m,p){ return polyDivMod(a,m,p).r; }
function polyGCD(a,b,p){
  a=trim(a,p); b=trim(b,p);
  while(polyDeg(b)>=0){ const r=polyMod(a,b,p); a=b; b=r; }
  const d=polyDeg(a); if(d<0) return a;
  const lcInv=inv(a[d],p); return trim(a.map(c=>mod(c*lcInv,p)),p);
}
function polyPowMod(base,e,m,p){
  let result=[1], b=polyMod(base,m,p);
  while(e>0){ if(e&1) result=polyMod(polyMul(result,b,p),m,p); b=polyMod(polyMul(b,b,p),m,p); e>>=1; }
  return result;
}
function polyToStr(a){
  const d=polyDeg(a); if(d<0) return '0';
  const terms=[];
  for(let i=d;i>=0;i--){ if(a[i]===0) continue;
    let t; if(i===0) t=String(a[i]); else if(i===1) t=(a[i]===1?'':String(a[i]))+'x'; else t=(a[i]===1?'':String(a[i]))+'x^'+i;
    terms.push(t); }
  return terms.join(' + ');
}

// Berlekamp matrix: row i holds the coefficients of x^(i*p) mod f(x), via fast exponentiation.
function berlekampMatrix(f,p){
  const n=polyDeg(f); const rows=[];
  for(let i=0;i<n;i++){
    const xip=polyPowMod([0,1], i*p, f, p);
    const row=new Array(n).fill(0);
    for(let j=0;j<xip.length;j++) row[j]=xip[j];
    rows.push(row);
  }
  return rows;
}

// Gaussian elimination on (Q - I) mod p to find a basis for its null space.
function nullSpace(Q,p){
  const n=Q.length;
  const M=Q.map((row,i)=>row.map((v,j)=>mod(v-(i===j?1:0),p)));
  const pivots=[]; let rank=0;
  for(let col=0;col<n&&rank<n;col++){
    let pivotRow=-1;
    for(let r=rank;r<n;r++) if(mod(M[r][col],p)!==0){ pivotRow=r; break; }
    if(pivotRow===-1) continue;
    [M[rank],M[pivotRow]]=[M[pivotRow],M[rank]];
    const invPiv=inv(M[rank][col],p);
    for(let c=0;c<n;c++) M[rank][c]=mod(M[rank][c]*invPiv,p);
    for(let r=0;r<n;r++){ if(r!==rank && mod(M[r][col],p)!==0){
      const factor=M[r][col];
      for(let c=0;c<n;c++) M[r][c]=mod(M[r][c]-factor*M[rank][c],p);
    }}
    pivots.push(col); rank++;
  }
  const freeCols=[]; for(let c=0;c<n;c++) if(!pivots.includes(c)) freeCols.push(c);
  const basis=[];
  for(const fc of freeCols){
    const vec=new Array(n).fill(0); vec[fc]=1;
    for(let i=0;i<pivots.length;i++){ const pc=pivots[i]; vec[pc]=mod(-M[i][fc],p); }
    basis.push(vec);
  }
  return basis;
}

// Use each null-space basis vector v(x) to split factors via gcd(f, v(x) - s) for s in F_p.
function berlekampFactor(f,p,basis){
  f=trim(f,p);
  let factors=[f];
  const target=basis.length;
  if(target===1) return factors;
  for(let bi=1; bi<basis.length && factors.length<target; bi++){
    const v=trim(basis[bi],p);
    const newFactors=[];
    for(const g of factors){
      if(polyDeg(g)===0){ newFactors.push(g); continue; }
      let remaining=g; const pieces=[];
      for(let s=0;s<p;s++){
        if(polyDeg(remaining)<=0) break;
        const vs=polySub(v,[s],p);
        const d=polyGCD(remaining,vs,p);
        if(polyDeg(d)>0){ pieces.push(d); remaining=polyDivMod(remaining,d,p).q; }
      }
      if(polyDeg(remaining)>0) pieces.push(remaining);
      newFactors.push(...pieces);
    }
    factors=newFactors;
  }
  return factors;
}

let Q = null, basis = null;

function setStatus(t, cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function renderMatrix(){
  const n = Q.length;
  let html = '<table class="matrix"><caption>' + fmt('Berlekamp matrix Q (%n% x %n%), row i = coefficients of x^(5i) mod f(x)', { n: n }) + '</caption>';
  for(let i=0;i<n;i++){
    html += '<tr>';
    for(let j=0;j<n;j++) html += '<td class="' + (i===j?'diag':'') + '">' + Q[i][j] + '</td>';
    html += '</tr>';
  }
  html += '</table>';
  document.getElementById('matrix').innerHTML = html;
}

function renderFactors(factors){
  const box = document.getElementById('factors');
  box.innerHTML = factors.map(g => '<span class="factor-chip">' + polyToStr(g) + '</span>').join('');
}

document.getElementById('build').addEventListener('click', () => {
  Q = berlekampMatrix(F, P);
  renderMatrix();
  basis = nullSpace(Q, P);
  setStatus(fmt('Matrix built. The null space of (Q - I) has dimension %k% — so f(x) has exactly %k% irreducible factors.', { k: basis.length }), 'info');
  document.getElementById('solve').disabled = false;
  document.getElementById('build').disabled = true;
});

document.getElementById('solve').addEventListener('click', () => {
  const factors = berlekampFactor(F, P, basis);
  renderFactors(factors);
  setStatus(fmt('Found %k% irreducible factors — their product reconstructs f(x) exactly.', { k: factors.length }), 'ok');
  console.log('Berlekamp factors:', factors.map(polyToStr).join(', '));
  document.getElementById('solve').disabled = true;
});

document.getElementById('reset').addEventListener('click', () => {
  Q = null; basis = null;
  document.getElementById('matrix').innerHTML = '';
  document.getElementById('factors').innerHTML = '';
  document.getElementById('build').disabled = false;
  document.getElementById('solve').disabled = true;
  setStatus('Press "Build the matrix" to begin.', '');
});
Result
Console

Every step is exact arithmetic mod 5 — no approximation, no search over random polynomials. The dimension of the null space you compute tells you, before you even extract a single factor, exactly how many irreducible factors f(x)f(x) has.

The Real Complexity

Why does the matrix trick even work? It leans on a special feature of finite fields called the Frobenius map: for any element aa of Fp\mathbb{F}_p, raising to the pp-th power fixes it, so ap=aa^p = a. Berlekamp extends that idea to polynomials modulo f(x)f(x).

  • Build the matrix. For a degree-nn polynomial f(x)f(x), compute xip mod f(x)x^{ip} \bmod f(x) for i=0,…,n−1i = 0, \dots, n-1. Stack the coefficient vectors as rows to get an n×nn \times n matrix QQ — this costs about O(n2log⁡n)O(n^2 \log n) operations using repeated squaring mod f(x)f(x).
  • Find the null space. Solve (Q−I)v⃗=0⃗(Q - I)\vec{v} = \vec{0} over Fp\mathbb{F}_p with ordinary Gaussian elimination — O(n3)O(n^3) arithmetic operations, the same cost as solving any linear system of that size.
  • Read off the count. The dimension kk of that null space equals the number of distinct irreducible factors of f(x)f(x) (assuming ff is squarefree). No trial division, no candidate roots — the answer falls straight out of linear algebra.
  • Split with gcd. Each basis vector v(x)v(x) of the null space satisfies v(x)p≡v(x)(modf(x))v(x)^p \equiv v(x) \pmod{f(x)}, so it behaves like a constant on each irreducible factor. Computing gcd⁡(f(x),v(x)−s)\gcd(f(x), v(x) - s) for each s∈Fps \in \mathbb{F}_p peels the factors apart, using the same Euclidean algorithm idea as ordinary integer gcd.

The whole procedure runs in polynomial time in nn and pp — worlds away from integer factoring, where no polynomial-time algorithm is known and the best classical attacks, like the number field sieve, are sub-exponential at best. Finite-field polynomials are simply a friendlier arithmetic world: the Frobenius map gives you a algebraic shortcut that plain integers never offer.

Where It Matters

Splitting polynomials over finite fields is quiet, foundational machinery that shows up wherever data lives in Fp\mathbb{F}_p instead of the real numbers:

  • Error-correcting codes: decoding Reed-Solomon codes — used on CDs, QR codes, and deep-space communication — requires locating roots of polynomials over a finite field, a job built on exactly this kind of factorization.
  • Computer algebra systems: software like Maple, Mathematica and SageMath call a Berlekamp-style routine (or its faster descendant, the Cantor-Zassenhaus algorithm) every time you ask them to factor a polynomial mod pp.
  • Cryptography: constructing finite fields Fpn\mathbb{F}_{p^n} for elliptic-curve and pairing-based schemes requires irreducible polynomials, which factorization algorithms help verify and generate.
  • Coding theory research: cyclic codes, BCH codes and their generalizations are all defined via factorizations of xn−1x^n - 1 over a finite field.

It's a rare case where an exotic-sounding 1960s algorithm quietly runs, unnoticed, every time you play a scratched CD or scan a damaged QR code.

Conclusion

Berlekamp's factorization is a reminder that "hard-looking" problems sometimes hide an entirely different, friendlier structure underneath. Integer factoring stays stubborn enough to protect RSA. But swap integers for polynomials over a finite field, and the exact same shape of question — split this object into its irreducible pieces — collapses into solving a linear system.

The next time your phone reads a scuffed-up QR code or a satellite link corrects a burst of noise, there is a good chance a factorization very much like Berlekamp's is running quietly underneath, turning a matrix's null space into a clean set of roots.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/berlekamp-factorization/Content licensed under CC BY-NC 4.0.