Thursday, September 12, 2013

Notes - Solving AX+ BY = D

The following are notes from Introduction to Cryptography with Coding Theory.
  • In a previous example we used the Euclidean Algorithm to find the GCD 
    • We will now show how we can get the integers x,y that fulfill
    • ax + by = gcd(a,b)
  • Example gcd(482,1180)
    • 1180 = 2 * 482 +216
    • 482 = 2 * 216 + 50
    • 216 = 4 * 50 + 16
    • 50 = 3 * 16 + 2
    • 16 = 8 * 2 + 0
    • Which gave us q1 = 2, q2 = 2, q3 = 4, q4 = 3, q5 = 8
  • We will now use the following sequences
    • x= 0, x= 1, x= -qj-1 xj-1 + xj-2
    • y= 1, y= 0, y= -qj-1 yj-1 + yj-2
  • In order to arrive at
    • x= 0
    • x= 1
    • x= -2 x+ x= -2
    • x= -2 x+ x= 5
    • x= -4 x+ x= -22
    • x= -3 x+ x= 71
  • y5 would be calculated similarly to arrive at -29
  • We would then plug this in to ax + by = gcd(a,b)
    • 482 * 71 + 1180 * (-29)
    • 2
  • This is often called the extended Euclidean algorithm
    • used for congruences

No comments:

Post a Comment