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
.