1|Page
CS6515 EXAM 2-
COMPLETE EXAM SET Q&A
2026
Basic Properties of MOD - correct-answer -if x:::y MOD N & a:::b MOD N:
1. x+a ::: y+b MOD N
2. xa ::: yb MODN N
Time to multiply or divide 2 n-bit numbers - correct-answer -O(n^2)
Modular Inverse - correct-answer -X is the multiplicative inverse of Z MOD N if:
- (x * z) MOD N = 1
Notation:
x:::z^-1 MOD N
z::::x^-1 MOD N
When does the inverse of x MOD N exist - correct-answer -When GCD(x, N) = 1.
That is x and N don't share a common divisor and are thus "relatively prime"
Properties of Modular Inverses - correct-answer -- if x^-1 MOD N exists, then it's
unique
,2|Page
- x^-1 MOD N doesn't exist when gcd(x, N) > 1
Euclid's Rule - correct-answer -- If x >= y > 0:
- gcd(x, y) = gcd(x MOD y, y)
Note: For Euclid's also that gcd(x, 0) = x
Extended-Euclid's algorithm alpha and beta output params - correct-answer --
Alpha is the inverse of x MOD y
- Beta is the inverse of y MOD x
Fermat's Little Theorem - correct-answer -- If p is prime then for every 1 <= z <= p
- 1:
- z ^ (p-1) ::: 1 MOD P
Note: since 1 <= z <= p - 1 that the gcd(z, p) = 1; they are relatively prime
Euler's Theorem - correct-answer -- for any N,z where gcd(z, N) = 1; that is they
are relatively prime:
- then z^(phi(n)) = 1 mod N
phi(N) = # of integers between 1 & N which are relatively prime to N
phi(N) - is called Euler's totient function
Note: Euler's Theorem is a generalization of Fermat's little theorem for arbitrary N
, 3|Page
RSA Protocol - correct-answer -1. Bob picks 2 n-bit random primes p & q
2. Bob chooses e relatively prime to (p-1)(q-1)
3. Bob publishes his public key (p*q, e)
4. Bob computes his private key: d ::: e^-1 mod (p-1)(q-1)
1. Alice looks up Bob's public key (pq, e)
2. Alice computes y:::m^e MOD N
1. Bob receives y
2. Bob decrypted: computes y^d MOD N ::: m
RSA Pitfalls - correct-answer -1. If gcd(m, N) > 1, crypto system is broken
2. m is not too large (m < N)
3. m is not too small, MOD N doesn't do anything
- send m and r, padding message by m + r
4. send same m, e times
- can decrypt message using Chinese remainder theorem
Fermat's Test - correct-answer -- Find z where z ^(r-1) != 1 mod r
--> r is composite
- This is called a Fermat Witness
--> every composite has a Fermat Witness
CS6515 EXAM 2-
COMPLETE EXAM SET Q&A
2026
Basic Properties of MOD - correct-answer -if x:::y MOD N & a:::b MOD N:
1. x+a ::: y+b MOD N
2. xa ::: yb MODN N
Time to multiply or divide 2 n-bit numbers - correct-answer -O(n^2)
Modular Inverse - correct-answer -X is the multiplicative inverse of Z MOD N if:
- (x * z) MOD N = 1
Notation:
x:::z^-1 MOD N
z::::x^-1 MOD N
When does the inverse of x MOD N exist - correct-answer -When GCD(x, N) = 1.
That is x and N don't share a common divisor and are thus "relatively prime"
Properties of Modular Inverses - correct-answer -- if x^-1 MOD N exists, then it's
unique
,2|Page
- x^-1 MOD N doesn't exist when gcd(x, N) > 1
Euclid's Rule - correct-answer -- If x >= y > 0:
- gcd(x, y) = gcd(x MOD y, y)
Note: For Euclid's also that gcd(x, 0) = x
Extended-Euclid's algorithm alpha and beta output params - correct-answer --
Alpha is the inverse of x MOD y
- Beta is the inverse of y MOD x
Fermat's Little Theorem - correct-answer -- If p is prime then for every 1 <= z <= p
- 1:
- z ^ (p-1) ::: 1 MOD P
Note: since 1 <= z <= p - 1 that the gcd(z, p) = 1; they are relatively prime
Euler's Theorem - correct-answer -- for any N,z where gcd(z, N) = 1; that is they
are relatively prime:
- then z^(phi(n)) = 1 mod N
phi(N) = # of integers between 1 & N which are relatively prime to N
phi(N) - is called Euler's totient function
Note: Euler's Theorem is a generalization of Fermat's little theorem for arbitrary N
, 3|Page
RSA Protocol - correct-answer -1. Bob picks 2 n-bit random primes p & q
2. Bob chooses e relatively prime to (p-1)(q-1)
3. Bob publishes his public key (p*q, e)
4. Bob computes his private key: d ::: e^-1 mod (p-1)(q-1)
1. Alice looks up Bob's public key (pq, e)
2. Alice computes y:::m^e MOD N
1. Bob receives y
2. Bob decrypted: computes y^d MOD N ::: m
RSA Pitfalls - correct-answer -1. If gcd(m, N) > 1, crypto system is broken
2. m is not too large (m < N)
3. m is not too small, MOD N doesn't do anything
- send m and r, padding message by m + r
4. send same m, e times
- can decrypt message using Chinese remainder theorem
Fermat's Test - correct-answer -- Find z where z ^(r-1) != 1 mod r
--> r is composite
- This is called a Fermat Witness
--> every composite has a Fermat Witness
