Blog
Copyright © 2019 Jiri Kriz, www.nosco.ch

Modular Arithmetic

Comments (0)
I present the very basic concepts of modular arithmetic as they are needed in cryptography. Important topics are: congruences, Fermat's theorem and the Euler function.

Introduction

In modular arithmetic, integer numbers "wrap around" upon reaching a certain value called the modulus. An example is in the 12-hour clock. If the time is 7:00 now, then 8 hours later it will be 3:00 because 7 + 8 = 15, 15 - 12 = 3.

Congruence

Modular arithmetic is based on the congruence relation. Two numbers a and b are congruent modulo n if their difference a − b is an integer multiple of n. This is written as

a ≡ b (mod n).(1)

The arithmetic operations like addition and multiplication are carried over to the respective congruences, e.g.
if

a1 ≡ b1 (mod n).
a2 ≡ b2 (mod n).

then

a1 ⋅ a2 ≡ b1 ⋅ b2 (mod n)
k⋅ a1 ≡ k ⋅ b1 (mod n).

In general, we cannot cancel a common multiplicative factor from a congruence. For example, it is:

7 ⋅ 2 ≡ 12 ⋅ 2 (mod 10) = 4

but after cancelling 2 we get:

7 ≢ 12 (mod 10).

However, if k is coprime with n then it can be cancelled:

k ⋅ a ≡ k ⋅ b (mod n)(2a)

implies

a ≡ b (mod n)(2b)

Eq. (2a) says that n divides k ⋅ a - k ⋅ b = k ⋅ (a -b). Since n and k have no common multiplicative factors, n must divide a - b, so eq. (2b) follows.

The following useful property will be applied in the public key cryptography. If

a ≡ b (mod n)(3a)
a ≡ b (mod m)(3b)

and n and m are coprime, then

a ≡ b (mod m ⋅ n)(4)

The proof is easy but tricky. Equations (3) can be written as

a - b = k1 ⋅ n = k2 ⋅ m(5)

for some integers k1 and k2. Because n and m are coprime we know from the Bézout's idententity that there exist numbers x and y such that

1 = n ⋅ x + m ⋅ y(6)

We multiply eq. (6) by a - b and substitute the expressions (5):

a - b =
= (a - b) ⋅ n ⋅ x + (a - b) ⋅ m ⋅ y
= k2 ⋅ m ⋅ n ⋅ x + k1 ⋅ n ⋅ m ⋅ y
= (k2 ⋅ x + k1 ⋅ y) ⋅ (m ⋅ n)

So, a - b is a multiple of n · m and the eq. (4) follows.

Integers modulo n

When we compute (mod n) it is sufficient to consider only the numbers 0, 1, .. n-1 because all other numbers are reduced to them via the congruence relation. The set of these "residues" Zn is a mathematical structure called a ring. A ring provides the operations of addition and multiplication with the usual properties. It does not provide division. However, in the special case when n = prime p each number a in Z+p = {1, .. p-1} has also an inverse with respect to multiplication that is denoted a-1

a ⋅ a-1 ≡ 1 (mod p) for a ≢ 0 (mod p)(7)

because gcd(a, p) = 1. The inverse a-1 can be computed using the Extended Euclidean Algorithm. So, the set Zp provides also division and is a mathematical field, denoted by Fp or GF(p) (GF for Galois Field).

Fermat's Little Theorem

If p is a prime number and a is a natural number, a ≢ 0 (mod p), then

ap-1 ≡ 1 (mod p).(8)

Proof: consider the numbers

1⋅a, 2⋅a, 3⋅a, ... (p-1)⋅a(9)

all (mod p). These numbers are different because if it were

k1 ⋅ a = k2 ⋅ a (mod p)

we could cancel a since a and p are coprime and get

k1 = k2

So, these p-1 numbers correspond to the numbers

1, 2, 3, ... (p-1)(10)

in some order. Consequently the product of the numbers (9) equals the product of the numbers (10):

ap-1 ⋅ (p-1)! ≡ 1 ⋅ (p-1)! (mod p)

Now we may cancel (p-1)! in GF(p) and get equation (8).

A simple corollary from equation (8) is:

ap ≡ a (mod p) for every a(11)

Euler's Φ Function

Euler's generalization of Fermat's Little Theorem is that for any modulus n

aΦ(n) ≡ 1 (mod n) (12)

provided that a and n are relatively prime. Here, Φ(n) is the count of numbers 0, 1, .. n-1 that are relatively prime to n. The proof is analogous to the proof of the Fermat's theorem. Notice that the Fermat's theorem is a special case of the Euler's theorem, because Φ(p) = p - 1 for a prime p.

The Euler's Φ function satisfies the following relation for coprime m and n (without proof):

Φ(n ⋅ m) = Φ(n) ⋅ Φ(m) (13)

Links:

Comments

New Comment