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