Transcript simple algebra

Simple modern algebra
Groups, rings, and fields
Modular arithmetic
Euclid’s algorithm
Polynomials and Galois multiplication
Conventional crypto - Noack
Elementary terms and notation
Set – a collection of objects – not otherwise defined
in naïve set theory
Correspondence – can be one-to-one or many-toone or one-to-many
Common symbols

Belongs to – is a member of

For all

There exists (at least one)

Not equal
Conventional crypto - Noack
Common relationships and definitions
Equality – relationship is an equality relationship if:
Reflexive
a=a
Transitive
a = b and b = c imply a = c
Symmetric
a = b implies b = a
Objects do not need to be equal numerically to satisfy an equivalence
relationship – example, similar triangles
Closure
a,b  S implies a  b  S
Associativity a  (b  c) = (a  b)  c – can be written a  b  c
Identity
e  S such that a  S e  a = a, a  e = a
Inversea  S a’  S such that a’  a = e, a  a’ = e
Commutativity a,b  S a  b = b  a
Distributivity a(b + c) = ab + ac
This is notational, the two operations are + and implied * even though they are
not necessarily numerical addition or multiplication – examples are Boolean
Conventional crypto - Noack
The hierarchy from group to field
Group
Set (S) and operation () over S
Satisfies closure, associativity, identity (e) and inverse (a’)
Also cyclic group if every element is a power of some possibly unique element
Abelian group
Group with commutativity
Ring
Set with two operations called addition (+) and multiplication () or (*)
Identity is 0, inverse is -a
Abelian group under addition
Satisfies closure, associativity, distributivity (* over +) for multiplication
Integral domain
Ring with identity (1) and no zero divisors
Field
Integral domain with defined inverse (a-1)
Conventional crypto - Noack
Some notation and examples
Common numeric sets are called
Z (integers), Q (rationals), R (reals), C (complex)
Common subsets
Z + (positive), Z* (nonzero),Zp`{0, 1, … p-1}
Examples
Z is a group under +, Z + is not (why)
Book says Z + is an infinite cyclic group generated by 1 and + (why
isn’t this true)
Definitions for division and divisibility
b|a means a = mb for some c  Z and b  Z* , meaning b divides a
Also for any a  Z and n  Z + , a = cn + r, with r  Zn and c  Z
r is called the residue or remainder
Conventional crypto - Noack
Modulo definition and operations
Definition of a mod n
The remainder in a = cn + r
Properties
a = b mod n means n|(a-b) the equal sign followed by mod means modulo
equality.
Modulo equality is an equality relationship
a mod n mod n = a mod n
Addition, subtraction, and multiplication, but not division mod n carry over into
modular arithmetic
Division-like issues depend on whether n is prime
Test yourself
What algebraic structure does Zn under under addition and multiplication
modulo n form? – ring, integral domain, field?
What is –a in modulo arithmetic
Under what conditions does ab=ac mod n imply b=c mod n?
Conventional crypto - Noack
Euclid’s algorithm
This ancient algorithm;
Finds the gcd of two integer-like quantities
Euclid (365BC?-275BC?) worked in Alexandria and
wrote the Elements at about age 40
The algorithm itself
gcd (a,b) = max(k such that k|a and k|b), k  Z +
and a,b  Z *
based on repeated application of gcd (a,b) = gcd
(b,a mod b)
It is easy to prove it terminates in 2 log2 steps.
Proof is slightly indirect –
Can be used with polynomials and also to find
multiplicative inverses in finite fields
Conventional crypto - Noack
442
286
286
156
156
130
130
26
26
0
Polynomials
Polynomial in X with coefficients in some field
anXn + an-1Xn-1 + an-2Xn-2 + … a0X0
Defined operations
Addition – coefficient by coefficient addition – the coefficients remain in the
same field
Multiplication by a scalar – multiply the coefficients by the scalar
Multiplication of two polynomials – the high-school method
Division – the high-school method – note that A(X)/B(Z) is really A(X) mod B(X)
and is “smaller” than B(X)
gcd exists and is found by Euclid’s algorithm
Some interesting equivalences
Polynomial – array
Polynomial in Z2 – binary register contents – bit sequence
Polynomial in Zn – positional representation of number in base n
But note that the numeric addition and multiplication algorithms are not the
standard polynomial operations
Conventional crypto - Noack
Galois field multiplication
Motivation
We need another invertible operation over Zp where p = 2n
Ordinary multiplication in a non-prime sized field doesn’t result in a
unique inverse
Galois fields with size 256 are easily constructed and are used in a
number of block encryption algorithms
Motivation for putting the rest of this on the board
Try doing equations in PowerPoint
Conventional crypto - Noack