Design and Analysis of Algorithms Neal Young
Computer Science 45
Due: in class Friday, May 2, 1997
Problem Set 4
Prove that gcd(a,b)
is the smallest positive element of .
(See CLR problem 33.2-7.)
Given primes p and q, integer n=pq,
and integer e relatively prime to ,
show how to efficiently compute
.
What does this have to do with RSA?