In this chapter, we are going to study the abstract properties of binary operations.

Algebraic structures known as groups, rings, and Fields are examples of the principle of abstraction: The particulars of the objects are abstracted into a few simple properties. These ideas are central to much of contemporary cryptography, without which secure transactions on the Web and much else in the world of business and finance would not be possible.

Rotating a Square in Space

Image:square2.gif

Suppose that we can pick up the square shown above, rotate it in any way that we want, and then put it back on the black frame. In how many different ways can we put the square back on the frame?

There are eight ways to do it, as shown below.

Image:square8.gif

Let us consider this set of eight motions, called symmetries of the square. We can label each motion and write the set as follows:

We can also combine these motions. We define the operation `*` to mean "first do one symmetry, and then do the next."

=''Examples''=

`` means "first rotate 90˚ clockwise and then 180˚." The result is equivalent to the motion ``.

`` means "first flip horizontally and then rotate 90˚." The result is equivalent to the motion ``.

If `a, b in `, does ` in `? The answer is yes. Indeed, we can create a table showing the results of all possible pairs of motion, one motion completed after the other.

Image:Square_table.gif

In order to talk about these operations and their results (as given in the table above), we need the following formal vocabulary.

If `S` is a set, `S xx S` is the set of all (ordered) pairs of elements of `S`.

::`S xx S = {(a,b)| a in S and b in S}`

=''Exercise''=

If `S` has `n` elements, how many elements does `S xx S` have?

Formally, `` is a function from `` to ``.

::`* : Y_(SQ) * Y_(SQ) rarr Y_(SQ)`

As shorthand, we write `` as "``."

Binary Operations

"``" is called a binary operation on ``.

We define a binary operation in the following way: A binary operation on a set `S` is a function `diamond : S xx S rarr S`.

=''Example''=

The function `f: NN xx NN rarr NN` defined by `` is a binary operation on `NN`.

A binary operation `diamond` on a set `S` is '''associative''' if for all `a,b,c in S, (a diamond b)diamond c = a diamond (b diamond c)`.

=''Examples''=

Is `f: NN xx NN rarr NN` defined by `f(x,y) = xy + y` associative?

::`(ab + b)c + c = a(bc + c) + (bc + c)`?

The answer is no.

Is the operation `*` on the set of symmetries of the square associative? Yes.

A binary operation `diamond` on a set `S` is '''commutative''' if for all `a,b in S, a diamond b = b diamond a`.

Is the operation `*` on the set of symmetries of the square commutative? The answer is no. For example, `R_90 * F_| ≠ F_| * R_90`.

Note that `R_0` is like a null motion. Is this true?

::`AA a in Y_(SQ), a * R_0 = R_0 * a = a`?

Yes. `R_0` is called the '''identity''' of `*` on `Y_(SQ)`.

In general, for any binary operation `diamond` on a set `S`, an element `e in S` such that for all `a in S`, `e diamond a = a diamond e = a` is called an identity of `diamond` on `S`.

The '''inverse''' of an element `a in Y_(SQ)` is an element `b` such that `a * b = b * a = R_0`.

For example, the inverse of `R_90` is `R_270`, the inverse of `R_180` is `R_180`, and the inverse of `F_|` is `F_|`.

Note that every element in `Y_(SQ)` has a unique inverse.

Groups

A '''group''' `G` is a pair `(S, diamond)`, where `S` is a set and `diamond` is a binary operation on `S` such that:

#`diamond` is associative. #Identity: There exists an element `e in S` such that `e diamond a = a diamond e = a`, for all `a in S`. #Inverse: For every `a in S` there is `b in S` such that `a diamond b = b diamond a = e`.

If `diamond` is commutative, then `G` is called a commutative (or Abelian) group.

=''Examples''=

Is `(NN,+)` a group?

::Is + associative on `NN`? Yes.
::Is there an identity? Yes: 0.
::Does every element have an inverse? No.

Hence, `(NN,+)` is ''not'' a group.

Is `(ZZ,+)` a group?

::Is + associative on `ZZ`? Yes.
::Is there an identity? Yes: 0.
::Does every element have an inverse? Yes.

Hence, `(ZZ,+)` is a group.

Is `(Y_(SQ), *)` a group?

::Is `*` associative on `Y_(SQ)`?
::Is there an identity? Yes: `R_0`.
::Does every element have an inverse? Yes.

Hence, `(Y_(SQ), *)` is a group.

Is `(ZZ_n,+)` a group?

::Is + associative on `ZZ_n`? Yes.
::Is there an identity? Yes: 0.
::Does every element have an inverse? Yes.

