CryptoBook
Search…
Modular Arithmetic
Authors: A~Z, perhaps someone else but not yet (or they've decided to remain hidden like a ninja)

Introduction

Thinking not over the integers as a whole but modulo some integer
nn
instead can prove quite useful in a number of situation. This chapter attempts to introduce to you the basic concepts of working in such a context.

Congruences

For the following chapter, we will assume
nn
is a natural integer, and
aa
and
bb
are two integers. We say that
aa
and
bb
are congruent modulo
nn
when
n(ba)n\mid (b-a)
, or equivalently when there is an integer
kk
such that
a=b+kna=b+kn
. We denote this by
ab [n]a\equiv b~ [n]
or
abmodna \equiv b\mod n
. I will use the first notation throughout this chapter.
Remark: When
b0b\neq0
, we have
ar [b]a\equiv r~[b]
, where
rr
is the remainder in the euclidean division of
aa
by
This relation has a number of useful properties:
    cZ,ab [n]    acbc [n]\forall c\in \mathbb Z, a\equiv b~[n] \implies ac \equiv bc ~ [n]
    cZ,ab [n]    a+cb+c [n]\forall c \in \mathbb Z, a\equiv b~[n] \implies a+c\equiv b+c ~[n]
    cZ,ab [n] and bc [n]    ac [n]\forall c \in \mathbb Z, a \equiv b ~[n] \text{ and } b\equiv c~[n]\implies a\equiv c ~[n]
    mN,ab [n]    ambm [n]\forall m \in \mathbb N, a\equiv b~[n] \implies a^m\equiv b^m ~[n]
    The proofs are left as an exercise to the reader :p (Hint: go back to the definition)
Seeing as addition and multiplication are well defined, the integers modulo
nn
form a ring, which we note
Z/nZ\mathbb Z/n\mathbb Z
. In sage, you can construct such ring with either of the following
1
Zn = Zmod(5)
2
Zn = Integers(5)
3
Zn = IntegerModRing(5)
4
# Ring of integers modulo 5
5
Zn(7)
6
# 2
7
Zn(8) == Zn(13)
8
# True
Copied!
Powering modulo
nn
is relatively fast, thanks to the double-and-square algorithm, so we needn't worry about it taking too much time when working with high powers
1
pow(2, 564654533, 7) # Output result as member of Z/7Z
2
# 4
3
power_mod(987654321, 987654321, 7) # Output result as simple integer
4
# 6
5
Zmod(7)(84564685)^(2^100) # ^ stands for powering in sage. To get XOR, use ^^.
6
# 5
Copied!
As a side note, remember that if an equality holds over the integers, then it holds modulo any natural integer
nn
. This can be used to prove that a relation is never true by finding a suitable modulus, or to derive conditions on the potential solutions of the equation.
Example: by choosing an appropriate modulus, show that not even god is able to find integers
aa
and
bb
such that
a2=2+4ba^2 = 2 + 4b

Modular Inverse

Since we can multiply, a question arises: can we divide? The answer is yes, under certain conditions. Dividing by an integer
cc
is the same as multiplying by its inverse; that is we want to find another integer
dd
such that
cd1 [n]cd\equiv 1~[n]
. Since
cd1 [n]    kZ,cd=1+kncd\equiv 1~[n]\iff\exists k\in\mathbb Z, cd = 1 + kn
, it is clear from Bézout's Identity that such an inverse exists if and only if
gcd(c,n)=1\gcd(c, n) = 1
. Therefore, the units modulo
nn
are the integers coprime to
nn
, lying in a set we call the unit group modulo
nn
:
(Z/nZ)×\left(\mathbb Z/n\mathbb Z\right)^\times
1
Zn = Zmod(10)
2
Zn(7).is_unit()
3
# True
4
Zn(8).is_unit()
5
# False
6
3 == 1/Zn(7) == Zn(7)^(-1) == pow(7,-1,10) # member of Z/10Z
7
# True
8
inverse_mod(7, 10) # simple integer
9
# 3
10
Zn(3)/7
11
# 9
12
Zn(3)/8
13
# ZeroDivisionError: inverse of Mod(8, 10) does not exist
14
Zn.unit_group()
15
# Multiplicative Abelian group isomorphic to C4 (C4 being the cyclic group of order 4)
Copied!
Finding the modular inverse of a number is an easy task, thanks to the extended euclidean algorithm (that outputs solutions in
dd
and
kk
to the equation
cdkn=1cd-kn=1
from above).
1
xgcd(7, 10) # find (gcd(a, b), u, v) in au + bv = gcd(a, b)
2
# (1, 3, -2) <-- (gcd(7, 10), d, -k)
Copied!
Last modified 4mo ago
Export as PDF
Copy link