Number Theoretical Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 34

o: A × B → C

to mean that the operation acts onpairs ofobjects, one from A and one from B, and will act onthem somehow
to return a result from the set C. In a shorter hand, this can also be written as a b = c , where a is an element

of A , b is from B , and c is from C .
These operations can be very diverse. For example, say we have a set of people (P = {Tom, Sara}), a set of
chairs (C = {Stool, Recliner}), and a set of emotions (E = {Happy, Sad}). We will use the symbol ⊕ for the
operations. We could have the operation define a relationship between the objects, such as the fact that a person
from P has an emotion from E toward an object in C, defined abstractly as ⊕ : P × C → E . We can define the
fact that Mary is Happy to sit in the Recliner, by stating that Mary ⊕ Recliner = Happy.
If this seems too elementary, then don't worry — things will get complicated soon enough.
Asaspecialcase,ifwehavethatoperationconsistofoperationsontwoobjectsfromthesameset,andchurn-
ing out an element of that same set (so that : A × A → A , for example), then we are getting somewhere. We
want a few properties to be satisfied for these operations to be useful. First, we want to have an identity element
(say, e ) — where any operation involving, say, a and the identity element gives us back a. For example, if we
had addition as the operation, then a + e = a, and for addition we have the identity 0, as 0 plus anything is that
anything. For multiplication, the identity is 1.
We want two more properties: inverse elements and associativity . For every element, we want to have an
opposite, or inverse ,element so that when the two are operated on together, the result is e, the identity. With
integer addition, 3 and -3 are inverses. Integers with multiplication don't have this property — for example,
there is no inverse of 1/2.
Associativity is merely the property that, given three elements (say, a, b, c), we have the equality
( a + b ) + c = a + ( b + c )
meaning that it doesn't matter in which order we perform two simultaneous operations. Addition and multiplic-
ation of integers both satisfy this property. Subtraction and division do not, though, since (1 - 2) - 3 = -1 - 3 =
-4 and 1 - (2 - 3) = 1 + 1 = 2, which are clearly not equal.
If we have a set with an operation with all three properties, then they are both collectively called a group,
and would be written as a pair, ( A , ) or ( + 1). If we have an operation on a group ( A , ), and any two ele-
ments from A (say, a and b) satisfy a + b = b + a, then it is called a commutative group ,or an abelian group.
There is just one more consideration to make for an operation to be valid. The operation needs to be well-
defined; we cannot have a valid group of ( , ÷), since 1 ÷ 2 = 0.5, which is not an integer, and therefore does
not qualify as a valid operation on the integers.
Two more definitions: If we have two operations, like addition and multiplication together, then we have
some other structures. A ring is where we have two operations on a set, say ( A , +, ×). In the ring, ( A , +) must
form an abelian group, while the second operation (usually multiplication) has, at least, the property of associ-
ativity, although it need not have an identity or inverses for any elements. For the integers, we can have a ring (
, +, ×), since the addition property is abelian, but we don't have as strict rules on ×.
Finally, if we have aring ( A , +, ×), and furthermore have every element of A (except the additive identity,
usually 0) form an abelian group under × , then this ring is a field. This means that we do have to have an
identity and multiplicative inverses; therefore ( , +, ×) is not a field. However, ( , +, ×) is a field, since every
element (except 0) will have an inverse.
A particularly interesting kind of field to cryptologists is the finitefield, where the underlying set has a finite
number of elements. We could, of course, have counterintuitive definitions, such as to define a new finite field,
say, (A, ⊕ , ), and A = { π, e }. We can then define the rules as being