Algebra, number theory, and graph theory Sample Clauses

Algebra, number theory, and graph theory. In order to understand some of the algorithms and problems to be presented later, some fundamental notions, definitions, and results from algebra and, in particular, from number theory, group theory, and graph theory are required. This concerns both the cryptosystems and zero-knowledge protocols in Chapter 7 and some of the problems to be considered in upcoming Chapter 8. The present subsection may as well be skipped for now and revisited later when the required notions and results come up. In this section, most of the proofs are omitted. Definition 7.2 (Group, ring, and field). • A group G = (S, ◦) is defined by some nonempty set S and a two-ary operation ◦ on S that satisfy the following axioms: – Closure: (∀x ∈ S) (∀y ∈ S) [x ◦ y ∈ S] . – Associativity: (∀x ∈ S) (∀y ∈ S) (∀z ∈ S) [(x ◦ y) ◦ z = x ◦ (y ◦ z)] . – Neutral element: (∃e ∈ S) (∀x ∈ S) [e ◦ x = x ◦ e = x] . – Inverse element: (∀x ∈ S) (∃x−1 ∈ S) [x ◦ x−1 = x−1 ◦ x = e] . The element e is called the neutral element of the group G. The element x−1 is called the inverse element forx. G is said to be a monoid if G satisfies associativity and closure under ◦, even if G has no neutral element or if not every element in G has an inverse. A group G = (S, ◦) (respectively, a monoid G = (S, ◦)) is said to be commutative (or abelian) if and only if x ◦ y = y ◦ x for all x, y ∈ S. The number of elements of a finite group G is said to be the order G and is denoted by |G|. • H = (T, ◦) is said to be a subgroup of a group G = (S, ◦) (denoted by H ≤ G) if and only if T ⊆ S and H satisfies the group axioms. • · · A ring is a triple R = (S, +, ) such that (S, +) is an abelian group and (S, ) is a monoid and the distributive laws are satisfied: (∀x ∈ S) (∀y ∈ S) (∀z ∈ S) : (x · (y + z) = (x · y) + (x · z)) ∧ ((x + y) · z = (x · z) + (y · z)) . · · · A ring R = (S, +, ) is said to be commutative if and only if the monoid (S, ) is commutative. The neutral element group (S, +) is called the zero element (the zero, for short) of the ring R. A neutral element of the monoid (S, ) is called the one element (the one, for short) of the ring R. • Let R = (S, +, ·) be a ring with one. An element x of R is said to be invertible (or a unity of R) if and only if it is invertible in the monoid (S, ·). • A field is a commutative ring with one in which each nonzero element is invert- ible. Example 7.3[Group, ring, and field] • Let k ∈ N. The set Zk = {0, 1, . . . , k − 1} is a finite group with respect to addition modulo k, with...