Ben-Or’s algorithm tests whether a degree-n polynomial over a finite field is irreducible. It rejects a trial polynomial when it shares a nonconstant factor with x^(p^i)−x for any 1 ≤ i ≤ n/2. section 11.1 section 11.4
A trial-and-error implementation follows this flow:
- Choose a degree-n trial polynomial, commonly the trinomial x^n+x+a, and vary its constant coefficient. section 11.1 section 11.2
- For each i from 1 through n/2, compute x^(p^i) modulo the trial polynomial, subtract x, and calculate the polynomial gcd. section 11.1 section 11.2
- Reject the candidate as soon as a gcd has nonzero degree; otherwise accept it as irreducible. section 11.2 section 11.4
- Stop when a candidate passes or when the coefficient search reaches the prime-field limit; return failure if no candidate passes. section 11.2
Quadratic example
For f=x²+13x+1 modulo 1187, gcd(x^1187−x,f) is the constant 849, normalized to 1. Because n=2, the test is complete; checking gcd(x^(1187²)−x,f) returns f as expected. section 11.1
Figure 11.1 Ben-Or’s algorithm for finding irreducible polynomials using trial and error
Use the algorithm flow to inspect candidate initialization, repeated Frobenius-power computation, gcd rejection, acceptance, and cleanup. section 11.2
