Cryptography: Number Theory - Modular Arithmetic

Modular Arithmetic 

Given any integer a and a positive integer n, and given a division of a by n that leaves the remainder between 0 and n − 1, both inclusive, we define

  a mod n    to be the remainder.

Note that the remainder must be between 0 and n − 1, both ends inclusive, even if that means that we must use a negative quotient when dividing a by n. 

Modular Arithmetic - Exponentation 

•To find 117 mod 13, we can proceed as follows:

•112 = 121 º 4 (mod13)
114 = (112)2 º 42 º 3 (mod13)
117 º 11*4*3 º132 º 2(mod13)

 

Properties of Modular Arithmetic

Modulo n arithmetic maps all integers into the set {0, 1, 2, 3, ...., n − 1} 

1.[(a mod n) + (b mod n)] mod n = (a + b) mod n

2.[(a mod n) - (b mod n)] mod n = (a - b) mod n

3.[(a mod n) * (b mod n)] mod n = (a * b) mod n

Proof 1:

•Define (a mod n) = ra and (b mod n) = rb.

•Then we can write a = ra + jn for some integer j and b = rb + kn for some integer k. Then

–(a+b) mod n = (ra + jn + rb + kn) mod n

–(ra + rb + (k+j) n) mod n

–(ra + rb)mod n

–[(a mod n) + (b mod n)] mod n