Theorems Flashcards
Theorems: Fast Exponentiation
(a) What does it solve?
(b) What are the steps?
(a) Solves mod problems like 5^1003 mod 17
(b) Steps:
- Get the binary number of 1003
- Follow sub steps:
i.e. for a mod N = 5 mod 17
x^1 = a mod N = a1
x^2 = (a1)^2 mod N = a2
x^4 = (a2)^2 mod N = a3
x^8 = (a3)^2 mod N = a4
….
Continue to match binary number 1003
- Multiply a1 - a4, simplifying as you go
if a3*a4 mod 17 can be simplified to b1, then you can replace a3 and a4 by b1:
a1 x a2 x b1 mod 17 - Get mod
Theorems: Fermat’s Little Theorem
(a) What does it solve?
(b) What are the steps?
(a) Solves mod problems like 5^1003 mod 17 if the number we’re mod-ing to is a prime number
(b) Steps:
if p is a prime number, then for any integer a not divisible by p (a is relatively prime to p), the following congruence holds:
a^(p-1) === 1 (mod p)
Theorems: Euclid’s Algorithm
(a) What does it solve?
(b) What are the steps?
(a) Helps find the greatest common divisor of 2 positive integers
(b) Steps:
Recursively follow:
gcd(x, y) = gcd(x mod y, y)
where x >= y > 0
Theorems: Extended Euclid Algorithm
(a) What does it solve?
(b) What are the steps?
(a) Helps to computes inverses
(b) For problem: x^-1 mod N
Steps:
1. Work our way down using gcd. if gcd(x, N) = 1 then x^-1 mod N exists
2. Work our way back up using d = x * alpha + y * beta
Theorems: Euler’s Totient Function
(a) What does it solve?
(b) What are the steps?
of prime numbers = 7 - 1 = 6
(a) Helps determine count of relatively prime numbers a given number has
(b)
If the number is prime:
count of relatively prime numbers = p - 1
i.e. if n = 7
= 7 - 1
= 6
If the number is NOT prime:
count of relatively prime numbers = (p - 1)(q -1)
this assumes that p and q are prime and that N = p * q
For 143
= (p - 1) (q - 1)
= (13 - 1)(11 - 1)
= 12 * 10
= 120
Theorems: Fermat’s Test
(a) What does it solve?
(b) What are the steps?
(a) Check if number is prime or not
(b) Fill in formula:
z^(r-1) where r is the number to check and z are all numbers between 1 and r - 1
i.e. Is 13 a prime number? We’ll choose a random numbers for z:
z^(r - 1) === 1 mod r,
5^(13 - 1) === 1 mod 13
5^12 === 1 mod 13
Using fast exponentiation, we find out that
5^12 === 1 mod 13 is true
i.e. Is 15 a prime number? We’ll choose a random numbers for z:
z^(r - 1) === 1 mod r,
3^(15 - 1) === 1 mod 15
3^14 === 1 mod 15
Using fast exponentiation, we find out that
3^12 === 1 mod 15 is false
Theorems:
If we’re given a problem like: 5^1003 mod 17
What theorems can we use to solve these type of problems?
- Fast Exponentiation
- Fermat’s Little Theorem IF the number is prime
Theorems:
If we’re given a problem like:
Get count from 1…143 of relatively prime numbers
What theorems can we use to solve these type of problems?
- Euler’s Totient Function
Theorems:
If we’re given a problem like:
Given a ribbon of 22,608 in and 10,206 in, find the spool that evenly divides into the same length
What theorems can we use to solve these type of problems?
- Euclid’s Algorithm
Theorems:
If we’re given a problem like: 13^-1 mod 17
What theorems can we use to solve these type of problems?
- Extended Euclid Algorithm
Theorems: RSA
What are the steps?
Steps:
- Determine p and q (if not provided)
Use Euler’s Totient Function for N - Determine N (if not provided)
N = p * q - Determine e
e is usually provided to you. But e is a prime and relatively prime to N - Determine d
d = e^-1 mod N
OR
d * e === 1 mod N
Use Extended Euclid’s Algorithm - Decrypt message with formula:
m = y^e mod N - Encrypt message with:
y = m^d mod N
