your exercise will not be checked!!!
1. In number theory, Bézout's identity or Bézout's lemma states that if a and b are nonzero integers with greatest common divisor d, then there exist integers x and y (called Bézout numbers or Bézout coefficients) such that
The extended Euclidean algorithm is an extension to the gcd algorithm presented in class for finding the greatest common divisor (GCD) of integers a and b: it also finds the integers x and y in Bézout's identity
Below is a pseudo code for the extended gcd algorithm:
function extended_gcd(a, b)
if a mod b = 0
return {0, 1}
else
{x, y} := extended_gcd(b, a mod b)
return {y, x-y*(a div b)}
Complete the scheme implementation of the extended gcd algorithm and explain how this algorithm can be used for finding RSA’s private key (d).
(define (egcd a b)
(if (= (remainder a b) 0) (lambda(c) (if c 0 1))
(let ((fxy (egcd b (remainder a b))))
(lambda(c) (if c (fxy #f) (- (fxy #t) (* (fxy ?) (quotient a b))))))
))