Math Theorems

Question 1

Using Fermats Little Theorem how can we avoid testing every number 1 to P

Answer 1

for a single number

Prob that flt returns yes when N is prime is 1

Prob that flt returns yes when N is not prime is <= 1/2

So depending on the amount of certainty we pick k different a values, which gives us

1/2^k as the probability flt returns yes when it is not prime.

Question 2

What theorem would you use to solve:

w^x - y^x divisible by N

if

1. N can be factored into two primes
2. GCD(w,N) = 1 and GCD(y,N) = 1

Answer 2

Euler’s Theorem:

If N is the product of 2 prime numbers and GCD(w,Z) = 1 and GCD(y,Z) = 1

Then Z^(p-1)(q-1) === 1 mod N

E.g. Is 4¹⁵³⁶ - 9⁴⁸²⁴ divisible by 35

35 is product of 5 & 7 (two primes)

gcd(4,35) = 1

gcd(9,35) = 1

(p-1)(q-1) = (5-1) * (7-1) = 24

Z²⁴ = 1 mod 35

1536/24 = 64 so 4^(24*64) equals 1 mod 55

4824/24 = 201 so 9^(24)(201) equals 1 mod 9

1 mod 5 = 1, 1 mod 9 = 1

1 -1 = 0, there is no left over so yes it is divisible!!!

Question 3

What is the substitution rule for x and y

in modulo arithmetic in terms of x’ and y’

Answer 3

if

x = x’ (mod n) and y = y’ (mod n)

then

x + y === x’ + y’ (mod n)

and

xy === x’y’ (mod n)

10 * 15 (mod 4) =>

(10 (mod 4) * 15) (mod 4) -or-

(10 * 15 (mod 4)) (mod 4)-or-

(10 (mod 4) * 15 (mod4)) (mod 4)

Question 4

Can you prove that if a mod b has an inverse then b mod a must also have an inverse?

Answer 4

Yes, a (mod b) only has an inverse if gcd (a,b) = 1

so the formula b (mod a) only has an inverse if gcd(b,a) = 1

gcd(a,b) and gcd(b,a) are the same formula.

Question 5

Euler’s Theorem

Answer 5

For N = pq where p & q are prime,

For any Z where gcd(Z, N) = 1

Then Z^(p-1)(q-1) is equivliant to 1 mod N

Question 6

Multiply Algorithm

Time O(n²)

Answer 6

Multiply(x,y):

if y == 0: return 0

z = multiply(x, floor(y/2))

if y is even:

return 2z

else

return x + 2z

Question 7

How can we use Fermats Little Theorem to prove a number is prime.

Answer 7

Fermat’s little theorem says:

If p is prime, then for every 1 <=a

a^(p-1) === 1 (mod p)

So if we have a number P that we want to test for primality, then calculate

a^(p-1) for every value a between 1 and p.

If they all equal 1, then it is prime.

