Devil's Night

Much of modern cryptography is built on the foundation of linear algebra and number theory. At the most basic level, Number theory is the study of natural numbers

Definition

Let a and b be integers with b != 0, We say that b divides a, or a is divisible by b, if there is an integer c such that:

a = bc

We write b | a to indicates with b != 0. If b does not divides a, we write b ∤ a
Example: 2 | 8 because 8 = 2 * 4, and 2 ∤ 7 because we try to divide 7 by 2 then we get a reminder of 1.

Proposition

(a) If a | b and b | c then a | c.
(b) If a | b and b | a then a = ±b
(c) If a | b and a | c then a | (b ± c)

Proof

(a) From a | b and b | c then we get b = a*m and c = n*b, then c = n*m*a. So a | c
(b) a | b means b = n*a; b | a means a = m*b. then a = ±b.
(c) a|b means b = n*a, a|c means c = m*a. So b±c = (m±n)a, then a|(b±c)

Common Divisor

A common divisor of two integers a and b is a positive integer d that divides both of them. Most of the time two numbers could have more than one common divisors, Greatest Common Divisor is the greatest one, denoted as gcd(a,b).

Example:

gcd(12, 32) = 4.

One way to find a greatest common divisor is by listing all the divisors of 2 numbers:

Divisors of 12 = (1, 2, 3, 4)
Divisors of 32 = (1, 2, 4, 8, 16)
Then find those common ones
Common divisor of 12 and 32 = (1, 2, 4)
And select the greatest value 4.

The key for calculating this efficiently is division with remainder.

Definition

Let a and b be two positive integers, if a is divisible by b with quotient q and reminder r.
a = b*q + r with 0 ≤ r ≤ b
The value of q and r are uniquely determined by a and b.

From Proposition (c) we find that if a and b have a common divisor d, then d also divides r, which means that common divisors of a and b are common divisors of b and r. Finding gcd of b and r is somehow easier than doing that on a and b since r is less than b. What’s more we can divide b by r again. If there is not reminder, gcd(b.r) = r = gcd(a,b). If there is a reminder r_n. We keep dividing.

The Euclidean Algorithm
r0 <-- a, r1 <-- b.
For i = 1, 2, 3...
Do: divide rr-1 by ri to get a quotient qi and a reminder rr+1
when ri+1 = 0, gcd(a,b) <-- ri, End For.