15-853: Algorithms in the Real World (Guy Blelloch, Fall 01)

Fixes to Course Notes

Introduction to Cryptography

In section 5.2 (RSA), the statement "But m is relatively prime to n (because n = pq ...)" is not necesarily true. We could pick all m < p and q, making it true, but this is not necessary. Knowing that m is relatively prime to p and q is good enough to prove that m^{ed} = m (mod n) even if m is not an element of Z_n^*..

Back to the Algorithms in the Real World page (V. 2001).

Guy Blelloch, guyb@cs.cmu.edu.