O'Reilly logo

Computer Security and Cryptography by Alan G. Konheim

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

11.2 MODULAR ARITHMETIC AND THE EUCLIDEAN ALGORITHM

The starting point for our study of modular arithmetic is Proposition 11.3.

Proposition 11.3: (The Division Algorithm for Integers): If a, b image, with b > 0, there exist unique integers q, r image such that a = qb + r with 0 ≤ r < b and we write a = r (modulo b).

Proof: If b divides a, then a = qb and the algorithm is true with r = 0. Otherwise, let S = {aqb : q image, aqb > 0}.

11.3a If A > 0, q = 0 is in S so that Simage;
11.3b If a ≤ 0, let q = a − 1 so that q < 0. If b ≥ 1, then aqb = a(l − b) + b > 0 so again Simage.

By the well-ordering principle, S has a minimum element, say r. If r = aqb, then 0 ≤ r < b or otherwise rb = a − (q + 1)b, contradicting the minimality of r. image

For every integer n ≥ 2, addition, subtraction, and multiplication can be defined on the set of residues modulo n, that is, on the set of integers

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