CS6515 - Exam 2 Algorithms Questions With 100% Correct Answers.

Equivalence - Answer-"x ≡ y (mod N) means that x/N and y/N have the same remainder a ≡ b (mod N) and c ≡ d (mod N) then: a + c ≡ a + d ≡ b + c ≡ b + d (mod N) a - c ≡ a - d ≡ b - c ≡ b - d (mod N) a ** c ≡ a ** d ≡ b ** c ≡ b ** d (mod N) ka ≡ kb (mod N) for any integer k ak ≡ bk (mod N) for any natural number k a + k ≡ b + k (mod N) for any integer k a + b = c, then a (mod N) + b (mod N) ≡ c (mod N) a ** b = c, then a (mod N) ** b (mod N) ≡ c (mod N)" Multiplicative Inverse - Answer-"Exists iff x and N are relatively prime Is unique 1 ≤ inverse N if it exists z is the multiplicative inverse of x if zx ≡ 1 (mod N) z ≡ x^(−1) (mod N) x ≡ z^(−1) (mod N)" Greatest Common Divisor - Answer-"gcd(x,y) = largest number that divides both x and y gcd(x,y) = gcd(x mod y, y)" Relatively Prime - Answer-iff gcd(a,b) = 1 Fermat's Little Theorem - Answer-"If p is a prime number: a^p≡ a (mod p) a^p-1 ≡ 1 (mod p) for 1 ≤ a ≤ p−1 a^(p-1) ≡ 1 (mod p) if a mod p ≠ 0 a^((p-1)*k) ≡ 1 (mod p) if a mod p ≠ 0 and any natural number k r is a prime number iff a^(r-1) ≡ 1 (mod r) for 1 ≤ a ≤ r−1"Euler's totient function - Answer-"N = pq where p and q are distinct prime numbers Denoted as ϕ(N) - How many numbers from 1 to n are relatively prime to n - 1 ≤ x ≤ N such that gcd(N,x) = 1 - ϕ(p) = p-1 where p is a prime number - ϕ(p^2) = p(p-1) where p is a prime number - ϕ(N) = (p-1)(q-1)" Euler's Theorem - Answer-"N = pq where p and q are distinct prime numbers If a,N are relatively prime: a^ϕ(N) ≡ 1 (mod N) a^(p-1)(q-1) ≡ 1 (mod pq) a^ϕ(N)k ≡ 1 (mod N) a^(p-1)(q-1)k ≡ 1 (mod pq)" Fermat's Little Theorem (RSA) - Answer-"If p is a prime number: bc ≡ 1 (mod p-1)bc = 1 + k(p - 1) for some integer k z^(bc) ≡ z (mod p)" Euler's Theorem (RSA) - Answer-"N = pq where p and q are distinct prime numbers If z,N are relatively prime: de ≡ 1 (mod (p-1)(q-1)) de = 1 + k(p - 1)(q - 1) for some integer k z^(de) ≡ z^(1 + k(p - 1)(q - 1)) ≡ (z)z^((p - 1)(q -1)k) ≡ z (mod N) Encrypt: E ≡ M^e (mod N) Decrypt: M ≡ E^d (mod N)" Fast modular exponentiation algorithm - Answer-"Inputs: x, y ≥ 0, N ≥ 1 Outputs: x^y mod N Runtime: O(n^3) mod_exp(x,y,N):if y = 0: return 1 z = mod_exp(x,⌊y/2⌋,N) if y is even: return z^2 mod N if y is odd: return xz^2 mod " Euclid's GCD algorithm - Answer-"Inputs: x ≥ y ≥ 0 Outputs: gcd of x and y gcd(x,y): if y = 0: return x else: return gcd(y, x mod y) Runtime: O(n^3) - n is the number of bits to represent x and y"