πŸ–ŠοΈ
Crypto
  • Crypto
  • Fundamentals
    • Divisibility, Factors and Euclid's Algorithms
    • Modular Arithmetic
    • Rings, Fields and Euler's Totient Function
  • Further Maths
    • Continued Fractions
  • RSA
    • Overview
    • Public Exponent Attacks
      • e=1
      • Small e
      • Multi-party RSA with Small e
      • Wiener's Attack
    • Choice of Primes
      • N is prime
      • Mersenne Primes
      • P=Q
      • Fermat Factorisation
    • Factorisation Methods
      • Pollard's p-1
  • Diffie-Hellman Key Exchange
    • Overview
    • Solving the DLP
      • Baby Step, Giant Step
Powered by GitBook
On this page
  • Divisibility
  • Greatest Common Divisor
  • Euclidean Algorithm
  • Extended Euclidean Algorithm

Was this helpful?

  1. Fundamentals

Divisibility, Factors and Euclid's Algorithms

An outline of the fundamentals of number theory

PreviousCryptoNextModular Arithmetic

Last updated 3 years ago

Was this helpful?

Cryptography is built on the foundations of algebra and number theory, which we will hopefully cover well enough here.

Divisibility

aaa is said to be divisible by bbb if there is another integer ccc such that a=bca=bca=bc. In this case, bbb is said to be a factor of aaa. This is denoted by a∣ba \mid ba∣b if aaa divides bbb, and a∀ba \nmid ba∀b if it does not.

Greatest Common Divisor

Given two integers aaa and bbb, the greatest common divisor gcd(a,b)gcd(a,b)gcd(a,b) (also known as the highest common factor) is the largest integer ppp where p∣ap \mid ap∣a and p∣bp \mid bp∣b.

Euclidean Algorithm

Given aaa and bbb, we can write an equation linking the two:

a=bβ‹…q+ra = b \cdot q + ra=bβ‹…q+r

​Where qqq and rrr are integers which fit the equation with r<br < br<b. Basically, bbb divides into aaa a maximum of qqq times with a remainder of rrr. But here's where the trick lies.

Every term added together in that equation must be divisible by gcd(a,b)gcd(a,b)gcd(a,b) because if we treat the gcd as ggg we can say that a=k1g,b=k2ga=k_1g,b=k_2ga=k1​g,b=k2​g​:

k1g=k2gβ‹…q+rk_1g = k_2g \cdot q + rk1​g=k2​gβ‹…q+r

This is quite a leap forward which will require a bit of thinking, but let's break it down algebraically:

I highly recommend you think about this for a bit until it makes sense to you, and make sure to use other resources if it helps!

Example

And now we attempt to calculate the GCD of 8075 and 133.

Therefore the GCD of 16283 and 8075 is 19.

Extended Euclidean Algorithm

This extension of the algorithm is invaluable for calculating modular inverses of numbers and is based on using the Euclidean Algorithm to calculate the GCD then writing it in terms of other numbers, repeating the process for the smallest non-GCD number until we reach an equation with only the GCD and the two starting numbers. Let's work with the example above, writing an equation for the GCD:

Now 38 is the smallest non-GCD number, and we can write it in terms of the larger number in the sequence of equations written in the example, then repeat for the next smallest:

Meaning rrr has to be some integer multiple of ggg​.

But now, if we think outside the box, we realise that both bbb and rrr are divisible by gcd(a,b)gcd(a,b)gcd(a,b)... so we can just calculate gcd(b,r)gcd(b, r)gcd(b,r)!

a=bβ‹…q0+r1b=r1β‹…q1+r2r1=r2β‹…q2+r3r2=r3β‹…q3+r4a = b \cdot q_0 + r_1 \\ b = r_1 \cdot q_1 + r_2 \\ r_1 = r_2 \cdot q_2 + r_3 \\ r_2 = r_3 \cdot q_3 + r_4 \\a=bβ‹…q0​+r1​b=r1​⋅q1​+r2​r1​=r2​⋅q2​+r3​r2​=r3​⋅q3​+r4​

