Algebra is the study of the possible structures of mathematical systems. Particular systems are given names, such as a group and a field. Fields are among the most familiar mathematical structures. The rational, real and complex numbers are all examples of fields. To the computer scientist: think objects - data elements and methods that can be called upon the data elements.
The data elements of fields are called the numbers. The methods (called operations) are addition, subtraction, multiplication and division.
A group is a field without multiplication. If you take a field and forget about multiplication, you have a group with respect to addition. A field, when considering only multiplication, is not a group because zero is without an inverse. However, we often look at the field with zero removed, the group of invertible elements in the field. Other examples of groups are the integers, negatives included, with the operation of addition; the positive rationals (zero excluded) with the operation of multiplication.
So far all our examples have an infinite number of elements. There are groups and fields with finite number of elements. If p is a prime, the integers mod p are a field.
Exercise: Take a prime of your choice and work out the table of addition and multiplication for the integers mod p. Find the additive and multiplicative inverses for each number. Solve some linear equations, given a, b and y, find an x satisfying ax + b = y.
Besides the integers mod p, there are the Galois Fields, GF(q), which have q elements, where q is a pure power of a prime p, q=p^i for some integer i one or greater. If 1 is added to itself repeatedly in GF(q), the sequence of numbers will be:
1, 2, 3, 4, ..., p-1, 0Because of this twisting back to 0 after p steps, GF(q) is said to have characteristic p. Infinite fields, where the sequence never ends:
1, 2, 3, 4, ....are said to have characteristic zero. Examples of fields of characteristic zero are the fields of real or complex numbers.
Removing zero from GF(q) gives a group of q-1 elements with respect to the multiplication operation. Importantly, these groups are cyclic. That is, there are elements of GF(q), called generators, whose successive powers cycle through all elements of the group.
Exercise: Take the example of GF(p), that is, the integers mod p, for several different choices of the prime p. For each invertible element x of GF(p), notation GF(p)*, form the so called orbit of the element:
< x > = { x, x^2, x^3, ... , 1 }
(Note: the invertible elements of GF(p) are 1, ..., p-1.)
Find the size of different orbits. Find an x whose orbit includes
all of GF(p)*. Such an x is a generator.
Theorem: Every GF(q)* is cyclic.
That is, every GF(q)* has generators. Generators are customarily denoted by g. This theorem says that for any x in GF(q)*, there is an integer i such that:
x = g^i
This i is the Discret Logarithm of x in base g. (There may
be other generators, defining other logarithms.)
Diffie-Hellman Problem: Given a q=p^k, p a prime, and generator g of GF(q)*; for any x in GF(q)* find the integer i such that x=g^i in GF(q)*. Since g^(q-1)=1 (Little Fermat Theorem), this i is unique mod q-1.
It is easy (Polynomial time algorithm) to compute x from g and i, but it is conjectured hard (Nondeterministic Polynomial time required) to compute i from g and x. This is the heart of many cryptographic systems in use today. If this conjecture falls, so too all these cryptographic systems.
Proof sketch of algebraic facts
For integers x and y, consider the set of all diophantine linear combinations ax+by, that is, let a and b vary over all integers, positive and negative. Consider these as points on a number line, they are all integers. Pick two closest points:
s = a_s x + b_s y
t = a_t x + b_t y
By subtraction, this "gap" can be brought to the origin. That is,
the point (s-t) is on the lattice. Since this is the smallest gap,
the lattice must be simply all multiples of (s-t).
Since x and y are on the lattice, (s-t) therefore divides x and y - it is a common divisor of x and y. Since any d dividing both x and y divides any linear combination of x and y, specifically, it divides (s-t), then (s-t) is the greatest common divisor of x and y.
Chosing x to be prime p and y to be less than x, but non-zero, therefore, (s-t)=1. That is, there is an equation:
a p + b y = 1
So b y = 1 mod p. b is the inverse of y. Hence GF(p) is a field.
Taking polynomials with coefficients in the field GF(p), notation GF(p)[x], read "GF(p) adjoin x", the same argument shows that for any two such polynomials f(x) and g(x) with greatest common divisor 1, there exists polynomials a(x) and b(x) such that:
a(x) f(x) + b(x) g(x) = 1
The condition of "greatest common divisor 1" can be achieved
by letting f(x) be an irreducible polynomial, say of degree d,
and g(x) being any polynomial of degree less than d.
So the resulting structure GF(p)[x] mod f(x) is a field.
Its elements can be represented as polynomials with degree
less than k and therefore has p^k elements.
To elaborate somewhat, it is a well-worn habit to consider a polynomial f(x)=x^d+ax^(d-1)+...+e as a "formula" to be evaluated at x, where x is a number of the same "type" as the coefficients a, b, ..., e, here we treat the polynomial formally: the x is an abstract symbol, meaning nothing, but guiding the calculation of polynomial addition and multiplication according to the usual rules. The resulting "number" a x^(d-1) + b x^(d-2) + .... + e can then be considered a vector with entry a in the coordinate marked by the symbol x^(d-1), entry b in the coordinate marked by the symbol x^(d-2), and so on.
We next show that the GF(q)* just created are cyclic. To do this we first must show that a polynomial of degree d with coefficients in a field has at most d distinct roots. Since the coefficients we are concerned with, elements of GF(q)* look like polynomials in x, we will construct our polynomials in y.
If r is a root of f(y) = a y^d + b y^(d-1) + ... + e, then divide f(y) by (y-r). The result looks like:
f(y) = g(y)(y-r) + remainder.
Evaluation at y=r determines that the remainder equals zero.
Further consideration shows that all other roots of f(y),
must be roots of g(y).
Furthermore, the degree of g(y) is d-1.
Continuing this way, supposing more than d roots to f(y) we
will end up with more than one root to the simple polynomial (y-s),
which is absurd.
Second, we must defined the Euler Totient Function phi(n) and show that it satisfies a certain sum. The Euler Totient function phi(n) is the number of numbers between 1 and n which have greatest common divisor 1 with n. Consider the sequence:
1/n, 2/n, 3/n, ..., n-1/n, n/nIn this sequence, some of the fractions will not be reduced to lowest terms. The number that are in lowest terms equal phi(n). Consider those fractions which reduce to have denominator d. There will be phi(d) of these, and d will divide n. Considering all possible divisors of n, we have the sum:
sum_(d divides n) phi(n) = n
We now put these two facts together for our proof of the cyclicity of GF(q)*. Taking any x in GF(q)* and form its orbit < x >. The orbit will have some size d, where d divides q-1. All the elements in this orbit will satisfy the equation y^d=1 in GF(q)*. Therefore there will be no other orbit of size d, else the equation y^d=1 will have too many roots. Some thought shows that this same orbit is generated by another element in the orbit if that element falls on an index relatively prime to d. So for each d dividing q-1 there are either 0 or phi(d) elements generating the unique orbit of size d in GF(q)*. Every element must generate some orbit, and the equation:
sum_(d divides q-1) phi(d) = q-1leaves just enough room that each orbit must exist - including the orbit of size q-1. Therefore there are generators - in fact, there are phi(q-1) generators.
Burton Rosenberg
September 1, 2001