(Note: There are some charmichael numbers like 561 which pass the test, but aren’t prime.

Question 8

Euclid’s Rule

Answer 8

if x & y are positive integers x >= y,

then gcd(x,y) = gcd(x mod y, y)

Question 9

How are keys created for RSA

Answer 9

1. Pick two large prime numbers p and q

2. calculate n = pq. (n is the modulus for pub and priv)
3. Calculate totient of n .. (p-1)(q-1)
4. Choose e (the public key exponent) so that the gcd(e, totient(n)) = 1. (can be small like 3, 5, 35)
5. Calculate d to be the inverse of e mod totient(n)
   
   1. Use Extended-Euclid (e,n)
   2. The number that returns as the multiple (x) for e is the inverse.
   3. if it’s negative you need to mod it. (Basically add N to it until it is positive.)
   4. This number alone not (x * e) but the x is the inverse x Mod N.

Public Key = (n, e)

Private key = (d)

Note if you get a decryption key of 1, then your selection of e was not gcd 1 with totn.

Question 10

ModExp Algorithm

Time O(n³)

Answer 10

ModExp(x, y, N):

if y = 0: return 1

Z = modexp(x, floor(y/2), N)

if y is even:

return z² mod N

else

return x * z² mod N

Question 11

What is Euclid’s Algorithm for GCD

Time O(n³)

Answer 11

Euclid(a,b):

// a and b with a >= b >= 0

if b = 0: return a

return Euclid(b, a mod b)

b, a mod b =>

Question 12

if x & y are positive

x >= y

then

gcd(x,y) is equal to

Answer 12

gcd(y, x mod y)

Question 13

p is prime, q is prime:

N = pq

What is totient(N)

Answer 13

(p-1)(q-1)

Question 14

Big O time for modulo

Addition

Multiplication

Division

Answer 14

Addition => O(n)

Multiplication => O(n²)

Division => O(n³)

Question 15

What is multiplicative inverse for modulo numbers?

Answer 15

x is the multiplicative inverse of a (mod n)

if a*x (mod n) = 1

Sometimes one doesn’t exist. if gcd(a, N) > 1, it can never exist. E.g. a=2, N=6

When gcd(a, N) = 1 (we say a and N are relatively prime), the extended Euclid algorithm gives us integers x and y such that ax + N y = 1, which means that ax ≡ 1 (mod N). Thus x is a’s sought inverse.

Question 16

Divide Algorithm

Time O(n²)

Answer 16

Divide(x,y):

if x = 0: return (q,r) = (0,0)

(q,r) = divide(floor(x/2), y)

q = 2 * q, r = 2 * r

if x is odd:

r = r + 1

if r >= y:

r= r - y

q = q + 1

return (q, r)

Question 17

What is Eculid’s Extended Algorithm

(and what can you tell with it)

Answer 17

To check if a number d is the gcd of a and b. Then the extension says:

if d divides both a and b, and d = ax + by for some integers x and y then necessarily d = gcd (a,b)

extended-euclid(a,b):

input a,b with a>=b>=0

output: x, y, d such that d = gcd(a,b) and ax + by = d

if b = 0: return (1,0,a)

(x’, y’, d) = extended-Euclid(b, a mod b)

return (y’, x’ - floor(a/b)y’, d)

Question 18

Euler’s Totient Function

Answer 18

For prime P, Totient(P) = P - 1;

When N = pq, Totient(N) = (p-1)(q-1)

Question 19

How can you reduce 2³⁴⁵ (mod 31)

using the substitution rules and associativity, commutativity and distributivity

Answer 19

Taken together with the substitution rule, it is legal to reduce intermediate results modulo N at any stage. So simplifications can be made like:

2³⁴⁵ (mod 31) ==>

(2⁵)⁶⁹ (mod 31) ==>

32⁶⁹ (mod 31) ==>

1⁶⁹ (mod 31) ==>

1 (mod 31)

Question 20

What theorem would you use to solve

a mod N

if N is prime.

Answer 20

Fermats Little Theorem

(If N is prime, than for 1 <= a < n)

a^(n-1) = 1 mod N

19⁹ (mod 5)

19^{(5-1) =>} 19⁴ = 1 mod 5

Divide exponent by N-1:

9/4 = 2 R 1

This means 19⁸ = 1 mod 5

Substiution leaves

19⁸ (mod 5) * 19¹ (mod 5) => 1 (mod 5) * 19 mod 5

1 * 4 = 4

Question 21

How is RSA performed using:

N, e -> public key

d -> private key

Answer 21

Encrypt x:

y = x^e mod N

Decrypt y:

x = y^d mod N

Question 22

Fermat’s Little Theorem

Answer 22

If p is prime, then for every 1 <=a < p

a^p-1 = 1 (mod p)

e.g: is 2^2 = 1 mod 3

p = 3 and is prime

2^(3-1) = 2^2 = 1 mod 3

1 mod 3

Question 23

How do you get a prime number?

Answer 23

Select a random n bit number

Run it through flt

if passes it is prime, otherwise try again

Probability of hitting a prime in n but numbers is 1/n so we expect this to only take n guesses at most.

Question 24

What are the 3 main steps to Kruskal’s Algorithm

Time: O(mlogn)

m = edges

n = verticies

Answer 24

Input: Undireted graph G(v,e) with weights w(e)

1. Sort E by increasing weight
2. Set x to the empty set.
3. For each edge in our sorted list of edges, if adding edge into x does not create a cycle, then add the edge.
4. Return x

Question 25

What are cut edges

Undirected G=(v,e)

Partition V = S union ~S

Answer 25

Cut(S,~S) = {(v,w) in E: v in S, w in ~s}

This says cut edges are the edges that

cross between S and ~S.

Question 26

2 Takeaway’s from MST proof

Answer 26

1) I can take a tree, add in e* and that creates a cycle. I can then remove any edge from that cycle and get a new tree T’
2) A minimum weight edge across the cut is part of a mst.

Question 27

What is topological order in an acyclic graph

Answer 27

The order based on decreasing post number.