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:

$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:

$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:

$15=1\times 10^{1}+5\times 10^{0}$

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

$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.

${\begin{aligned}3=(11)_{2}=x+1\\5=(101)_{2}=x^{2}+1\\15=(1111)_{2}=x^{3}+x^{2}+x+1\end{aligned}}$

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:

$(x+1)(x^{2}+1)=x^{3}+x^{2}+x+1$

which is equivalent to the true statement:

$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:

${\begin{aligned}1787=(6023)_{16}=6x^{3}+2x+3\\1789=(6025)_{16}=6x^{3}+2x+5\\3196943=(51996995)_{16}=5x^{7}+x^{6}+9x^{5}+9x^{4}+6x^{3}+9x^{2}+9x+5\end{aligned}}$

Punch this into Wolfram Alpha:

$(6x^{3}+2+3)*(6x^{3}+2+5)=36x^{6}+72x^{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:

$72x^{3}=(4\times 16+8)x^{3}=(4x+8)x^{3}=4x^{4}+8x^{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 $x^{6}$ step:

$36x^{6}=(2\times 16+4)x^{6}=(2x+4)x^{6}=2x^{7}+4x^{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