Team: 54
School: MANZANO HIGH
Area of Science: Mathematics
Abstract: Given two relatively prime integers, p and q, the Extended Euclidean Algorithm may be used to find two other integers, a and b, such that ap + bq = 1. If we consider this equation modulo n, it says that we can, given such a q, find the inverse of q mod n, that is, bq = 1 mod n. Alternately, Lagrange's Theorem from Group Theory says that, for a multiplicative group G, any element raised to the order of the group, O(G), equals 1. This means that if an element is raised to one less power, O(G) - 1, it will also give the multiplicative inverse of the element. Since the numbers that are relatively prime to n form a multiplicative group, this provides an alternate method for finding a multiplicative inverse mod n.
Both of these methods may be extended to general finite fields. In particular, GF(2^n) is the finite field of polynomials with coefficients in Z_2, the integers modulo 2, with each polynomial being taken modulo an irreducible polynomial of degree n. There are 2^n elements in the field, and, discarding the zero element, there are 2^n-1 elements in the multiplicative group GF(2^n)*, so we may find the inverse of an element by raising it to the 2^n-2 power. Alternately, we may use the Extended Euclidean Algorithm, starting with the given field element (polynomial) and the irreducible polynomial to find the inverse.
Finite fields, especially GF(2^n), are used extensively in such fields as cryptography and error correction codes. For example, the Advanced Encryption Standard (AES) calculates the inverse of elements in GF(2^8) in each round of the encryption. Elliptic Curve Cryptography also makes use of finite field inverses. Reed-Solomon and other BCH Error Correcting Codes, extensively used in communications and data transmissions, use inverses of elements in GF(2^n) as well. It is therefore useful to be able to efficiently calculate the inverse of these field elements.
In our project, we will write code to implement both of these methods of finding inverses of elements of GF(2^n), and we will measure the run-times to determine which is more efficient.
Team Members:
Kristin Cordwell
Chen Zhao
Sponsoring Teacher: Stephen Schum