Public key Mathematics

Question 1

What does the Euclidean Algorithm calculate?

Answer 1

It calculates the greatest common divisor of two numbers r0 and r1

Question 2

How does the Euclidean Algorithm work?

Answer 2

Example: gcd(211, 60)
- Start by getting r0 (211) and r1(60)
- Perform r0 mod r1 i.e. 211 mod 60
- Get the result i.e. 31
- Figure out how many of r1 did you need before you needed to get a remainder i.e. 3 * 60
- Form new equation i.e. 211 = 3 * 60 + 31
- Reset to the beginning, using r0 (60) and r1 (31) from the new equation
- Repeat process until you get a 0 for the remainder
- The previous remainder was the greatest common denominator

Question 3

How does Extended Euclidean build upon normal Euclidean?

Answer 3

• Work out all the equations for Euclidean
• Reverse-engineer all the equations so that they are equal to the remainder e.g. 15 = 2 * 6 + 3 is now set to 3 = 15 - (2 * 6)
• Start at the ‘lowest’ equation, and then continuously keep ‘injecting’ any equations that fit any numbers in the current equation, starting with the lowest equation first.
• Once you can’t do that any more, then re-arrange so that you have the co-efficients in front of the original two numbers that you wanted to find the gcd for.