O'Reilly logo

Introduction to Computer Security by Matt Bishop

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 28. 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 chapter reviews this algorithm and its applications. We begin with the classical algorithm and then extend it to solve simple equations.

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 ab. 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 = aqb. If n ≠ 0, and x divides a – qb, then x divides r. We have now ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required