ECCHacks

Finite fields

[Python snippets]

Reduction modulo 7 is the operation that reads an integer, divides the integer by 7 to produce a quotient and remainder, and outputs the remainder. Math people write "x mod 7" for the reduction of x modulo 7. Python people write "x % 7":

     for n in range(0,20):
       print n,n%7
     
     # output: 0 0
     # output: 1 1
     # output: 2 2
     # output: 3 3
     # output: 4 4
     # output: 5 5
     # output: 6 6
     # output: 7 0
     # output: 8 1
     # output: 9 2
     # output: 10 3
     # output: 11 4
     # output: 12 5
     # output: 13 6
     # output: 14 0
     # output: 15 1
     # output: 16 2
     # output: 17 3
     # output: 18 4
     # output: 19 5

The output is always in the set {0,1,2,3,4,5,6}. Warning: C also has an "x % 7", but most compilers produce a negative remainder if x is negative, and we don't want negative remainders; the same operation in C is "((x % 7) + 7) % 7".

A finite field

F₇ means the set {0,1,2,3,4,5,6} with the following overloaded arithmetic operations:

• +: Given two elements x,y of F₇, output (x+y) mod 7. For example, given 2 and 5, output 0.
• -: Given two elements x,y of F₇, output (x-y) mod 7. For example, given 2 and 5, output 4.
• *: Given two elements x,y of F₇, output (x*y) mod 7. For example, given 2 and 5, output 3.

These operations, together with 0 and 1, satisfy all the equations that you expect: for example, x*(y-z) = x*y-x*z.

Here's how to define an "F7" type in Python with its own +,-,*, separate from the integer +,-,*. First let's define an initializer F7(x) converting an integer x into x mod 7, and some output functions:

     class F7:
       def __init__(self,x):
         self.int = x % 7
       def __str__(self):
         return str(self.int)
       __repr__ = __str__
     
     # examples:
     print F7(2)
     # output: 2
     print F7(6)
     # output: 6
     print F7(7)
     # output: 0
     print F7(10)
     # output: 3

Now we can define +,-,* operations for this type:

     F7.__add__ = lambda a,b: F7(a.int + b.int)
     F7.__sub__ = lambda a,b: F7(a.int - b.int)
     F7.__mul__ = lambda a,b: F7(a.int * b.int)
     
     # examples:
     print F7(2) + F7(5)
     # output: 0
     print F7(2) - F7(5)
     # output: 4
     print F7(2) * F7(5)
     # output: 3

Let's also allow equality tests and inequality tests:

     F7.__eq__ = lambda a,b: a.int==b.int
     F7.__ne__ = lambda a,b: a.int!=b.int
     
     # examples:
     print F7(7) == F7(0)
     # output: True
     print F7(10) == F7(3)
     # output: True
     print F7(-3) == F7(4)
     # output: True
     print F7(0) != F7(1)
     # output: True
     print F7(0) != F7(2)
     # output: True
     print F7(1) != F7(2)
     # output: True
     print F7(7) != F7(0)
     # output: False
     print F7(10) != F7(3)
     # output: False
     print F7(-3) != F7(4)
     # output: False
     print F7(0) == F7(1)
     # output: False
     print F7(0) == F7(2)
     # output: False
     print F7(1) == F7(2)
     # output: False

Division, and the field concept

The equations 1*1=1, 2*4=1, 3*5=1, 6*6=1 in F₇ show that 1, 2, 3, 4, 5, 6 have reciprocals in F₇: 1/1 = 1, 1/2 = 4, 1/3 = 5, 1/4 = 2, 1/5 = 3, 1/6 = 6. 0 doesn't have a reciprocal: there's nothing you can multiply 0 by to obtain 1.

We don't say field, and don't use the F notation, unless the nonzero elements are exactly the elements with reciprocals. For example, the integers modulo 10 aren't a field (and there isn't an F₁₀), since the set {1,2,3,4,5,6,7,8,9} of nonzero integers modulo 10 isn't the same as the set {1,3,7,9} of integers modulo 10 with reciprocals. As another (nitpicky) example, the integers modulo 1 aren't a field, since the set {} of nonzero integers modulo 1 isn't the same as the set {0} of integers modulo 1 with reciprocals.

More finite fields

For every prime number p (2 or 3 or 5 or 7 or 11 or ...), F_p is the finite field of integers modulo p:

     def F(p):
       # caveat: caller must ensure that p is prime
       class F:
         def __init__(self,x):
           self.int = x % p
         def __str__(self):
           return str(self.int)
         __repr__ = __str__
         def __eq__(a,b):
           return a.int == b.int
         def __ne__(a,b):
           return a.int != b.int
         def __add__(a,b):
           return F(a.int + b.int)
         def __sub__(a,b):
           return F(a.int - b.int)
         def __mul__(a,b):
           return F(a.int * b.int)
         def __div__(a,b):
           # caveat: caller must ensure that b is nonzero
           return a*F(pow(b.int,p-2,p))
       return F
     
     # examples:
     F1009 = F(1009)
     print F1009(-1) == F1009(1008)
     # output: True
     print F1009(6) != F1009(5)
     # output: True
     print F1009(101) + F1009(1000) == F1009(92)
     # output: True
     print F1009(101) - F1009(1000) == F1009(110)
     # output: True
     print F1009(101) * F1009(1000) == F1009(100)
     # output: True
     print F1009(101) / F1009(1000) == F1009(213)
     # output: True

There are also "non-prime" finite fields (of sizes 4, 8, 9, 16, 25, 27, 32, ...), but we won't need those for ECCHacks.

The __div__ function above uses "Fermat's little theorem", which says that you can compute the reciprocal of any nonzero x in F_p by computing x^p-2. There are other division methods, but the Fermat method is very simple to implement, and its performance is tolerable even when p is very large.