Transcript CS413Chapter12PowerPointsPart2x

Security in Computing
Chapter 12, Cryptography Explained
Part 2
Summary created by
Kirk Scott
1
• This set of overheads corresponds to the second
portion of section 12.1 in the book
• The overheads for Chapter 12 roughly track the topics
in the chapter
• Keep this in mind though:
• On some topics I simply go over the book’s material
• On other topics I expand on the book’s material in a
significant way
• You are responsible not just for what’s in the book, but
also what’s in the overheads that’s not in the book
2
Book Section 12.1, Mathematics for Cryptography
Subsection Heading: Properties of Arithmetic
• These are the sub-subheadings covered in this
portion of the overheads:
• Inverses
• Primes
• Greatest Common Divisor
• Euclidean Algorithm
• Modular Arithmetic
• Example
• These topics may be covered in a different order
and in more or less detail than in the book
3
Math for Encryption
• 1. Thinking Concretely about Division and
Remainders. The Euclidean Algorithm for
Finding the Greatest Common Divisor.
• 2. Algebraic Background
• 3. Modular Arithmetic and Modular Fields
4
1. Thinking Concretely about Division and
Remainders. The Euclidean Algorithm for Finding the
Greatest Common Divisor.
5
Prime Number, Definition
• Any integer greater than 1 that has only 1 and
itself as factors is prime.
• Historically, the number 1 has occasionally been
treated as a prime number.
• It is certainly true that it only has 1 and itself as
factors.
• It is generally not included in the definition of
primes, not because it fails in some way, but
because it has so many other unique
characteristics, that classifying simply as prime
does not do it justice.
6
Composite Number, Definition
• A number which is not 1 and not prime is
composite.
• In other words, an integer greater than 1
which has factors other than 1 and itself is
composite.
7
Greatest Common Divisor, Definition
• The greatest common divisor is the largest
integer which is a factor of two other integers.
• The notation is usually given as follows:
• Given a and b, positive integers, gcd(a, b) = x is
the largest integral factor of a and b.
• Note that x <= a and x <= b.
8
Relatively Prime, Definition
• Given 2 positive integers, a and b, if the gcd(a,
b) = 1, then a and b are relatively prime.
• Both a and b may be composite.
• If you did a prime factorization of a and b you
would find that they have no prime factors in
common.
9
Finding the gcd(a, b)
• One approach to finding the greatest common
divisor of 2 positive integers:
• Find the prime factorization of each.
• The product of the prime factors they have in
common forms the greatest common factor or
greatest common divisor.
10
Example of Finding the gcd(a, b)
•
•
•
•
For example:
72 = 2 * 2 * 3 * 3
30 = 2 * 3 * 5
The common prime factors of the two
numbers are 2 and 3.
• 2 * 3 = 6 is their greatest common divisor.
11
The Euclidean Algorithm
• This is an algorithm for finding the gcd
• It is iterative in nature
• It is suitable for implementation in a computer
program
• It does not involve finding the prime
factorizations of a and b
12
An Explanation of the Euclidean
Algorithm without Proof
•
•
•
•
•
Let x = gcd(a, b)
Suppose a > b
Suppose you did modular arithmetic:
a % b  remainder r
x also goes into r evenly
13
•
•
•
•
Informally, this is why:
a is a multiple of x
b is a multiple of x
subtract one multiple of x from another and
what’s left should be a multiple of x
• Then gcd(a, b) = gcd(b, r)
14
•
•
•
•
•
•
•
This is iterative; repeat the process
r<b
b % r  new, smaller r1
If x went into b and r, it will go into r1 evenly
The gcd(a, b) = gcd(b, r) = gcd(r, r1)
This will eventually converge to rn = 0
At that point, you can conclude that rn-1 = x
15
A More Formal Explanation of the
Euclidean Algorithm
• Let integers a and b be given.
• Let x = gcd(a, b)
• Without loss of generality, assume that a > b.
Then it is possible to write the following:
• a=m•b+r
16
• a=m•b+r
• Since x = gcd(a, b), then there must be some
values a1 and b1 such that:
• a = a1x, and b = b1x
• Now substitute these expressions for a and b
into the expression relating a and b:
• a1x = mb1x + r
17
•
•
•
•
•
•
•
a1x = mb1x + r
Now solve the expression for r:
r = mb1x – a1x
r = x(mb1 – a1)
Conclusion:
x, the gcd(a, b), is also a factor of r
x goes evenly into r
18
•
•
•
•
•
•
So you know that gcd(a, b) = x goes into r
There are now two intertwined questions:
Is x the gcd(b, r)?
Is the gcd(b, r) = gcd(a, b)?
In other words, is the following true:
gcd(a, b) = x = gcd(b, r)
19
• The way to show this is to consider and
eliminate two cases:
• 1. gcd(b, r) = y is less than gcd(a, b) = x
• 2. gcd(b, r) = y is greater than gcd(a, b) = x
• If you can eliminate theses cases, the
conclusion is that x = gcd(b, r) = gcd(a, b)
20
•
•
•
•
Case 1:
Could this be true? gcd(b, r) = y < x = gcd(a, b).
By definition, gcd(a, b) is a factor of b.
The preceding sequence of steps showed that
gcd(a, b) is also a factor of r.
• Thus, gcd(a, b) goes into both b and r
• This means that gcd(b, r) has to be at least as big
as gcd(a, b)
• In other words, y cannot be less than x
21
• Case 2:
• Could this be true? gcd(b, r) = y > x = gcd(a, b).
• Since y = gcd(b, r), there must be some values b2
and r2 such that:
• b = b2y and r = r2y
• Now go back to the original expression relating a,
b, and r:
• a = mb + r
22
• a = mb + r
• Now substitute the expressions in y for b and r
in the expression relating a, b and r:
• a = mb2y + r2y
• Factoring the previous expression gives:
• a = y(mb2 + r2)
23
• In other words, y is a factor of a.
• y is also a factor of b.
• As a common factor of a and b, y cannot be
greater than gcd(a, b)
24
• Case 1 showed that y = gcd(b, r) is at least as
big as x = gcd(a, b)
• Case 2 showed that y = gcd(b, r) can’t be
greater than x = gcd(a, b)
• Therefore y = gcd(b, r) = x = gcd(a, b)
• Having shown this for the first step, with r, the
same reasoning applies at every step, for ri
25
An Outline of the Iteration
• Given a and b, it is possible using integer division
and modulus to find b and r.
• The process can then be repeated on b and r.
•
• a = mb + r0
gcd(a, b) = gcd(b, r0)
• b = m1r0 + r1
gcd(b, r0) = gcd(r0, r1)
• r0 = m2r1 + r2
gcd(r0, r1) = gcd(r1, r2)
• …
• You stop when you reach a remainder of 0.
26
An Illustrative Example
•
•
•
•
•
•
•
Let a = 72 and b = 30.
72 = 2 * 30 + 12
30 = 2 * 12 + 6
12 = 2 * 6 + 0
a = 72, m =2, b = 30, r0 = 12
b = 30, m1 = 2, r0 = 12, r1 = 6
r0 = 12, m2 = 2, r1 = 6, r2 = 0
The final remainder is 0 and the remainder before that was
6.
• According to the algorithm, gcd(72, 30) = gcd(30, 12) =
gcd(12, 6) = gcd(6, 0)
• gcd(a, b) = gcd(6, 0) = 6 because anything divides 0 and 6 is
the largest divisor of 6
27
Another Example
• Consider the case where a and b are relatively
prime.
• You know their gcd should come out as 1.
• Let a = 17 and b = 6
• 17 = 2 * 6 + 5
• 6=1*5+1
• 5=5*1+0
• The gcd(17, 6) = gcd(1, 0) = 1
28
How Do You Know This Really
Converges to 0?
•
•
•
•
•
Consider the following points:
At every step, rj < ri.
All ri >= 0.
All ri are integers.
Logic tells you that r is eventually going to reach
0.
• That may not be very satisfying.
• There may be a more intuitive argument, but I
won’t pursue that.
29
2. Algebraic Background
30
• Algebras in general are defined in terms of
one or more operators and a set of values
which the operators can be applied to.
• For the purposes of the initial exposition
below, let a single operator be represented by
• and the set of interest be S.
• Within an algebraic system, certain properties
can be defined.
31
Properties of Algebra
• Here are the definitions of some of the
properties of an algebraic system:
• Closure: Given a, b ε S, a • b ε S.
– The result of the operation is also in the set
• Identity: Given some arbitrary a ε S, there is
an i ε S such that a • i = i • a = a.
– The identity gives the element a back.
– For the familiar operations + and * the identities
are 0 and 1, respectively.
32
• Inverse: For some a ε S, its inverse is a-1 ε S
such that a • a-1 = i.
– a and its inverse give the identity back.
– In a regular system of arithmetic over the reals,
note that the additive identity, 0, does not have a
multiplicative inverse
– There’s nothing you can multiply 0 by to get 1
back as a result; you only get 0 back as a result.
33
• The Associative Property: For a, b, c ε S, (a •
b) • c = a • (b • c).
– It doesn’t matter how you group the operands.
• The Commutative Property: For a, b ε S, a • b
= b • a.
– The order of the operands doesn’t matter.
34
• The Distributive Property: Given two
operations on the set, + and *, * distributes
over + if the following holds:
• For a, b, c ε S, a * (b + c) = (a * b) + (a * c).
– In regular arithmetic, multiplication distributes
over addition; addition doesn’t distribute over
multiplication.
– In a two operation system, (the inverses of) the
operations do not have exactly the same
characteristics.
35
Commentary on Alternative Systems,
Commutativity, and the Inverse
• We are accustomed to the way things work with the
familiar arithmetic operations + and *.
• In the real numbers all elements have inverses except
for a multiplicative inverse of 0.
• For example, the additive inverse of 1 is -1 and the
multiplicative inverse of 7 is 1/7.
• Depending on the set of values and the operation of a
system, some values may not have inverses.
• If you restrict yourself to the set of integers, no values
except 1 and -1 have multiplicative inverses.
• If you restrict yourself to the set of positive integers,
there are no additive inverses.
36
• Other systems can have even stranger
characteristics.
• In the reals, the inverse is commutative
• a • a-1 = a-1 • a = i .
• In some systems the commutative property
may not hold for inverses.
• Elements of the set could have a left inverse
which was not an inverse on the right, and
vice-versa.
37
Algebraic Structures
• The algebraic structures will seem obscure at
the moment.
• What good are they?
• It turns out that significant encryption systems
are based on modular arithmetic
• Modular arithmetic is not like regular
arithmetic
• It behaves differently
38
• You will eventually see that modular
arithmetic embodies one of the algebraic
structures that will be presented.
• The behavior of modular arithmetic IS the
behavior of that algebraic structure.
• A sequence of structures will be presented.
• The definitions of the later structures are
stated in terms of the definitions of the earlier
ones.
39
•
•
•
•
•
There are three basic algebraic structures:
Groups
Rings
Fields
To cut to the chase, modular arithmetic embodies an
algebraic field
• In order to understand what a field is, you have to
proceed through the definitions of groups and rings
• These algebraic structures will be presented below.
40
Algebraic Groups
• An algebraic group consists of a set S
• The group has one operation, say •
• The set and operation have these 4
properties:
– Closure under •.
– Identity under •.
– An inverse for all elements of the set under •.
– Associativity under •.
41
Commentary on Groups
• Notice that commutativity is NOT one of the
properties of a group.
• There are groups which are commutative and it is
generally easier to think of an example of a
commutative group than a plain group.
• For instance, consider the positive and negative
integers under addition.
• This satisfies all four of the requirements for a
group.
• In addition the commutative property holds.
42
A Biographical Interlude
• From Widipedia:
• “Niels Henrik Abel (5 August 1802 – 6 April
1829) was a noted Norwegian
mathematician[1] who proved the impossibility
of solving the quintic equation in radicals… he
invented (independently of Galois) an
extremely important branch of mathematics
known as group theory…”
43
• From Wikipedia, continued:
• “Mathematician Felix Klein wrote about Abel:
• ‘…I will not sound absurd if I compare his kind
of productivity and his personality with
Mozart's…’”
44
• Commutative groups are known as abelian
groups in his honor.
45
Matrix Algebra: A System that Differs
from the Reals
• What follows is not a full exposition of the
questions of commutativity and inverses.
• It is simply an illustration of the fact that you
have encountered mathematical constructs
where not all of the familiar rules of algebra in
the integers or reals apply.
• Matrix algebra has characteristics that differ.
46
• Let A be an m x n matrix.
• Let B be an n x p matrix.
• Let the • represent standard matrix
multiplication.
• Then A • B is a well defined operation because
A has the same number of columns as B has
rows.
47
• On the other hand, A • B ≠ B • A because B •
A is not even a valid product, assuming that p
≠ m.
• Thus, in general, matrix multiplication is NOT
commutative.
• It is commutative only in the special case of
square matrices.
48
• The zero matrix of any size has no inverse.
• A non-zero matrix might also have no inverse.
• A given non-zero matrix might also have an
inverse on one side but not the other.
• Examples will be given.
• If the matrix is not square, even if it had
inverses on both sides, those inverses couldn’t
be the same because they would have
different numbers of rows and columns.
49
• First of all, consider any zero matrix such as
the following:
 0 0


 0 0
