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
  • Division
  • Greatest common divisor

Was this helpful?

Export as PDF
  1. Fundamentals

Division and Greatest common divisor

Author: Zademn

Introduction

Two of the skills a cryptographer must master are:

  1. Knowing his way and being comfortable to work with numbers.

  2. Understanding and manipulating abstract objects.

This chapter of fundamentals proposes to prepare you for understanding the basics of number theory and abstract algebra .We will start with the most basic concepts such as division and build up knowledge until you, future cryptographer, are able to follow and understand the proofs and intricacies of the cryptosystems that make our everyday life secure.

We will provide examples and snippets of code and be sure to play with them. If math is not your strongest suit, we highly suggest to pause and ponder for each concept and take it slow.

For the math-savy people we cover advanced topics in specific chapters on the subjects of number theory and group theory.

So what are we waiting for? Let's jump right in!

Division

Let Z={…,−1,0,1,2,3… }\mathbb{Z} = \{\dots , -1, 0, 1, 2, 3 \dots \}Z={…,−1,0,1,2,3…}be the set denoting the integers.

Definition - Divisibility

For a,b,∈Za, b, \in \mathbb{Z} a,b,∈Zwe say that aaadivides bbbif there is some k∈Zk \in \mathbb{Z}k∈Zsuch that a⋅k=ba \cdot k = ba⋅k=b

Notation: a∣ba | ba∣b

Example

For a=2,b=6a = 2, b = 6a=2,b=6 we have 2∣62 | 62∣6 because we can find k=3k = 3k=3such that 6=2⋅36 = 2 \cdot 36=2⋅3.

Properties

  • a∣a, 1∣a and a∣0a | a, \ 1 | a \text{ and } a | 0a∣a, 1∣a and a∣0

  • a∣ba | ba∣b and a∣c a | c a∣c implies a∣(bu+cv) ∀u,v,∈Za | (bu + cv) \ \forall u, v, \in \mathbb{Z}a∣(bu+cv) ∀u,v,∈Z

    • Example: Let b=6,u=5b = 6, u = 5b=6,u=5 and c=9,v=2c = 9, v = 2 c=9,v=2

    • 3∣63 | 63∣6 and 3∣9⇒3∣(6⋅5+9⋅2)  ⟺  3∣483 | 9 \Rightarrow 3 | (6 \cdot 5 + 9 \cdot 2) \iff 3 | 483∣9⇒3∣(6⋅5+9⋅2)⟺3∣48 . We can find k=16k = 16k=16such that 48=3⋅1648 = 3 \cdot 1648=3⋅16

  • a∣ba | ba∣b and b∣c b | c b∣c implies a∣c a | ca∣c

  • if a∣ba|ba∣band b∣ab|ab∣a then a=±ba = \pm ba=±b

Definition - Division with remainder

Let a,b∈Za, b \in \mathbb{Z}a,b∈Zwith b≥1b≥1b≥1,

There exists unique q,r∈Zq, r \in \mathbb{Z}q,r∈Zsuch that a=bq+r\boxed{a = bq + r}a=bq+r​and 0≤r<b0 \leq r < b0≤r<b

qq q is called the quotient and rrr the remainder

Examples:

  • To find q,rq, rq,r python offers us the divmod() function that takes a,ba, ba,bas arguments

q, r = divmod(6, 2)
print(q, r)
# 3 0 

q, r = divmod(13, 5)
print(q, r)
# 2 3 
# Note that 13 = 2 * 5 + 3
  • If we want to find only the quotient qqq we can use the // operator

  • If we want to find the remainder rrr we can use the modulo % operator

q = 13 // 5
print(q)
# 2

r = 13 % 5
print(r)
# 3

Exercises:

  1. Now it's your turn! Play with the proprieties of the division in Python and see if they hold.

Greatest common divisor

Definition

Let a,b∈Za, b \in \mathbb{Z}a,b∈Z be 2 integers. The greatest common divisor is the largest integer d∈Zd \in \mathbb{Z}d∈Zsuch that d∣ad | ad∣aand d∣bd | bd∣b

Notation: gcd⁡(a,b)=d\gcd(a, b) = dgcd(a,b)=d

Examples:

# In python we can import math to get the GCD algo
import math
print(math.gcd(18, 12)) # -> 6
# Sage has it already!
print(gcd(18, 12)) # -> 6

Remark:

  • for all other common divisors ccc of a,ba, ba,bwe have c∣dc | dc∣d

Things to think about

What can we say about numbersa,b a, ba,b with gcd⁡(a,b)=1\gcd(a, b) = 1gcd(a,b)=1? How are their divisors?

PreviousMathematical NotationNextEuclidean Algorithm

Last updated 4 years ago

Was this helpful?