A finite field is essentially a set of q=p^n numbers, where p is a prime and n is a positive integer. The characteristic of the finite field is defined to be p. Fields themselves have the operations addition, subtraction (so we have additive inverses), multiplication, and division (so we have multiplicative inverses), are commutative, associative, have the elements 0 (additive identity) and 1 (multiplicative identity), and all distributive properties hold. Examples of fields are the rational numbers, real numbers, and complex numbers, which by definition have characteristic 0. For crypto, we use finite fields because finite things are nicer to work with. The best example of a finite field is F_p = {0,1,2,..., p-1}. All arithmetic is done modulo p, so in the case of F_5 = {0,1,2,3,4} we have
4*2 = 8 = 3 mod 5 and 4*4 = 16 = 1 mod 5, so the inverse of 4 is 4.
For the case of the finite field q=2^n, n>0, elements are polynomials of degree at most n-1 with coefficients in F_2 = {0,1}. Arithmetic is done modulo an irreducible polynomial of degree n, like x^2+x+1 if n=2, which means that
x*x = x^2 = -x-1 = x+1 (in F_2, -1 = +1).
For elliptic curves, the points of the elliptic curve are the elements in the group we work with and are ordered pairs (x,y) satisfying y^2 = x^3+ax+b, where x,y,a, and b are in the finite field. Hope this helps!
-- Eric
― TOMBOT 64 (TOMBOT 64), Tuesday, 8 March 2005 03:41 (twenty years ago)
JW is a slashdork, but he is at his parents house (actually he's wandering around Providence; he just called me) so you may have to wait for his response, tom tom tom.
― Ian John50n (orion), Tuesday, 8 March 2005 03:46 (twenty years ago)