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)

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

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

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)
PreviousEuclidean AlgorithmNextTheorems of Wilson, Euler, and Fermat

Last updated 3 years ago

Was this helpful?

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

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