RSA: Mathematical background
Algorithm and Correctness of RSA
- divisibility
- Congruence
- Ring Zn
- Greatest Common Denominator
- Euclidean algorithm
- Bit complexity
- Extended Euclidean alg., Bezout's identity
- Primes
- field Zp
- group of units
- euler's totient function
- Little Fermat and generalization
Security of RSA
- Security Models, Computational Complexity, Randomized Algorithms
- Reduction to Factoring
- Complexity of guessing factorization.
- How to factor: x2=y2 (n) when x != +- y.
- Finding x when y=1; plentitude of such x.
-