GeneratorPolynomial

What is it

A generator polynomial is a mathematical object (basically just a polynomial) that can be used to generate other polynomials. It's an abstract algebra concept that has concrete uses in cryptography. It relates to binary representations of numbers, information theory, prime numbers, factorization, and modular arithmetic.

Factoring

The basic math operation at the heart of much of cryptography is factoring. The strength of cryptography is built on the difficulty of factoring very large numbers.

Decomposing into primes

Every number can be decomposed into the product of prime numbers - this is a fundamental property of numbers. Cryptography is interested in finding very large prime numbers because composite numbers that are products of very large prime numbers are particularly difficult to factor, giving them higher crypotgraphic strength.

For example, if we take 15 we can decompose it into the product of two primes:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 15 = 3 \times 5 }

Other bases

This is not just true in base 10 arithmetic - it is also true in other bases as well. In binary, 15 is 00001111, 3 is 00000011, and 5 is 00000101, and the statement still holds:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 00001111 = 00000011 \times 00000101 }

One fact that is important for the insight into the next section is the definition of a polynomial. In general, a polynomial function is defined as a sum of monomial functions, where a monomial function is a constant, real number coefficient times a positive integer power of some independent variable x:

f(x) = \sum_{i=0}^{n} a_{i} x^{i}

When we talk about numbers that are base 10 or base 2, we are talking about numbers that are written as polynomials, with x replaced by the base. For example, the number 15 is:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 15 = 1 \times 10^{1} + 5 \times 10^{0} }

which is a polynomial, base 10. In binary, 15 is 00001111, or

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 15 = 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 | 1 \times 2^0 }

Algebraic bases

The above observation leads us to the question: what happens if we leave the base as a variable? The answer is, we can represent numbers using algebraic objects.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} 3 = (11)_{2} = x + 1 \\ 5 = (101)_{2} = x^2 + 1 \\ 15 = (1111)_{2} = x^3 + x^2 + x + 1 \end{align} }

IMPORTANT: we are using the binary representation here - the base 2 representation - so each of the numbers (3, 5, and 15) are turned into polynomials here, and those polynomials have base-2 coefficients.

Now we can represent the operation 15 = 3 * 5 as:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (x + 1)(x^2 + 1) = x^3 + x^2 + x + 1 }

which is equivalent to the true statement:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 00000011 \times 00000101 = 00001111 }

Now let's do a more complicated example. We'll use the twin primes 1787 and 1789 to create a composite number, and represent it using an arbitrary base (16). Then we'll do the polynomial multiplication, and parse the results to see if it holds up to a true statement.

First, for verification purposes, we compute our product:

1787 \times 1789 = 3196943

In our chosen base 16, this product is written:

(6023)_{16} \times (6025)_{16} = (51996995)_{16}

We start by writing our two prime numbers in base 16 notation:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} 1787 = (6023)_{16} = 6 x^3 + 2 x + 3 \\ 1789 = (6025)_{16} = 6 x^3 + 2 x + 5 \\ 3196943 = (51996995)_{16} = 5 x^7 + x^6 + 9 x^5 + 9 x^4 + 6 x^3 + 9 x^2 + 9x + 5 \end{align} }

Punch this into Wolfram Alpha:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (6x^3+2+3)*(6x^3+2+5) = 36 x^6 + 72 x^3 + 35 }

Oh no, we have overflow! We have to reduce the polynomial coefficients modulo 16. Starting from right to left:

35 = 2 \times 16 + 3 = 2 x + 3

---

(GOT CONFUSED HERE)

Substituting:

(6x^3+2+3)*(6x^3+2+5) = 36 x^6 + 72 x^3 + 2x + 3

Next term:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 72 x^3 = (4 \times 16 + 8) x^3 = (4 x + 8) x^3 = 4 x^4 + 8 x^3 }

Replacing and combining like terms

(6x^3+2+3)*(6x^3+2+5) = 36 x^6 + 4 x^4 + 8 x^3 + 2x + 3

Last step, reduce the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x^6} step:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 36 x^6 = (2 \times 16 + 4) x^6 = (2 x + 4) x^6 = 2 x^7 + 4 x^6 }

(6x^3+2+3)*(6x^3+2+5) = 2 x^7 + 4 x^6 + 4 x^4 + 8 x^3 + 2x + 3

6023 \times 6025 = a44953