Modular Arithmetic
Modular arithmetic is a fundamental concept in cryptography, used extensively in various
encryption algorithms, key exchange protocols, digital signatures, and more. Let's explore
modular arithmetic in detail, especially its role and applications in cryptography.
What is Modular Arithmetic?
Definition:
Modular arithmetic is a system of arithmetic for integers where numbers "wrap around"
after they reach a certain value called the modulus.
The notation:
a mod n
means the remainder when a is divided by n.
if a>=n then a mod n is the remainder when a is divided by n
if a < n then a mod n is ‘a’
Examples:
1. 17 mod 5=2
2. 2 mod 5 = 2 (Since 2<5)
3. -13 mod 8 = (-13+8) mod 8 = -5 mod 8 = (-5+8) mod 8 = 3 mod 8 = 8 (We must keep
on adding ‘a’ with ‘n’ until the LHS of mod operation becomes a +ve value. After
that only we should take mod)
Why Modular Arithmetic is Important in Cryptography
Modular arithmetic provides properties that are crucial for cryptographic operations:
Easy to Compute
Difficult to reverse (e.g., modular exponentiation vs. discrete logarithm)
Supports one-way functions, essential for encryption and digital signatures
Enables finite fields, which ensure predictable and secure behavior
Congruent modulo operation
Two integers a and b are said to be congruent modulo n, written as:
a ≡ b mod n
This means:
amod n = bmod n
Properties of Congruence
If: a ≡ bmodnand c ≡ dmodn then
1. Addition: a+ c ≡ b+d mod n
2. Subtraction: a−c ≡b−d mod n
3. Multiplication: a ⋅ c ≡b ⋅ d mod n
4. Exponentiation: a k ≡ bk modn
Key Operations in Modular Arithmetic
1. Modular Addition & Subtraction
( a+ b ) mod n=[ ( amod n )+ ( bmod n ) ] mod n
( a−b ) mod n=[ ( amod n )−( bmod n ) ] mod n
2. Modular Multiplication
(a x b) mod n = [(a mod n) x (b mod n)]mod n
3. Modular Inverse
The modular inverse of a modulo n is a number a−1 such that:
a⋅a−1≡1mod n
Exists only if a and n are co-prime (gcd (a, n) = 1).
Example:
−1
3 mod 11=4 because 3⋅ 4=12≡ 1 mod 11
Prime numbers:
Numbers that are divided by 1 and by itself are called prime numbers.
Example: 2,3,5,7,11,13,17 etc. Because each number can be divided by 1 and by the
number itself.
Co-prime or relatively prime numbers:
Two numbers are said to be coprime or relatively prime numbers if their GCD is 1. These
two numbers need not be prime numbers.
Example:
(9, 10) are coprime or relatively prime numbers because GCD (9, 10) = 1.
Note: 9 and 10 are not prime numbers.
Residue set:
Residue Set (also called set of residues) refers to the collection of remainders when
integers are divided by a given number, called the modulus.
A complete residue system modulo n is a set of ‘n’ integers such that every integer is
congruent to exactly one element of the set modulo n.
Example:
Modulo n=5, a complete residue system is: {0,1,2,3,4}. This means that if we do any
mathematical operations such as addition, subtraction and multiplication on any two
integers and take modulus 5, we get one number as a result from the residue set.
Proof:
let a= 15, b= 23 perform
1. addition and take modulus 5 we get
(15+23) mod 5 = 38 mod 5 = 3
2. multiplication and take modulus 5
(15 x 23) mod 5 = 345 mod 5 = 0
3. subtraction and take modulus 5
(15-23) mod 5 = -8 mod 5 = (-8+5) mod 5 = -3 mod 5 = (-3+5) mod 5 = 2 mod 5 = 2
You can also perform division operations. After performing the division operation, you
must apply floor or ceil value for the result and take modulus 5. If we do so we get the
result in the same residue set.
Euclid’s Algorithm
Euclid’s Algorithm is a fundamental method used to compute the Greatest Common
Divisor (GCD) of two integers. The GCD of two numbers is the largest positive integer that
divides both numbers without leaving a remainder.
It’s one of the oldest and most efficient algorithms in number theory, and it's heavily used
in cryptography, especially in algorithms like RSA and for computing modular inverses.
Definition
Let’s say we want to find:
GCD (a, b)
Where a≥b≥0
Euclid's algorithm is based on the principle:
GCD (a, b) =GCD(b, a mod b)
We keep replacing a with b, and b with a mod b, until b=0. The GCD is then the last non-zero
value of a.
Pseudocode
function gcd(a, b):
while b ≠ 0:
temp = b
b = a mod b
a = temp
return a
Step-by-step Example
Find GCD (252, 105)
Step a b a mod b
1 252 105 42
2 105 42 21
3 42 21 0
So, GCD (252, 105) = 21
The Extended Euclid Algorithm
Consider the following theorem in number theory:
Theorem. For all positive integers a and b there exist integers s and t such that
a ⋅ s + b ⋅ t = gcd(a, b).
The proof of this theorem can be found in an exercise in the Rosen textbook. However, the
proof merely shows that s and t exist. It doesn't show how to find s and t. The Extended
Euclid algorithm can be used to find s and t.
Finding s and t is especially useful when we want to compute multiplicative inverses.
Suppose that gcd(a, n) = 1. (That is, a and n are relatively prime.) We have seen that in this
situation a has a multiplicative inverse modulo n. That is, there exists an integer, which we
call a-1, such that
a ⋅ a-1 ≡ 1 (mod n).
Using the theorem above, we can find s and t so that
a ⋅ s + n ⋅ t = 1.
Since gcd(a, n) = 1. Now, notice that
a ⋅ s = 1 - n ⋅ t.
Now, n ⋅ t ≡ 0 modulo n, so
a ⋅ s ≡ 1 (mod n).
Therefore, s ≡ a-1 modulo n and we have found the multiplicative inverse of a.
The Algorithm
Here's the pseudo-code for the Extended Euclid algorithm:
Find b-1mod m
ExtEuclid (b.m) {
Step1: Take A1, A2, A3, B1, B2, B3
Step2: Initialize A1=1, A2=0, A3 = m
Initialize B1=0, B2=1, B3=b
Step3: if B3==1 then
B2 is the inverse value and A2 is the GCD (b, m)
if B3==0 then
No inverse and B2 is the GCD (b, m)
Otherwise, go to Step 4:
Step4:
Find Q = |[A3/B3} | //floor value of A3/B3
Find T1 = A1-QB1; T2=A2-QB2; T3=A3-QB3
Assign A1=B1; A2=B2; A3=B3
Assign B1=T1; B2=T2; B3=T3
Repeat Step 3 and Step 4 until B3 = 0 or B3 = 1
}
Example
Find the multiplicative inverse of 60 under modulus 13.
Solution:
Given
here b=60 and m=13
Step1: Take A1, A2, A3, B1, B2, B3
Step2: Initialize A1=1, A2=0, A3 = 13
Initialize B1=0, B2=1, B3=60
If
B3=
T1=A1 T2=A T3=A
Step A1 A2 A3 B1 B2 B3 0 || Q=|[A3/B3} |
-QB1 2-QB2 3-QB3
B3=
1
0 1 0 13 0 1 60 No 0 0 1 13
1 0 1 60 0 1 13 No 4 -4 1 8
2 0 1 13 -4 1 8 No 1 5 -1 5
3 -4 1 8 5 -1 5 No 1 -9 2 3
4 5 -1 5 -9 2 3 No 1 14 -3 2
5 -9 2 3 14 -3 2 No 1 -23 5 1
6 14 -3 2 -23 5 1 Yes
Since B3=1 B2 is the inverse of 60 mod 13.
How do I check this?
Let A = 60
Let A-1 = 5
According to multiplicative inverse law A x A-1 mod m = 1
So if we get 60 x 5 mod 13 = 1 our answer is correct
Let’s check
60 x 5 mod 13 = 300 mod 13 = 1
