Team: 54
School: MANZANO HIGH
Area of Science: Mathematics
Interim: Finding Inverses in a Finite Field
Interim Report: AiSC 2005-2006
Kristin Cordwell, Chen Zhao
Team Number 54
In our project, we are writing code to find inverses of integers mod p1 and elements of GF(2n)* using the Extended Euclidean Algorithm and Lagrange's Theorem from Group Theory. (If we take q mod p, it means that we divide q by multiples of p, and obtain a remainder r which is less than p. We can then say that r is congruent to q mod p.)
The Extended Euclidean Algorithm finds two integers, a and b, for two given relatively prime integers, p and q, such that ap + bq = 1. If we look at this equation modulo p, we see that, given such a q, we can find the inverse of q mod n: bq = 1 mod p. Concurrently, Lagrange's Theorem from Group Theory says that if we raise any element in a multiplicative group G to the order of the group, O(G), we get 1. This means that if we raise an element to one less power, O(G) - 1, we will obtain the multiplicative inverse of the element.
These methods can also both be applied to general finite fields. In our project, we are finding the inverses of polynomials in the Galois Field GF(2n)*, in which there are 2 n-1 elements. Thus, raising an element to the 2n-2 power will give its inverse. We can also use the Extended Euclidean Algorithm by beginning with the given field element (polynomial) and taking it mod the irreducible polynomial.
Both of these methods are useful; however, we are writing code to determine which is more efficient.
So far this year, we have written programs that find the inverse of an integer mod p (where p is prime) using both of these methods. We are currently working on writing code to find the inverse of a polynomial using the Extended Euclidean Algorithm. After we finish this code, we will then create a program to find the inverse of a polynomial using Lagrange's Theorem. Finally, we will compare the run times of the two methods, both for integers and for polynomials, and figure out which is most efficient. Using this information, we will begin to apply our code to fields such as cryptography and error correction codes (used in communications and data transmissions).
Also, we have written the skeleton of our web page. As we continue to make progress on our code and programs throughout the year, we will develop our page further.
This year, we learned basic C++ programming - functions, arrays, and structures. We are constantly furthering our understanding as we begin to write more advanced code for our project. We also learned how to make basic web pages. During the rest of the year, we plan to continue developing our programming skills.
Timeline:
December 16 - have the first two programs finished and the webpage started
January 15 - have the third program and the webpage finished
March 1 - have all four programs finished and debugged
Resources:
"Software Implementation of Elliptic Curve Cryptography over Binary Fields"
Hankerson, Hernandez, and Menezes
CHES 2000 Proceedings, Springer-Verlag, Berlin, 2000
"Elliptic Curve Public Key Cryptosystems"
Menezes
Kluwer Academic Publishers, Boston, 1993
Knuth, Donald; The Art of Computer Programming, vol. 2, Seminumerical Algorithms; Addison Wesley Longman; 1998; Berkeley, CA
(modular arithmetic, GCD [Euclidean Algorithm], raising to powers)
McEliece, Robert J.; Finite Fields for Computer Scientists and Engineers; Kluwer Academic Publishers; 1987; Boston
Lidl and Niederreiter; Finite Fields; Cambridge University Press; 1997; New York
Alfred J. Menezes, Editor; Applications of Finite Fields; Kluwer Academic Publishers; 1993; Boston
Joseph J. Rotman; A First Course in Abstract Algebra; Prentice-Hall; 2000; Upper Saddle River, NJ
(for Lagrange's Theorem, the Euclidean Algorithm)
Team Members:
Kristin Cordwell
Chen Zhao
Sponsoring Teacher: Stephen Schum