- 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 q
_{1}= 2, q_{2}= 2, q_{3}= 4, q_{4}= 3, q_{5}= 8 - We will now use the following sequences
- x
_{0 }= 0, x_{1 }= 1, x_{j }= -q_{j-1}x_{j-1 }+ x_{j-2} - y
_{0 }= 1, y_{1 }= 0, y_{j }= -q_{j-1}y_{j-1 }+ y_{j-2} - In order to arrive at
- x
_{0 }= 0 - x
_{1 }= 1 - x
_{2 }= -2 x_{1 }+ x_{0 }= -2 - x
_{3 }= -2 x_{2 }+ x_{1 }= 5 - x
_{4 }= -4 x_{3 }+ x_{2 }= -22 - x
_{5 }= -3 x_{4 }+ x_{3 }= 71 - y
_{5}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

## Thursday, September 12, 2013

### Notes - Solving AX+ BY = D

The following are notes from Introduction to Cryptography with Coding Theory.

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment