Overview

8 Multiplication of polynomials explained

The chapter explains how irreducible polynomials serve as the polynomial analogue of prime numbers and why they are essential for building extension fields. It shows that the choice of the underlying prime modulus can change whether a polynomial is reducible or irreducible, and that once an irreducible polynomial is chosen, setting it equal to zero creates the reduction rule that defines the field. From that rule, every higher power of the polynomial variable can be rewritten in terms of lower powers, so all field elements can be represented with a fixed number of coefficients.

It then develops polynomial multiplication modulo an irreducible polynomial. The ordinary product of two polynomials is first computed using coefficient convolution, producing terms up to the sum of the input degrees. Those higher-degree terms are then reduced using a precomputed table built from repeated multiplication by the variable and substitution of the irreducible polynomial relation. This table captures how each power of the variable expands back into the reduced basis, making modular multiplication efficient and systematic.

The later part focuses on implementation details, including how to build the multiplication matrix, how to multiply using it, and how to normalize a polynomial so its leading coefficient becomes one. It also includes a debugging routine for printing the table and a worked example that confirms the generated rows match the expected expansion pattern. Overall, the chapter lays the algebraic and coding foundation needed for all later finite-field routines in the book by turning abstract polynomial reduction into practical, reusable algorithms.

Multiplication modulo a prime polynomial. Polynomial \(a\) times polynomial \(b\) gives polynomial \(c\)—each coefficient of \(c\) is multiplied with the corresponding row in the expansion matrix and then summed to find the result modulo the prime polynomial.
figure

Summary

  • An irreducible polynomial over a finite field is defined as a polynomial having no other polynomial factors.
  • The variable defining an irreducible polynomial is a root of the polynomial when set equal to zero.
  • A matrix of coefficients with \(k\) columns and \(2k\) rows allows the multiplication of any two polynomials modulo an irreducible polynomial. This lookup table is only computed once for an irreducible polynomial.
  • A degree \(n\) polynomial multiplied by a degree \(m\) polynomial has intermediate result of degree \(n+m\). The degrees higher than \(k\) are reduced by multiplying the coefficient at that power by all the coefficients in the corresponding row of the matrix and summed to the final result, which has, at most, \(k\) coefficients.
  • A monic polynomial has a leading coefficient of 1. All irreducible polynomials used for field extensions are monic.
  • Normalization of a polynomial inverts the leading coefficient and multiplies that with all coefficients leaving a monic polynomial.
  • The term prime polynomial  means the same as the term irreducible polynomial  because working with a polynomial as a modulus is the same concept as working with a prime number as a modulus for integers.

FAQ

What is an irreducible polynomial in this chapter?An irreducible polynomial is a polynomial that cannot be factored into smaller-degree polynomials over the chosen finite field. In this chapter, it plays the same role that a prime number plays in ordinary modular arithmetic: it serves as the modulus that defines the extension field.
Why does the book sometimes call an irreducible polynomial a “prime polynomial”?Because in this context it behaves like a prime modulus. When a polynomial is used as the modulus for arithmetic, it acts like a prime in the same way an integer prime does in modular number systems. “Irreducible” describes its factorization property, while “prime polynomial” emphasizes its role as a modulus.
Why does the choice of field prime affect whether a polynomial is irreducible?Polynomial factorization depends on the coefficients being considered modulo a specific prime. A polynomial may be irreducible modulo one prime but factor into smaller polynomials modulo another. So the underlying field prime determines which polynomials can be used to build the extension field.
What happens when an irreducible polynomial is set equal to zero?Setting the polynomial equal to zero gives a rule for replacing higher powers of the symbol, such as \(t^n\), with lower-degree terms. This lets all powers reduce back into a fixed degree range, making the extension field finite.
Why do all elements in the extension field have degree less than \(n\)?Because any term \(t^n\) or higher can be reduced using the irreducible polynomial relation. As a result, every field element can be represented using only coefficients of \(1, t, t^2, \dots, t^{n-1}\).
How is polynomial multiplication done modulo an irreducible polynomial?First, multiply the two polynomials normally to get a higher-degree result. Then reduce any terms of degree \(n\) or above using the irreducible polynomial so that the final result has degree at most \(n-1\).
Why does the multiplication table need \(2n\) rows?The product of two degree-\((n-1)\) polynomials can have degree as high as \(2n-2\). So the table must cover powers from \(t^0\) through \(t^{2n-2}\), which requires \(2n-1\) rows conceptually, and the implementation allocates enough space to handle that range.
What is the purpose of the coefficient table in polynomial multiplication?The table stores the reduced forms of powers of \(t\) under the chosen irreducible polynomial. During multiplication, each high-degree coefficient is combined with the appropriate row of this table, allowing fast reduction without repeating polynomial division every time.
Why does the code normalize the irreducible polynomial?Normalization makes the polynomial monic, meaning its leading coefficient becomes 1. This simplifies the reduction process and ensures the modulus has the standard form expected by the multiplication routines.
What is the key idea behind the debug output for the multiplication table?The debug output prints the table row by row so you can verify the structure visually. It helps confirm that the diagonal entries, the modulus row, and the shifted reduction rows were generated correctly, which is useful for testing and troubleshooting.

pro $24.99 per month

  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose one free eBook per month to keep
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime

lite $19.99 per month

  • access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more


Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free
Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free
Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free