Skip to Main Content
Computer Security Art and Science, 2nd Edition
book

Computer Security Art and Science, 2nd Edition

by Matt Bishop
November 2018
Intermediate to advanced content levelIntermediate to advanced
1440 pages
48h 29m
English
Addison-Wesley Professional
Content preview from Computer Security Art and Science, 2nd Edition

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 ab. The trick is to find the largest such x.

Assume (without loss of generality) that a > b. If x divides ab, then it also divides aqb, where q is an integer. Let r = aqb. If r ≠ 0, and x divides aqb, then x divides

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Security Engineering, 3rd Edition

Security Engineering, 3rd Edition

Ross Anderson
Defensive Security Handbook, 2nd Edition

Defensive Security Handbook, 2nd Edition

Lee Brotherston, Amanda Berlin, William F. Reyor

Publisher Resources

ISBN: 9780134097145