• There is no 2 x 2 matrix that it can be
multiplied by to arrive at the identity:
 1 0


 0 1
50
• The preceding result is not surprising.
• It is the way things work in a two operation
system, as already noted for the reals.
• The additive identity does not have a
multiplicative inverse.
51
• At this point we’re talking about groups, which
just have the one operation (multiplication in
this example)
• That the 0 matrix is the additive identity for
matrices is not directly relevant
• However, it’s not an accident that things work
out this way
52
• Now consider a matrix where the rows and
columns are linear combinations of each
other:
 1 2


 2 4
• An inverse would be of this form:
a b


c d
53
• For the inverse to work, these equations,
among others, would have to be satisfied:
• a + 2c = 1
• 2a + 4c = 0
• Multiply the top equation by 2 and you get:
• 2a + 4c = 2
• This system of two equations is inconsistent,
so no inverse of the matrix can exist.
54
• If A is m x n, a right hand inverse matrix of A,
say A1-1, has to be n x m, and the product A •
A1-1 would give Im, the square identity matrix
with dimensions m x m.
• A left hand inverse matrix of A, A2-1, has to be
n x m, and the product A2-1 • A would give In,
the square identity matrix with dimensions n x
n.
55
• Now consider this matrix:
1 1


 1 2
 2 1


