CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • Introduction
  • Congruences
  • Modular Inverse

Was this helpful?

Export as PDF
  1. Fundamentals

Modular Arithmetic

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

PreviousEuclidean AlgorithmNextTheorems of Wilson, Euler, and Fermat

Last updated 3 years ago

Was this helpful?

Introduction

Thinking not over the integers as a whole but modulo some integernnninstead 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 assumennnis a natural integer, andaaaandbbbare two integers. We say thataaaandbbbare congruent modulonnnwhenn∣(b−a)n\mid (b-a)n∣(b−a), or equivalently when there is an integerkkksuch thata=b+kna=b+kna=b+kn. We denote this bya≡b [n]a\equiv b~ [n]a≡b [n]or a≡bmod  na \equiv b\mod na≡bmodn. I will use the first notation throughout this chapter.

Remark: Whenb≠0b\neq0b=0, we havea≡r [b]a\equiv r~[b]a≡r [b], whererrris the remainder in the euclidean division ofaaaby

This relation has a number of useful properties:

  • ∀c∈Z,a≡b [n]  ⟹  ac≡bc [n]\forall c\in \mathbb Z, a\equiv b~[n] \implies ac \equiv bc ~ [n]∀c∈Z,a≡b [n]⟹ac≡bc [n]

  • ∀c∈Z,a≡b [n]  ⟹  a+c≡b+c [n]\forall c \in \mathbb Z, a\equiv b~[n] \implies a+c\equiv b+c ~[n]∀c∈Z,a≡b [n]⟹a+c≡b+c [n]

  • ∀c∈Z,a≡b [n] and b≡c [n]  ⟹  a≡c [n]\forall c \in \mathbb Z, a \equiv b ~[n] \text{ and } b\equiv c~[n]\implies a\equiv c ~[n]∀c∈Z,a≡b [n] and b≡c [n]⟹a≡c [n]

  • ∀m∈N,a≡b [n]  ⟹  am≡bm [n]\forall m \in \mathbb N, a\equiv b~[n] \implies a^m\equiv b^m ~[n]∀m∈N,a≡b [n]⟹am≡bm [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 modulonnnform a ring, which we noteZ/nZ\mathbb Z/n\mathbb ZZ/nZ. In sage, you can construct such ring with either of the following

Zn = Zmod(5)
Zn = Integers(5)
Zn = IntegerModRing(5)
# Ring of integers modulo 5
Zn(7)
# 2
Zn(8) == Zn(13)
# True
pow(2, 564654533, 7) # Output result as member of Z/7Z
# 4
power_mod(987654321, 987654321, 7) # Output result as simple integer
# 6
Zmod(7)(84564685)^(2^100) # ^ stands for powering in sage. To get XOR, use ^^.
# 5

Modular Inverse

Zn = Zmod(10)
Zn(7).is_unit()
# True
Zn(8).is_unit()
# False
3 == 1/Zn(7) == Zn(7)^(-1) == pow(7,-1,10) # member of Z/10Z
# True
inverse_mod(7, 10) # simple integer
# 3
Zn(3)/7
# 9
Zn(3)/8
# ZeroDivisionError: inverse of Mod(8, 10) does not exist
Zn.unit_group()
# Multiplicative Abelian group isomorphic to C4 (C4 being the cyclic group of order 4)
xgcd(7, 10) # find (gcd(a, b), u, v) in au + bv = gcd(a, b)
# (1, 3, -2) <-- (gcd(7, 10), d, -k)

Powering modulonnnis relatively fast, thanks to the algorithm, so we needn't worry about it taking too much time when working with high powers

As a side note, remember that if an equality holds over the integers, then it holds modulo any natural integernnn. 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 integersaaaandbbbsuch thata2=2+4ba^2 = 2 + 4ba2=2+4b

Since we can multiply, a question arises: can we divide? The answer is yes, under certain conditions. Dividing by an integercccis the same as multiplying by its inverse; that is we want to find another integerdddsuch thatcd≡1 [n]cd\equiv 1~[n]cd≡1 [n]. Sincecd≡1 [n]  ⟺  ∃k∈Z,cd=1+kncd\equiv 1~[n]\iff\exists k\in\mathbb Z, cd = 1 + kncd≡1 [n]⟺∃k∈Z,cd=1+kn, it is clear from that such an inverse exists if and only ifgcd⁡(c,n)=1\gcd(c, n) = 1gcd(c,n)=1. Therefore, the units modulonnnare the integers coprime tonnn, lying in a set we call the unit group modulonnn: (Z/nZ)×\left(\mathbb Z/n\mathbb Z\right)^\times(Z/nZ)×

Finding the modular inverse of a number is an easy task, thanks to the (that outputs solutions indddandkkkto the equationcd−kn=1cd-kn=1cd−kn=1from above).

double-and-square
Bézout's Identity
extended euclidean algorithm