Cs6515 Exam 2 Questions And Complete Solutions

Time to multiply or divide 2 n-bit numbers {Ans: O(n^2)}Euclid's Rule {Ans: - If x >= y > 0: - gcd(x, y) = gcd(x MOD y, y) Note: For Euclid's also that gcd(x, 0) = x}Fast Modular Exponentiation Algorithm {Ans: Inputs: x, y >= 0, N >= 1 Outputs: x^y MOD N Runtime: O(N^3)* Description: recursively squaring modulus}RSA Worst Features {Ans: 1. gcd(m, N) > 1 - then gcd(y, N) = p (or q) - can then factorize N and break crypto system - **Make sure m and N are relatively prime to each other** 2. m not too large (m < N) - must break messages into n bit segments - m < 2^n 3. m is not too small - m^e mod N = m^e - N isn't doing anything, so easy to decrypt - send padded message with m + r and r 4. Same message m, e times is a problem - if they all have e = 3, but different N's, the same message m can be decrypted using CRT}Post Order Properties: Back Edge {Ans: For edge z -> w, post(z) < post(w)}x mod N = {Ans: x =