Question

The algorithm credited to Euclid for easily finding the greatest common divisor of two integers has broad significance in cryptography.
a. True
b. False

Answer 1

Answer:

a. True                      

Explanation:

• Euclid's algorithm for finding greatest common divisor of two integers is a very effective method which has importance in cryptography as it is being used in cryptographic schemes and algorithms.
• This algorithm calculates gcd of  2 integers which is the largest number which divides both the integers.
• The famous RSA public-key encryption technique also uses extended version of this algorithm to compute modular multiplicative inverse
• Euclid algorithm is also used in Chinese remainder theorem.
• This algorithm is not only used in cryptographic algorithm but is also used in breaking these cryptosystems using prime factorization as we know that factorization of large integers is very tough and the security of many cryptography systems depends on this.