Encryption-Number Theory

Euclid’s Algorithm

Purpose-> To find the greatest common divisor (gcd) of two numbers. Euclid’s algorithm is the most efficient for finding gcd’s with numbers "a" and "b" both greater than zero.

    1. General Form:

    2. a=bq+r1 (where "q" is the quotient and "r" is the remainder)

    3. b=r1q2+r2

    4. r1=r2q3+r3

    5. Repeat this procedure until the remainder is equal to zero.

    6. The last non-zero remainder is the gcd of "a" and "b."

Example:

    1. Let a=405 and b=63

    2. 405=63(6)+27

    3. 63=27(2)+9

    4. 27=9(3)+0

    5. The gcd of 405 and 63 is the last non-zero remainder, so gcd=9.

 

Why does Euclid's Algorithm work?

    1. the remainders will decrease until they reach zero

    2. the gcd's are all the same

    3. Proof: Show that every divisor of (a,b) is a divisor of (b,r).

      4. Let "x" be a common of "a" and "b"

      a=kx b=lx

      substitute into a=bq+r

      kx=lxq+r ó r=(k-lq)x ó "x" divides "r"

      this means that every divisor of "a" and "b" divides "r"

    4. Proof: Now show that every divisor of (b,r) is a divisor of (a,b).

      5. b=yp r=ys

      a=bq+r ó a=ypq+ys ó a=y(pq+s) ó a=(integer)y ó a=yz

      so all divisors of "b" and "r" also divide "a" ó the greatest members of each set are the same

    5. Proof: Show that rn+1=(rn,rn+1)

    6. Proof: rn=rn+1q ó gcd of (rn,rn+1) ó "rn+1" divides (rn,rn+1) and no bigger number divides both so "rn+1=(rn,rn+1)"

 

Diophantine Equations

Goal->To solve or show no integer solution(s) to the equations:

i. ax+by=1 ii. ax+by=k

Theorem #1-> The equation ax+by=(a,b) -as in gcd- always has integer solutions.

Theorem #2-> ax+by=k has integer solutions if and only if (a,b)/k

In order to find these integer solutions we use Euclid's Algorithm backwards.

Example: find integer solutions to 56x+72y=8

Euclid's Algorithm Procedures: (72,56)

72=56(1)+16

56=16(3)+8

16=8(2)+0

Backwards: 8=56-16(3)

8=56-3(72-56)

8=56(4)+72(-3)

x=4 and y=-3

Modular Arithmetic

Definition-> aº b(mod n)

ó a-b=kn for some k

ó a-b is divisible by n

Example: 5º 2(mod 3)

5-2=3(1)

Definition-> [x] in mod n ó {yú xº y(mod n)}

Example in mod 5 of the equivalence class [3]

[3]=?

[3]={…3, 8, 13, 18,…}

Definition of Z5

[0] [1] [2] [3] [4]

Z5 can also have multiplication and addition. Multiply and add the numbers as you would normally do and assign the solution to the correct equivalence class.

Example: [3]Ä[4]=[3x4]=[12]=[2]

Multiplicative Inverses

For Zn if n=p, a prime number, then all multiplicative inverses exist, and if "x" and "y" are not equal then [x]Ä[y] is not equal zero.

Proof: if n=p all numbers in Zp have multiplicative inverses

Let "x" be any member of Zp. We want to show that there is always a "y" such that [x]Ä[y]º k(mod p)

xy-1=kp for some k

xy-kp=1

gcd=1

Mersenne Primes

A Mersenne prime is any prime number of the form p=2n-1. Not all of these numbers are prime though. By using these primes in the formula 2n-1(p) you are able to get perfect numbers whose factors excluding itself add up to the same number. Two of these numbers are 6 and 28.