ECCHacks 
A gentle introduction to ellipticcurve cryptography 

Finite fieldsReduction 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 fieldF_{7} means the set {0,1,2,3,4,5,6} with the following overloaded arithmetic operations:
These operations, together with 0 and 1, satisfy all the equations that you expect: for example, x*(yz) = x*yx*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 conceptThe equations 1*1=1, 2*4=1, 3*5=1, 6*6=1 in F_{7} show that 1, 2, 3, 4, 5, 6 have reciprocals in F_{7}: 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_{10}), 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 fieldsFor 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,p2,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 "nonprime" 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^{p2}. 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. Version: This is version 2014.12.27 of the finitefield.html web page. 