Dr Phill’s Science Made Simple

The Euclidean algorithm finds the greatest common devisor (gcd) of two integers x and y where y > x. It uses the fact that if \(y = ax + r\) then \(gcd(y, x) = gcd(ax,r)\). Repeatedly evaluate \(y_i = a_ix_i + r_i\), then set \(y_{i+1} = x_i\) and \(x_{i+1} = r_i\). When \(r_i = 0\), \(x_x\) is the gcd.

Example: find the GCD of 42823 and 6409.

The GCD is 17.

Given two integers x and y, find the two integers a and b such that ax + by = gcd(x, y). First, calculate the gcd \(g\) using the Euclidean algorithm. Rearrange the penultimate term.

Rearrange the previous term in the same way and replace the \(y_i\) term with \(x_{i-1}\) and the \(x_i\) term with \(r_{i-1}\) in the gcd equation.

Example y = 1914 and x = 899.

First, find the gcd using Euclid.

The gcd is 29, now apply the extended algorithm by rearranging the last but one equation and working backwards.

The extended computation can be done as part of the Euclid algorithm by adding two variables that will become the coefficients. Repeating the previous example:

The extended Euclidian algorithm is often used to calculate the modular inverse of an integer. Given two integers x and y where \(y > x\) and y is prime, then \(gcd(y, x) = 1\). The algorithm calculates a and b where \(ax + by = 1\). It follows that \(ax = 1\; mod\; y\), a is the modular inverse of x.

Example: find the modular inverse of 28 mod 37.

This works as 37 is prime. We use Extended Euclid starting with \(s_0 = 1\), \(s_1 = 0\), \(t_0 = 0\), \(t_1 = 1\).

This gives \(gcd(28, 37) = 1\) and \(4 * 28 - 3 * 37 = 1\) whicha can easily be verified. So, the inverse of 28 mod 37 is 4.

Integer polynomials can be performed for addition, subtraction, and multiplication. There is an integer prime modulus \(m\) for reducing the coefficients and ensuring that they are positive. If the examples \(m = 11\). For computation, polynomials are represented by vectors of their coefficients in order of increasing powers of \(x\).

Addition is just the sum of the coefficients, and subtraction is the difference of the coefficients.

Multiplication is just long multiplication.

Division can be done, but it is a bit more complex. It uses long division. The divisor coefficients need to be turned into their modular inverses and multiplied. For polynomials \(a\) and \(b\) we want to calculate \(a / b mod m\).

For a divisor coefficient \(b\) its modular inverse \(b^*\) is the integer satisfying \(bb^* = 1\; mod\; m\). This always exists if \(b \ne 0\) and \(gcd(b, m) = 1\). The second condition is true as \(b < m\) and \(m\) is prime. The coefficient divisor becomes \(a/b \rightarrow ab^*\; mod\; m\). In the case \(b = 0\) then \(b^* = 0\) works!

An example:

We need to calculate.

Find the first term divisor modular inverse: \(1^* = 1 \text{ mod 11}\).

Dividing the first terms of each gives a factor of \(3x^2\). Now perform long division mod 11.

This gives the quotient \(3x^2 + 2x + 1\) and the remainder \(x^3 + 10x^2 + 3x + 1\).

The modulus of a polynomial can also be another polynomial.

Polynomial multiplication and division can also be performed modulus a third polynomial. In the case of multiplication it is used to reduce the order of the result polynomial.

If two degree 12 polynomials are multiplied, the resultant polynomial has degree 24. This can be reduced to degree 12 by taking the modulus with a degree 13 polynomial woth the coefficent on the \(x^{12}\) term being 1. This is done using polynomial division and just keeping the remainder.

Example: polynomial multiplication.

]](x^5 + 3x^3 + 4) * (6x^6 + 4x^3) = 6x^{11} + 7x^9 + 4x^8 + 3x^6 + 5x^3]]

We want to reduce the degree of the result polynomial modulus \(x^5 + x^3 + 1\). This is done using long division. The coefficients will be calculated mod 11.

The reduced polynomial is the remainder \(7x^2 + 7x + 4\).

Modular polynomial division can be performed using the polynomial modular inverse. This requires a prime modulus for coefficients and a polynomial modulus that is indivisble, the polynomial equivalent of prime. The extended Euclid algorithm can be used to calculate the modular inverse.

Example find the inverse of \(2x^2 + 1\) mod \(x^4 + 5x + 3\) mod 11.

Start with \(s_0 = 1\), \(s_1 = 0\), \(t_0 = 0\), \(t_1 = 1\).

The greatest common divisor is 3. As this is a constant and polynomials are being compared, this can be normalised to 1 and the modular inverse exists. It is \(t_3 = 9x^3 + 9x^2 + x + 2\).

Polynomial division modulus polynomial uses polynomial multiplication modulus polynomial using the polynomial modular inverse of the divisor.