1/19
Looks like no tags are added yet.
When does b have an inverse mod n?
Exactly when gcd(b,n)=1.
How do you calculate a/b mod n?
a*b^(-1) mod n.
What does XGCD give?
x,y with gcd(a,b)=xa+yb.
How does XGCD give a^(-1) mod n?
If 1=xa+yn, then x mod n is a^(-1).
What is phi(n)?
The number of residues modulo n relatively prime to n; |Z_n*|.
phi(p) for prime p?
p-1.
phi(pq) for distinct primes p,q?
(p-1)(q-1).
General totient formula?
If n=product p_i^e_i, phi(n)=product p_i^(e_i-1)(p_i-1).
Euler's theorem?
If gcd(a,n)=1, then a^phi(n)=1 mod n.
How does Euler help with modular powers?
Reduce the exponent modulo phi(n), when the base is invertible.
Fermat's Little Theorem?
If p is prime and p does not divide a, then a^(p-1)=1 mod p.
Purpose of square-and-multiply?
Efficient modular exponentiation using the binary exponent.
CRT condition for unique reconstruction?
The moduli must be pairwise coprime.
CRT core idea?
Compute modulo smaller coprime factors, then reconstruct the unique result.
Quadratic residue q mod n?
Some x exists with x^2=q mod n.
If n=pq and a is a QR in Z_n*, how many roots?
Exactly four.
How do you find roots mod pq?
Find roots mod p and mod q, then combine sign choices with CRT.
Exam trigger: a/b mod n?
Find b^(-1) with XGCD, then multiply by a.
Exam trigger: huge exponent mod n?
Look for phi/Euler or Fermat reduction, then square-and-multiply.
Exam trigger: all roots mod pq?
Factor n, solve mod each prime, combine four sign pairs with CRT.