Hence, `(ZZ_n, +)` is a group.

Is `(ZZ_n*, *)` a group?

::Is * associative on `ZZ_n*`? Yes
::Is there an identity? Yes: 1.
::Does every element have an inverse? Yes.

Hence, `(ZZ_n*, *)` is a group.

=Uniqueness=

We can establish an important property of both identities and inverses: their uniqueness.

''Theorem'': A group has at most one identity element.

''Proof'': Suppose `e` and `f` are both identities of `G = (S,diamond)`.
::Then `f = e diamond f = e`.

''Theorem'': Every element in a group has a unique inverse.

''Proof'': Suppose `b` and `c` are both inverses of `a`.
::Then `b = b diamond e = b diamond (a diamond c) = (b diamond a) diamond c = c`.

=Order=

Here is another important property of a group: A group `G = (S,diamond)` is finite if `S` is a finite set.

Let us define `|G| = |S|` to be the order of the group (that is, the number of elements in the group).

''Question'': What is the group with the least number of elements?

::`G = ({e},diamond)` where `e diamond e = e`.

''Question'': How many groups of order 2 are there?

Image:15_order2.gif

=Generators=

Let's now take a look at generators.

A set `T sube S` is said to generate the group `G = (S,diamond)` if every element of `S` can be expressed as a finite product of elements in `T`.

''Question'': Does `{R_90}` generate `Y_(SQ)`? No.

''Question'': Does `{S_|, R_90}` generate `Y_(SQ)`? Yes.

A single element `g in S` is called a generator of `G = (S,diamond)` if `{g}` generates `G`.

::Does `Y_(SQ)` have a generator? No.

Any `a in ZZ_n` such that GCD`(a,n) = 1` generates `ZZ_n`.

''Claim'': If GCD`(a,n) = 1`, then the numbers `a, 2a, . . ., (n-1)a, na` are all distinct modulo `n`.

''Proof'' (by contradiction):
::Suppose `xa = ya (mod n)` for `x,y in {1,. . .,n}` and `x ≠ y`.
::Then `n | a(x-y)`.
::Since GCD`(a,n) = 1`, then `n | (x-y)`, which cannot happen.

=''Examples''=

There are exactly eight distinct multiples of 3 modulo 8.

Image:15_3_8.gif

Because we hit all numbers when we start with 3, we can say that 3 is a generator for `ZZ_8`.

There are exactly 2 distinct multiples of 4 modulo 8.

Image:15_4_8.gif

Note that 4 does not generate `ZZ_8`.

We can generalize this idea. There are exactly LCM`(n,c)`/`c` = `n`/GCD`(c,n)` distinct multiples of `c` modulo `n` and hence elements `c` with GCD`(c,n) = 1` generate `ZZ_n`.

We now define the order of an element. If `G = (S,diamond)`, we use `a^n` to denote `(a diamond a diamond . . . diamond a)`, for `n` `a`'s.

''Definition'': The order of an element `a` of `G` is the smallest positive integer `n` such that `a^n = e, n > 0`.

''Lemma:'' `a` is a generator of `G` if order`(a) = |G|`.

''Question'': What is the order of `F_|` in `Y_(SQ)`? 2.
''Question'': What is the order of `R_90` in `Y_(SQ)`? 4.

The order of an element can be infinite!

''Example:'' The order of 1 in the group `(ZZ,+)` is infinite.

What if `G` is a finite group. Is the order of any element of `G` finite?

The answer is yes. Consider `a, a^2, a^3, a^4, a^5, . . .`. Since `G` is finite, at some point `a^j = a^k` for some `j < k`. Hence, `a^(k-j) =` identity.

We can say that the order_{`(ZZ_n,+)`}`(c)` = `n`/GCD`(c,n)`. For example, in `ZZ_8`, order(3) = 8 because it generates the sequence 3,6,1,4,7,2,5,0; order(4) = 2 because it generates the sequence 4,0.

=''Example''=

What is order of the group `ZZ_n`*?

::`|ZZ_n`*`| = φ(n)`

Does `ZZ_n`* have generators? In other words, does `ZZ_n`* have an element `a` with order`(a) = φ(n)`?

What are the orders of elements in `ZZ_n`*?

Consider the following case.

::`ZZ_7`* `= {1,2,3,4,5,6}`

::`2^0 = 1`; `2^1 = 2`; `2^2 = 4`; `2^3 = 1`
::`3^0 = 1`; `3^1 = 3`; `3^2 = 2`; `3^3 = 6`; `3^4 = 4`; `3^5 = 5`; `3^6 = 1`

