A root is a value in an algebraic structure that makes a polynomial equal to zero. In finite-field work, roots support polynomial factorization and can also be represented formally by setting an irreducible polynomial to zero. section 14.4 section 8.1
A root-finding workflow for a polynomial modulo a prime proceeds as follows:
- Reduce the problem recursively into smaller polynomial factors. section 14.4
- Check for a zero root by testing the constant term and dividing by x when it vanishes. section 14.4
- Solve degree-one factors directly and degree-two factors with the quadratic formula. section 14.4
- For higher degrees, use modular exponentiation, greatest common divisors, random splitting values, and a stack of factors. section 14.4
A formal root in a finite-field extension
Setting x² + 13x + 1 equal to zero modulo 1187 gives x² = −13x − 1. Thus x is technically a root of the irreducible polynomial, even though no integer value satisfies the equation; the equation defines the desired field element. section 8.1
Figure 14.2 Roots mod p of P(x)
Use the factorization flow to follow how modular gcd computations split a polynomial until its linear or quadratic factors yield roots. section 14.4
