Appendix B
The Extended Euclidean Algorithm
The Extended Euclidean Algorithm is a staple of number theory and is used to solve equations of the form ax mod n = b. This appendix reviews this algorithm and its applications. We begin with the classical algorithm, and then extend it to solve simple equations.
B.1 The Euclidean Algorithm
Euclid’s algorithm determines the greatest common divisor of two integers. The algorithm is based on the observation that, if x divides both a and b, then x divides their difference a – b. The trick is to find the largest such x.
Assume (without loss of generality) that a > b. If x divides a – b, then it also divides a – qb, where q is an integer. Let r = a – qb. If r ≠ 0, and x divides a – qb, then x divides
Get Computer Security Art and Science, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
