CryptoBook

Search…

Fundamentals

Number Theory

Abstract algebra

Elliptic Curves

Lattices

Asymmetric Cryptography

Symmetric Cryptography

Isogeny Based Cryptography

Appendices

Powered By GitBook

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

$n$

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*congruent* modulo

$n$

is a natural integer, and$a$

and$b$

are two integers. We say that$a$

and$b$

are $n$

when$n\mid (b-a)$

, or equivalently when there is an integer$k$

such that$a=b+kn$

. We denote this by$a\equiv b~ [n]$

or $a \equiv b\mod n$

. I will use the first notation throughout this chapter.Remark: When

$b\neq0$

, we have$a\equiv r~[b]$

, where$r$

is the remainder in the euclidean division of$a$

byThis relation has a number of useful properties:

$\forall c\in \mathbb Z, a\equiv b~[n] \implies ac \equiv bc ~ [n]$

$\forall c \in \mathbb Z, a\equiv b~[n] \implies a+c\equiv b+c ~[n]$

$\forall c \in \mathbb Z, a \equiv b ~[n] \text{ and } b\equiv c~[n]\implies a\equiv c ~[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

$n$

form a ring, which we note$\mathbb Z/n\mathbb Z$

. In sage, you can construct such ring with either of the following1

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

$n$

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 powers1

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

$n$

. 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

$a$

and$b$

such that$a^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*units* modulo

$c$

is the same as multiplying by its inverse; that is we want to find another integer$d$

such that$cd\equiv 1~[n]$

. Since$cd\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$

. Therefore, the $n$

are the integers coprime to$n$

, lying in a set we call the unit group modulo$n$

: $\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

$d$

and$k$

to the equation$cd-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