Cryptography Lecture Notes 2/21/17
By William McHarg
Euclidian Algorithm:
Find GCD fast:
Theorem: if GCD(m,n)=d
Then there exists integers x and y so that mx+nyd
So the GCD of m,n is a linear combination of m and n
Ex: Use Euclidian Theorem to find x,y
m = 79 n = 19
Find x,y so that mx+ny = 1
79 = 19*4 +3
19 = 6*3 + 1 Stop here because value = 0
3 = 3 * 1 + 0
To find x,y: work backwards
1 = 19 - 6 * 3
3 = 79 - 4 * 19
1 = 19 - 6(79 - 4 * 19)
1 = 19 - 6(79) + 24(19)
So 1 = 25(19) - 6(79)
So x = -6 and y = 25
In general: Work through euclid’s algorithm forward, solve each equation for the remainder. Work backwards substituting the remainder into each equation.
Reduce the equation (mod 79)
1 = 25(19) + 0 (mod 79)
So 19^-1 25 (79)
In general: if we want to find the inverse of a (mod m) use Euclid's algorithm to find x,y so that ax + my = 1 then a^-1 x (mod m)
Ex: find 19^-1 (mod 26) use Euclid’s Algorithm on 19, 26
26 = 1(19) + 7
19 = 2(7) + 5
7 = 1(5) + 2
5 = 2(2) + 1
7 = 26 - 1(19)
5 = 19 - 2(7)
2 = 7 - 1(5)
1 = 5 - 2(2)
1 = 5 - 2(2)
= 5 - 2(7 - 1(5))
= 3(5) - 2(7)
= 3(19 - 2(7)) - 2(7)
= 3(19) - 8(7)
= 3(19) - 8(26 - 1(19))
= 11(19) - 8(26)
So 19^-1 11(mod 26)
When we are working with modular arithmetic we call the number we are working mod the modulus.
And we call all the remainders 0, 1, …, m-1 the residues mod m.
Every int is congruent to exactly one residue mod m.
Given any 2 residues a, b mod m. We can add, subtract, multiple, and maybe divide them. Or have additive and multiplicative identities 0 and 1.
We call any set that we can add, subtract, multiply with additive and multiplicative identities a Ring.
Ex of Rings:
Residues (mod m)
Integers
Real Numbers
Form a Ring of trig functions
Polynomials
Rational Numbers
N x M matrices