The extended Euclidean algorithm is of interest to cryptographers because
Answers
The extended Euclidean algorithm is of interest to cryptographers because 'A multiplicative inverse can be calculated using this algorithm easily'.
Short note on Euclidean algorithm:
(i) It is an efficient method for computing the greatest common of two integers
(ii) Let g = gcd(a,b) = 1 then a and b are said to be co primes(or relatively prime).
(iv) The Euclidean Algorithm proceeds in a series of steps such that the output of each step is used as an input for the next one.
Example 1:
A simple variant of Euclid Algorithm,called Extended Euclid algorithm, on inputs(ab) outputs also n = gcd(a,b) together with integers d,e
n = d * a + e * b.
Note that if x is coprime to n then ExtEucGCD(a,b,c) outputs (n,d,e) n = 1 because gcd(x,n) = 1 and therefore,
1 = d * x + e * b
Therefore, d = x⁻¹ mod b.
Therefore,Computing multiplicative inverse is as easy as computing GCD.
Hope it helps!
Answer:bcoz it is particularly useful when a and b are coprime. It follows that both extended euclidean algorithm are widely used in cytrograhpers.
Explanation: