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
  • Euclidean Algorithm
  • Algorithm
  • Extended Euclidean Algorithm

Was this helpful?

Export as PDF
  1. Fundamentals
  2. Division and Greatest common divisor

Euclidean Algorithm

Introduction

Although we have functions that can compute our gcd⁡\gcdgcdeasily it's important enough that we need to give and study an algorithm for it: the euclidean algorithm.

It's extended version will help us calculate modular inverses which we will define a bit later.

Euclidean Algorithm

Important Remark

If a=b⋅q+ra = b \cdot q + ra=b⋅q+rand d=gcd⁡(a,b)d = \gcd(a, b)d=gcd(a,b) then d∣rd | rd∣r. Therefore gcd⁡(a,b)=gcd⁡(b,r)\gcd(a, b) = \gcd(b, r)gcd(a,b)=gcd(b,r)

Algorithm

We write the following:

a=q0⋅b+r0b=q1⋅r0+r1r0=q2⋅r1+r2⋮rn−2=rn−1⋅qn−1+rnrn=0 a = q_0 \cdot b + r_0 \\ b = q_1 \cdot r_0 + r_1 \\ r_0 = q_2 \cdot r_1 + r_2 \\ \vdots \\ r_{n-2} = r_ {n-1} \cdot q_{n - 1} + r_n \\ r_n = 0a=q0​⋅b+r0​b=q1​⋅r0​+r1​r0​=q2​⋅r1​+r2​⋮rn−2​=rn−1​⋅qn−1​+rn​rn​=0

Or iteratively rk−2=qk⋅rk−1+rkr_{k-2} = q_k \cdot r_{k-1} + r_krk−2​=qk​⋅rk−1​+rk​ until we find a 000. Then we stop

Now here's the trick:

gcd⁡(a,b)=gcd(b,r0)=gcd(r0,r1)=⋯=gcd⁡(rn−2,rn−1)=rn−1=d\gcd(a, b) = gcd(b, r_0) = gcd(r_0, r_1) = \dots = \gcd(r_{n-2}, r_{n-1}) = r_{n-1} = dgcd(a,b)=gcd(b,r0​)=gcd(r0​,r1​)=⋯=gcd(rn−2​,rn−1​)=rn−1​=d

If d=gcd⁡(a,b)d = \gcd(a, b)d=gcd(a,b) then ddd divides r0,r1,...rn−1r_0, r_1, ... r_{n-1}r0​,r1​,...rn−1​

Pause and ponder. Make you you understand why that works.

Example:

Calculate gcd⁡(24,15)\gcd(24, 15)gcd(24,15)

24=1⋅15+915=1⋅9+69=1⋅6+36=2⋅3+0⇒3=gcd⁡(24,15)24 = 1 \cdot 15 + 9 \\ 15 = 1 \cdot 9 + 6 \\ 9 = 1 \cdot 6 + 3 \\ 6 = 2 \cdot 3 + 0 \Rightarrow 3 = \gcd(24, 15) 24=1⋅15+915=1⋅9+69=1⋅6+36=2⋅3+0⇒3=gcd(24,15)

Code

def my_gcd(a, b):
    # If a < b swap them
    if a < b: 
        a, b = b, a
    # If we encounter 0 return a
    if b == 0: 
        return a
    else:
        r = a % b
        return my_gcd(b, r)

print(my_gcd(24, 15))
# 3

Exercises:

  1. Pick 2 numbers and calculate their gcd⁡\gcdgcdby hand.

  2. Implement the algorithm in Python / Sage and play with it. Do not copy paste the code

Extended Euclidean Algorithm

This section needs to be expanded a bit.

Bezout's identity

Let d=gcd⁡(a,b)d = \gcd(a, b)d=gcd(a,b). Then there exists u,vu, vu,v such that au+bv=dau + bv = dau+bv=d

The extended euclidean algorithm aims to find d=gcd⁡(a,b), and u,vd = \gcd(a, b), \text{ and }u, vd=gcd(a,b), and u,vgiven a,ba, ba,b

# In sage we have the `xgcd` function
a = 24
b = 15
g, u, v = xgcd(a, b)
print(g, u, v)
# 3 2 -3 

print(u * a + v * b)
# 3 -> because 24 * 2 - 15 * 3 = 48 - 45 = 3

PreviousDivision and Greatest common divisorNextModular Arithmetic

Last updated 4 years ago

Was this helpful?