And so on. But when does it stop? When do we stop taking the GCD? Well we can stop taking the GCD once rn=0r_n = 0rn​=0, in which case rnβˆ’1∣rnβˆ’2r_{n-1} \mid r_{n-2}rnβˆ’1β€‹βˆ£rnβˆ’2​ and as a result we can take rnβˆ’1r_{n-1}rnβˆ’1​ as the GCD!

Let’s say we want to find the GCD of 8075 and 16283. First, we can write it in the form a=bβ‹…q+ra= b \cdot q+r a=bβ‹…q+r:

16283=8075β‹…2+13316283 = 8075Β·2 + 13316283=8075β‹…2+133
8075=133β‹…60+95133=95β‹…1+3895=38β‹…2+1938=19β‹…2+08075 = 133 \cdot 60 + 95 \\ 133 = 95 \cdot 1 + 38 \\ 95 = 38 \cdot 2 + 19 \\ 38 = 19 \cdot 2 + 08075=133β‹…60+95133=95β‹…1+3895=38β‹…2+1938=19β‹…2+0

We can take the Euclidean Algorithm a step further and calculate, in addition to the GCD, u,v∈Zu,v \in \mathbb{Z}u,v∈Z for a,ba,ba,b which sum to the GCD, i.e.

au+bv=gcd(a,b) au + bv = gcd(a,b) au+bv=gcd(a,b)
19=95βˆ’38β‹…219 = 95 - 38 \cdot 219=95βˆ’38β‹…2
19=95βˆ’38β‹…2=95βˆ’(133βˆ’95β‹…1)β‹…2=95βˆ’(133β‹…2+95β‹…βˆ’2)=95β‹…3+133β‹…βˆ’2=(8075+133β‹…βˆ’60)β‹…3+133β‹…βˆ’2=8075β‹…3+133β‹…βˆ’180+133β‹…βˆ’2=8075β‹…3+133β‹…βˆ’182=8075β‹…3+(16283+8075β‹…βˆ’2)β‹…βˆ’182=8075β‹…3+16283β‹…βˆ’182+8075β‹…364=8075β‹…367+16283β‹…βˆ’18219 = 95 - 38 \cdot 2 \\ = 95 - (133 - 95 \cdot 1) \cdot 2 \\ = 95 - (133 \cdot 2 + 95 \cdot -2) \\ = 95 \cdot 3 + 133 \cdot -2 \\ = (8075 + 133 \cdot -60) \cdot 3 + 133 \cdot -2 \\ = 8075 \cdot 3 + 133 \cdot -180 + 133 \cdot -2 \\ = 8075 \cdot 3 + 133 \cdot -182 \\ = 8075 \cdot 3 + (16283 + 8075 \cdot -2) \cdot -182 \\ = 8075 \cdot 3 + 16283 \cdot -182 + 8075 \cdot 364 \\ = 8075 \cdot 367 + 16283 \cdot -18219=95βˆ’38β‹…2=95βˆ’(133βˆ’95β‹…1)β‹…2=95βˆ’(133β‹…2+95β‹…βˆ’2)=95β‹…3+133β‹…βˆ’2=(8075+133β‹…βˆ’60)β‹…3+133β‹…βˆ’2=8075β‹…3+133β‹…βˆ’180+133β‹…βˆ’2=8075β‹…3+133β‹…βˆ’182=8075β‹…3+(16283+8075β‹…βˆ’2)β‹…βˆ’182=8075β‹…3+16283β‹…βˆ’182+8075β‹…364=8075β‹…367+16283β‹…βˆ’182

Therefore our equation au+bv=gcd(a,b)au + bv = gcd(a,b)au+bv=gcd(a,b) is as follows:

16283β‹…βˆ’182+8075β‹…367=1916283 \cdot -182 + 8075 \cdot 367 = 1916283β‹…βˆ’182+8075β‹…367=19