• You can verify that it has this unique left hand
inverse:
1 
1  2

3
3
1 1
2 
3
3

56
• It is easy to see that the left hand inverse is
not the right hand inverse.
• It is not hard to show that the equations for a
right hand inverse for this matrix are
inconsistent, meaning that one doesn’t exist.
57
• We have not said what kind of algebraic
structure matrix algebra is.
• That, specifically, isn’t important to us.
• Matrix algebra was brought up for this reason:
• It reminds you that you have encountered
algebraic systems different from the reals.
58
• In particular, commutativity, identities, and
inverses may are an issue with matrix algebra.
• Keep in mind the defining characteristics of a
group, which are repeated on the following
overhead.
59
• An algebraic group consists of a set S
• The group has one operation, say •
• The set and operation have these 4
properties:
– Closure under •.
– Identity under •.
– An inverse for all elements of the set under •.
– Associativity under •.
60
• Take the set S consisting of all of the integers,
and the arithmetic addition operation for
example
• This set and operation would satisfy all of the
requirements for being a group.
• Incidentally, it would also satisfy
commutativity, which would make it an
abelian group.
61
Algebraic Rings
• An algebraic ring consists of a set S
• The ring has two operations, say + (which we will
call addition) and * (which we will call
multiplication)
• The set and operations have these 4 properties:
–
–
–
–
Under addition, S is an Abelian group.
S is closed under multiplication.
Multiplication is associative.
Multiplication distributes over addition.
62
• The set S, consisting of all of the integers, and the
arithmetic operations + and * would satisfy the
requirements for an algebraic ring.
• Notice that the properties of a ring do not include
inverses under the multiplication operation.
• Except for the identity element 1, which is its own
inverse, the integers don’t contain multiplicative
inverses.
• Since this is not required, this is still a ring.
63
• For our purposes the ring is an intermediate
structure.
• We are more interested in the structure that
follows, the algebraic field.
• Its definition relies on knowing both what a
group and a ring are.
64
Algebraic Fields
• An Algebraic Field consists of a set S with two
operations, addition (+) and multiplication (*)
and the following properties:
– S is a ring.
– With the exception of the 0 element (the additive
identity), which does not have a multiplicative
inverse, S satisfies the requirements for an Abelian
group under multiplication.
65
• The definition on the previous overhead is the
compact one.
• It depends on your remembering the
definitions of a group and a ring.
• A field can also be defined by listing all of its
basic properties.
• This is done on the following overheads.
66
• A field consists of a set S with two operations,
+ and *
• The operation + has these properties in S:
• Closure
• Associativity
• Commutativity
• Identity
• An inverse for all elements
67
•
•
•
•
•
•
The operation * has these properties in S:
Closure
Associativity
Commutativity
Identity
With the exception of the additive identity (0)
there is an inverse for all elements
68
• The following relationship holds between the
operations * and +:
• * distributes over +
• Note: I checked with one of the
mathematicians
• There is a subtlety here
• Technically it may be more correct to say that
the additive identity does not have to have a
multiplicative inverse
69
• You may have heard the expression “the field
of real numbers”.
• This means that the real numbers form an
algebraic field.
• The properties given above correspond to the
everyday characteristics of arithmetic with
real numbers that we are used to.
70
What About No Inverse for 0?
• You’re so used to the fact that 0 doesn’t have
a multiplicative inverse, you probably haven’t
thought about it before.
• This is not an entirely foreign realm of thought
though.
• Consider this, which you have doubtless
thought about before:
• 0 is the one number that you are not allowed
to divide by.
71
• Subtraction and division don’t appear in the
definitions of algebraic structures.
• Subtraction is the inverse of addition and
division is the inverse of multiplication.
• In other words, subtraction of x is
accomplished by adding the additive inverse
of x.
• Division by x is accomplished by multiplying by
the multiplicative inverse of x.
72
• Why can’t you divide by 0?
• Because, although you can write the expression ‘1/0’,
the thing that this is supposed to express is defined not
to exist.
• 0 does not have a multiplicative inverse.
• Therefore, it’s impossible to multiply quantities by the
multiplicative inverse of 0.
• Therefore ‘dividing by 0’ is impossible.
• To say you’re going to divide by 0 is meaningless,
because by definition the set S does not contain an
element that makes this possible.
73
More Commentary on the Lack of a
Multiplicative Inverse for the Additive Identity
• You might ask, could you come up with an
algebraic structure with two operations where
the additive identity had a multiplicative
inverse?
• The answer is yes
• It might be useful for the sake of better
understanding what’s going on to consider
such a system
74
• In the interests of having descriptive names,
let these conventions be used:
• The multiplicative identity will be written
multident
• The additive identity will be written addident
• The multiplicative inverse will be indicated by
a superscript -1, for example, x-1
• Consider the sequence of steps on the
following overheads
75
• x = x + addident
• Now suppose that addident does have an
inverse
• x * addident-1 = (x + addident) * addident-1
• x * addident-1 = x * addident-1 + addident *
addident-1
• x * addident-1 = x * addident-1 + multident
76
• This was the ending equality:
• x * addident-1 = x * addident-1 + multident
• This would hold true if the multident equalled
addident
• So the assumption that addident-1 existed led
to the conclusion that:
• multident = addident
77
• It is possible to come up with an example
where this is true.
• Suppose S = {0}
• 0+0=0
• 0*0=0
78
• Going back to the definition of a field, you
could either say that this is the world’s
smallest field—so small that it’s useless
• Or you could decide that this illustrated
something that you didn’t want to deal with
• In that case you would just say that
something isn’t a field if the additive identity
has a multiplicative inverse
79
Why Are Fields Important?
• The concept of an algebraic field is important
because a lot of advanced cryptography is based
on it.
• In the next section modular arithmetic will be
discussed and the claim will be asserted that
modular arithmetic leads to an algebraic field.
• RSA encryption is based on the problem of
finding multiplicative inverses in modular fields
• You need to grasp the algebra in order to know
whether inverses exist and what the algorithms
might be for finding them.
80
3. Modular Arithmetic and Modular
Fields
81
Definition of Modulus
• Modular arithmetic means finding the
remainder when one integer is divided by
another.
• The following statements are equivalent in
describing the operation of modulus for
integers a, b, c, and n:
• a mod n = b
• a%n=b
• a=c*n+b
82
• You have already encountered modular
arithmetic applied to cryptography in a very
simple way.
• If the letters from a to z are represented by
the integers from 0 to 25, Caesar’s cipher can
be expressed using modular arithmetic:
• c = (p + 3) mod 26
83
• It is also possible to devise ciphers of this
form:
• c = (p * 3) mod 26
• I assert without proof that the cipher above
works OK.
84
• However, consider the following cipher:
• c = (p * 2) mod 26
• The integer 0 stands for the letter a and the
integer 13 stands for the letter n.
• Under this scheme they both encode to 0, or a.
• This is a collision.
• These kinds of collisions happen all the way
through the scheme.
• 1 stands for b and 14 stands for o.
• Both would encode to 2, or c, another collision.
85
• These collisions provide an entry point for
asking algebraic questions about modular
arithmetic.
• I observe that 3 and 26 are relatively prime
and that 2 and 26 are not.
• Could this be the basis for the success of one
of the schemes and the failure of the other?
• This question won’t be answered right now.
86
Continuing the Exploration of Modulus
• a mod n = b
• By definition b is the remainder upon integer
division by n.
• This means that 0 <= b < n.
• b is an element of the integral range [0, n)
• Given some finite n, the number of different
values that b can take on is finite.
87
• a mod n = b
• If a can be taken from among all the integers
without restriction, then there is an infinite set of
values a for which the modulus n is b.
• Another way of saying this is that the operation
modulus n divides the set of integers into n – 1
equivalence classes, each of which is infinite.
• For a given equivalence class, each of its
elements mod n gives the same value b.
88
The Definition of Equivalence Under
Modulus
• “x and y are equivalent modulus n” can be
expressed using this notation:
• x ≡n y
• This means:
• (x mod n) = (y mod n)
• In other words, x and y are in the same one of
the n – 1 equivalence classes defined by
modulus n.
89
•
•
•
•
•
•
•
•
•
The following is also true:
x ≡n y ↔
(x – y) = kn for some integer k
That is, the difference between any two elements of a
modular equivalence class is an integer multiple of n.
In case this isn’t clear, consider the following:
x = cn + b and y = dn + b for some c and d
Then subtract both sides of the equations from each other:
x – y = (c – d)n
In other words, k = c – d, and the difference between x and
y is indeed a multiple of n.
90
Modulus and Algebraic Fields
• What does any of this have to do with the presentation
of the algebraic structures in the previous section?
• Given some prime integer n.
• Given the set S = {0, 1, 2, …, n – 1}.
• Given an operation denoted “+” defined as normal
integer addition modulus n.
• And given an operation denoted “*” defined as normal
integer multiplication modulus n.
• This set of components forms an algebraic field
known as a modular field.
91
• A complete demonstration of the fact that this
is true will not be given at this point.
• The required conditions are listed on the
following overheads
• Most of the conditions are easily met
• The crux of the use of modular fields for
encryption is whether and how one of the
conditions in particular is met
92
• A field consists of a set S with two operations, + and *
• The operation + has these properties in S:
• Closure—add any two non-negative integers and you get a
non-negative integer—mod n puts you back in [0, n – 1],
namely S
• Associativity—additive associativity works in a modular
field because it works for addition of the integers in general
• Commutativity—same as above
• Identity—0 is still the additive identity
• An inverse for all elements—for any k in the field, add k + (n
– k) = n, mod n gives 0
93
• The operation * has these properties in S:
• Closure—multiply any two non-negative
integers and you get a non-negative integer—
mod n puts you back in [0, n – 1], namely S
• Associativity—multiplicative associativity
works in a modular field because it works for
multiplication of the integers in general
• Commutativity—same as above
• Identity—1 is still the multiplicative identity
94
• With the exception of the additive identity (0)
there is an inverse for all elements
• 0’s lack of a multiplicative identity is not
controversial
• What is of interest is the multiplicative inverse
of all of the other elements
95
• The questions are:
• Does an arbitrary element x have a
multiplicative inverse?
– The answer is yes.
• If so, under what conditions?
– The answer is, if n is prime.
• If so, how do you find it?
– This remains to be seen.
96
• This is the last condition for a field:
• The following relationship holds between the
operations * and +:
• * distributes over +
• Again, this property holds because it holds for
regular multiplication and addition of integers
• You do the arithmetic and take the modulus at
the end
97
An Example of a Modular Field
• Suppose you choose n = 5, as your prime number.
• The set S = {0, 1, 2, 3, 4}.
• If addition is defined as addition mod 5, you can write
a simple addition table for the set:
•
• + 0
1
2
3
4
• 0 0
1
2
3
4
• 1 1
2
3
4
0
• 2 2
3
4
0
1
• 3 3
4
0
1
2
• 4 4
0
1
2
3
98
• You can verify all of the entries in the table, but
just a few should illustrate the general idea:
• (3 + 4) mod 5 = (7) mod 5 = 2
• It is true that in doing the arithmetic in this way,
we make use of the value 7.
• 7 is not an element of the set, but this is not a
problem because 7 is not the final answer.
• Speaking algebraically, the key property
illustrated by this is closure, a property needed
for the structure.
99
• You might also ask, if this is the table for the
addition operation, is it clear that every
element in S has an additive inverse?
• Take this for example:
• (2 + 3) mod 5 = (5) mod 5 = 0
• This looks a little strange because the additive
inverses are not negative.
100
• There are no negative elements in the field in
the sense that the integers or the reals have
negatives.
• However, by definition 2 and 3 are additive
inverses of each other.
• You can quickly confirm that every element
has an additive inverse by observing that each
row and each column in the addition table
contains one (and only one) zero element.
101
• A more complete review of the algebraic properties of
modular fields will come shortly, but first, it’s useful to
take a look at a multiplication table.
• For n = 5 you get:
•
• * 0
1
2
3
4
• 0 0
0
0
0
0
• 1 0
1
2
3
4
• 2 0
2
4
1
3
• 3 0
3
1
4
2
• 4 0
4
3
2
1
102
• Again, taking a few example illustrates the
idea:
• (3 * 4) mod 5 = (12) mod 5 = 2
• (2 * 3) mod 5 = (6) mod 5 = 1
• Observe that the value 1 is the multiplicative
identity, and the second example illustrates
the fact that 2 and 3 are multiplicative
inverses of each other.
103
• It is a coincidence the same values, 2 and 3,
are both additive and multiplicative inverses in
this example.
• You can also observe in the table that 0 does
not have a multiplicative inverse.
• You can also observe that 1 appears once in
every other row and column, indicating that
each non-zero element of the field has one
and only one multiplicative inverse.
104
• In passing it’s possible to notice two things
about the multiplication table:
• It’s symmetric
• Every row and every column contains exactly
one occurrence of each of the values of S.
• You could also state this by observing that
each row and each column is a permutation of
S.
105
• This is a momentary detour, but hopefully it will also give
some insight into what is going on.
• Consider the multiplication table mod 4.
• Keep in mind that the claim was made that if n is prime,
you get a field.
• The implication was that if n is composite you don’t.
•
• * 0
1
2
3
• 0 0
0
0
0
• 1 0
1
2
3
• 2 0
2
0
2
• 3 0
3
2
1
106
• Notice that the row and column for element 2
do not contain a 1.
• In other words, 2 does not have a
multiplicative inverse in this structure.
• It is not a coincidence that 2 is a factor of 4.
• Many other little discoveries might be lurking
here, but the absence of an inverse for one of
the elements is enough to confirm that the
structure is not an algebraic field.
107
The Properties of a Modular Field in
Mathematical Notation
• Associativity:
• (a + (b + c)) mod n = ((a + b) + c) mod n
• (a * (b * c)) mod n = ((a * b) * c) mod n
• Commutativity:
• (a + b) mod n = (b + a) mod n
• (a * b) mod n = (b * a) mod n
108
•
•
•
•
•
•
Distributivity:
(a * (b + c)) mod n = ((a * b) + (a * c)) mod n
Identities:
(a + 0) mod n = (0 + a) mod n = a
(a * 1) mod n = (1 * a) mod n = a
109
• Inverses:
• This is purely notation:
• An additive inverse, -a, such that (a + (-a))
mod n = 0 exists for all a.
• We know in fact that the arithmetic value of
the inverse “-a” is not negative a in the reals, a
value that does not exist in S, but is (n – a).
110
• This is also notation:
• A multiplicative inverse, a-1, such that (a * (a1)) mod n = 1 exists for all a except 0.
• We know in fact that the arithmetic value of
the inverse “a-1” is not 1/a in the reals, a value
that does not exist in S.
• It is not clear at this point how to find the
inverse.
• Its algebraic properties will be of interest.
111
• Modular arithmetic also has an additional
property.
• This is not a field property, simply a
computational property that might be useful
when doing modular arithmetic.
• The property is called reducibility
112
• Reducibility means that taking the modulus of
some expression “distributes” over its parts.
• You can apply modulus to subparts of
expressions in order to simplify them
• Then you can find the modulus of the
combined results rather than having to
evaluate the whole expression and then find
the modulus.
113
• In order to show that this is true for the addition
operation, consider the following:
• a mod n = ra ↔ a = cn + ra
• b mod n = rb ↔ b = dn + rb
• Consider what happens when you evaluate the whole
expression (a + b) first:
• (a + b) mod n
• = ((cn + ra) + (dn + rb)) mod n
• = (cn + dn + ra + rb) mod n
• = (n(c + d) + (ra + rb)) mod n
• = (ra + rb) mod n
114
• The expression (ra + rb) mod n matches what you
would get if you applied modulus to the parts of
the expression first:
• = ((a mod n) + (b mod n)) mod n
• By the way, if (ra + rb) < n, then the final result
would simply be (ra + rb).
• A general statement of reducibility under
addition is the following:
• (a + b) mod n = ((a mod n) + (b mod n)) mod n
115
•
•
•
•
•
•
Reducibility also applies under multiplication.
(ab) mod n
= ((cn + ra)(dn + rb)) mod n
= (cndn + cnrb + radn + rarb) mod n
= (n(cdn + crb + rad) + rarb) mod n
= (rarb) mod n
116
• The expression (rarb) mod n matches what you
would get if you applied modulus to the parts
of the expression first:
• = ((a mod n)(b mod n)) mod n
• A general statement of reducibility under
multiplication is the following:
• (ab) mod n = ((a mod n)(b mod n)) mod n
117
The End
118