So, 2 generates `{1, 2, 4}`. Hence, it is order 3.
And 3 generates `{1,2,3,4,5,6}`. Hence, it is order 6.

We conclude that 3 is a generator of `ZZ_7`*, but 2 is not.

''Theorem'': There are `φ(n-1)` generators of the group (`ZZ_n`*, *).

For example, for `ZZ_7`*, `φ(7-1) = φ(2*3) = 2`.
::Generators: `3,5`. You can check that `ZZ_7`* = `{1, 2, 3, 4, 5, 6}`has orders, respectively, `1, 3, 6, 3, 6, 2`.

''Theorem'': Let `x` be an element of `G`. The order of `x` divides the order of `G`.

=Subgroups=

We can also consider subgroups. Given a group `G = (S, diamond)`, a subset `S' sube S` forms a '''subgroup''' if `H = (S', diamond)` satisfies the group properties. That is, `S'` is closed under the group operation `diamond`; the identity element of `G` is also in `S'`; and the inverse of every element in `S'` is also in `S'`.

==''Examples''==

For example, `Y_(SQ) = {R_0, R_90, R_180, R_270, F_|, F_—, F_/, F_\\}` has the subgroup `Y_(rot) = {R_0, R_90, R_180, R_270}`.

`ZZ_8`_,even `= {0, 2, 4, 6}` with the + operation is a subgroup of `ZZ_8 = {0,1,2,3,4,5,6,7}`.

Lagrange's theorem gives an important property of subgroups.

''Theorem'': If `H` is a subgroup of `G`, then `|H|` divides `|G|`.

''Fact'': The set generated by any element `x in G` is a subgroup of `G`.

''Corollary'': The order of any element `x in G` divides `|G|`.

Rings

We can define more than one operation on a set. For example, in `ZZ_n`, we can do addition and multiplication modulo `n`. A '''ring''' is a set together with two operations (usually called + and *).

''Definition'': A '''ring''' `R` is a set together with two binary operations + and *, satisfying the following properties:

#`(R,+)` is a commutative group. #`**` is associative. #The distributive laws hold in `R`:
::`(a + b) * c = (a * c) + (b ** c)`
::`a * (b + c) = (a * b) + (a ** c)`

=''Example''=

Do the integers `ZZ` form a ring?

:`(ZZ, +)` is a commutative group.
:`**` is associative.
:`+` distributes over `**`.

Fields

''Definition'': A field `F` is a set together with two binary operations + and `**`, satisfying the following properties:

#`(F,+)` is a commutative group. #`(F-{0},**)` is a commutative group. #The distributive law holds in `F`:
::`(a + b) * c = (a * c) + (b ** c)`

=''Examples''=

Do the integers `ZZ` form a field?

`(ZZ, +)` is a commutative group, but `(ZZ-{0},**)` does not form a group! There are no multiplicative inverses.

`ZZ_p` (for prime `p`) is a field.

`(ZZ_p, +)` is a commutative group.
`(ZZ_p** = ZZ_p-{0},**)` is a commutative group.
The distributive law holds.

The real numbers `RR` form a field.

`(RR, +)` is a commutative group.
`(RR-{0},**)` is a commutative group.
The distributive law holds.

Cryptography

As we saw with the RSA cryptosystem (chapter 14), cryptographic schemes can be based on the presumed computational difficulty of a number theoretic problem.

Let `p` be prime and `g` be a generator for `(Z_p**, **)`.

Note that DH_`p.g``(x)` = `g^x` mod `p` is fast to compute.
DISCRETE-LOG_`p,g``(r)` = `x` means that `g^x` = `r` mod `p`.
No one knows a fast algorithm given a random `r` to compute `x`.

In 1976, Diffie and Hellman took advantage of this asymmetry to come up with a public-key cryptosystem.

Let `p` be prime, and `g` be a generator mod `p`. Alice picks random `x in ZZ_(p-1)` and publishes `g^x` mod `p`. Bob picks random `y in ZZ_(p-1)` and publishes `g^y` mod `p`. Both parties can compute (mod `p`) `(g^x)^y = (g^y)^x` = `g`^{`(xy)` mod `p-1`}.

Eve sees both published strings, but she does not know `x` and `y`. Can she figure out `g^(xy)` mod `p`?

The Diffie-Hellman public-key cryptosystem has an amazing feature. Two people who have never met and have no prior shared secrets can use the system. Without this property, commerce on the net would be impossible.

In a typical implementation, users would agree on a random string `r`. We could then use `r` as our secret key in a more conventional private-key cryptosystem.