Introduction to Number Theory

Lecturer:: Prof. Dr. Michael Eichberg
Version:: 2023-10-19
Based on:: Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings

Divisibility

We say that a nonzero \(b\) divides \(a\) if \(a = mb\) for some \(m\), where \(a\), \(b\) and \(m\) are integers.
\(b\) divides \(a\) if there is no remainder on division.
The notation \(b|a\) is used to mean \(b\) divides \(a\).
If \(b|a\) we say that \(b\) is a divisor of \(a\).

Properties of Divisibility

If \(a|1\), then \(a = \pm 1\).
If \(a | b\) and \(b|a\), then \(a = \pm b\).
Any \(b \neq 0\) divides \(0\).
If \(a | b\) and \(b|c\), then \(a|c\).

Properties of Divisibility

If \(b | g\) and \(b|h\), then \(b|(mg+nh)\) for arbitrary integers \(m\) and \(n\).

Division Algorithm

Given any positive integer \(n\) and any nonnegative integer \(a\), if we divide \(a\) by n we get an integer quotient \(q\) and an integer remainder \(r\) that obey the following relationship:

\begin{equation*} a = qn + r \qquad 0 \leq r < n; q = \left \lfloor{a/n} \right \rfloor \end{equation*}

Division Algorithm for negative a

Euclidean Algorithm

One of the basic techniques of number theory.

Procedure for determing the greatest common divisor (GCD) of two positive integers.

Greatest Common Divisor (GCD)

The greatest common divisor of two integers \(a\) and \(b\) is the largest integer that both divides \(a\) and \(b\).
We use the notation \(gcd(a,b)\) to mean the GCD of \(a\) and b.
We define \(gcd(0,0) = 0\).
The positive integer \(c\) is said to be the gcd of \(a\) and \(b\) if:
- \(c\) is a divisor of \(a\) and \(b\)
- any divisor of \(a\) and \(b\) is a divisor of \(c\).

Greatest Common Divisor (GCD)

Alternative definition:

\begin{equation*} gcd(a,b) = max[k, such\;that\; k|a \; and \; k|b] \end{equation*}

Greatest Common Divisor (GCD)

We stated:

two integers \(a\) and \(b\) are relatively prime iff their only common positive integer factor is 1

\(\Leftrightarrow\)

\(a\) and \(b\) are relatively prime if \(gcd(a,b)=1\)

Greatest Common Divisor (GCD)

Computing the GCD using the Euclidean algorithm.

Greatest Common Divisor (GCD)

Example of computing the GCD using the Euclidean algorithm.

Euclidean Algorithm

Step	Dividend	Divisor	Quotient	Remainder
1	1160718174	316258250	3	211943424
2	316258250	211943424	1	104314826
3	211943424	104314826	2	3313772
4	104314826	3313772	31	1587894
5	3313772	1587894	2	137984
6	1587894	137984	11	70070
7	137984	70070	1	67914
8	70070	67914	1	2156
9	67914	2156	31	1078
10	2156	1078	2	0

Modular Arithmetic

The Modulus

If a is an integer and n is a positive integer, we define \(a\; mod\; n\) to be the remainder when a is divided by n. The integer n is called the modulus.

Thus, for any integer a:

\begin{equation*} a = qn + r \quad 0 \leq r < n; q = \left\lfloor a / n \right\rfloor \end{equation*}

\begin{equation*} a = \left\lfloor a / n \right\rfloor \times n + (a\; mod\; n) \end{equation*}

Modular Arithmetic (Congruent modulo \(n\))

Two integers a and b are said to be congruent modulo n if \((a\; mod\; n) = (b\; mod\; n)\)
This is written as \(a \equiv b(mod\; n)\).
Note that if \(a \equiv 0 (mod\; n)\), then \(n|a\).

Properties of Congruence

Congruences have the following properties:

\(a \equiv b (mod\; n)\) if \(n|(a-b)\)
\(a \equiv b (mod\; n) \Rightarrow b \equiv a (mod\; n)\)
\(a \equiv b (mod\; n)\; and\; b \equiv c (mod\; n) \Rightarrow a \equiv c (mod\; n)\)

Properties of Congruence (Explained)

To demonstrate the first point, if \(n|(a - b)\), then \((a - b) = kn\) for some \(k\)

So we can write \(a=b+kn\)

Therefore, \((a\; mod\; n)\) = (remainder when \(b + kn\) is divided by n) = (remainder when b is divided by n) = \((b\; mod\; n)\)

Example

\(23 = 8(mod\; 5)\) because \(23 - 8 = 15 = 5* 3\)

\(-11 = 5(mod\; 8)\) because \(-11 - 5 = -16 = 8* (-2)\)

\(81 = 0(mod\; 27)\) because \(81 - 0 = 81 = 27* 3\)

Modular Arithmetic

Modular arithmetic exhibits the following properties:

\([(a\; mod\; n) + (b\; mod\; n)]\; mod\; n = (a + b)\; mod\; n\)
\([(a\; mod\; n) - (b\; mod\; n)]\; mod\; n = (a - b)\; mod\; n\)
\([(a\; mod\; n) \times (b\; mod\; n)]\; mod\; n = (a \times b)\; mod\; n\)

Modular Arithmetic (First Property)

Define \((a\; mod\; n) = r_a\) and \((b\; mod\; n) = r_b\). Then we can write \(a = r_a + jn\) for some integer j and \(b = r_b + kn\) for some integer k.

Then:

\begin{equation*} (a + b)\; mod\; n = (r_a + jn + r_b + kn)\; mod\; n \end{equation*}

\begin{equation*} = (r_a + r_b + (k + j)n)\; mod\; n \end{equation*}

\begin{equation*} = (r_a + r_b)\; mod\; n \end{equation*}

\begin{equation*} = [(a\; mod\; n) + (b\; mod\; n)]\; mod\; n \end{equation*}

Modular Arithmetic (Examples of Properties)

Modular Arithmetic Modulo 8

Addition

+	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	2	3	4	5	6	7	0
2	2	3	4	5	6	7	0	1
3	3	4	5	6	7	0	1	2
4	4	5	6	7	0	1	2	3
5	5	6	7	0	1	2	3	4
6	6	7	0	1	2	3	4	5
7	7	0	1	2	3	4	5	6

Modular Arithmetic Modulo 8

Multiplication

×	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7
2	2	4	6	0	2	4	6
3	3	6	1	4	7	2	5
4	4	0	4	0	4	0	4
5	5	2	7	4	1	6	3
6	6	4	2	0	6	4	2
7	7	6	5	4	3	2	1

Modular Arithmetic Modulo 8

Additive and muliplicative inverse modulo 8.

\(w\)	\(-w\)	\(w^{-1}\)
0	0	\(-\)
1	7	1
2	6	\(-\)
3	5	3
4	4	\(-\)
5	3	5
6	2	\(-\)
7	1	7

Properties of Modular Arithmetic for Integers in \(Z_n\)

Commutative Laws:

\((w + x)\; mod\; n = (x + w)\; mod\; n\)

\((w \times x)\; mod\; n = (x \times w)\; mod\; n\)

Associative Laws:

\([(w + x) + y]\; mod\; n = [w + (x + y)]\; mod\; n\)

\([(w \times x) \times y]\; mod\; n = [w \times (x \times y)]\; mod\; n\)

Distributive Law:: \([w \times (x + y)]\; mod\; n = [(w \times x) + (w \times y)]\; mod\; n\)

Identities:: \((0 + w)\; mod\; n = w\; mod\; n\) \((1 \times w)\; mod\; n = w\; mod\; n\)

Additive Inverse (-w):: For each \(w \in Z_n\) there exists a \(z\) such that \(w + z \equiv 0\; mod\; n\)

Euclidean Algorithm Revisited

Euclid(a,b):
    if (b = 0) then return a;
    else return Euclid(b, a mod b);

Example

gcd(10,6)
    ↳ gcd(6,4)
        ↳ gcd(4,2)
            ↳ gcd(2,0)
2              ↩︎

Extended Euclidean Algorithm

Necessary for computations in the area of finite fields and encryption algoritms such as RSA.
For two integers \(a\) and \(b\), the extended Euclidean Algorithm computes the gcd \(d\), but also two additional integers \(x\) and \(y\) that satisfy the following equation:

Note

\(x\) and \(y\) will have oposite signs.

\begin{equation*} ax + by = d = gcd(a,b) \end{equation*}

Extended Euclidean Algorithm - \(gcd(a=42,b=30)\)

Let's take a look at \(ax+by\) for some \(x\) and \(y\):

\(_у \\ ^x\)	-3	-2	-1	0	1	2	3
-3	-216	-174	-132	-90	-48	-6	36
-2	-186	-144	-102	-60	-18	24	66
-1	-156	-114	-72	-30	12	54	96
0	-126	-84	-42	0	42	84	126
1	-96	-54	-12	30	72	114	156
2	-66	-24	18	60	102	144	186
3	-36	6	48	90	132	174	216

Extended Euclidean Algorithm

We assume that at each step \(i\) we can find integers \(x_i\) and \(y_i\) that satisfy: \(r_i = ax_i + by_i\).

\begin{equation*} \begin{matrix} original & extension \\ a = q_1b + r_1 & r_1 = ax_1 + by_1 \\ b = q_2r_1 + r_2 & r_2 = ax_2 + by_2 \\ r_1 = q_3r_2 + r_3 & r_3 = ax_3 + by_3 \\ \vdots & \vdots \\ r_{n-2} = q_nr_{n-1}+r_n & r_n=ax_n + by_n \\ r_{n-1} = q_{n+1}r_n +0 & \\ d = gcd(a,b) = r_n & \end{matrix} \end{equation*}

Extended Euclidean Algorithm

Calculate	Which satisfies	Calculate	Which satisfies
\(r_{-1} = a\)		\(x_{-1}=1; y_{-1}=0\)	\(a = ax_{-1} + by_{-1}\)
\(r_{0} = b\)		\(x_0=0;y_{0}=0\)	\(b = ax_{0} + by_{0}\)
\(r_{1} = a\;mod\;b; q_1= \lfloor a/b \rfloor\)	\(a=q_1b+r_1\)	\(x_1=x_{-1} -q_1x_0 = 1; y_1=y_{-1} -q_1y_0 = -q_1\)	\(r_1 = ax_{1} + by_{1}\)
\(r_{2} = b\;mod\;r_1; q_2= \lfloor b/r_1 \rfloor\)	\(b=q_2r_1+r_2\)	\(x_2=x_{0} -q_2x_1; y_2=y_{0} -q_2y_1\)	\(r_2 = ax_{2} + by_{2}\)
\(r_{3} = r_1\;mod\;r_2; q_3= \lfloor r_1/r_2 \rfloor\)	\(r_1=q_3r_2+r_3\)	\(x_3=x_{1} -q_3x_2; y_3=y_{1} -q_3y_2\)	\(r_3 = ax_{3} + by_{3}\)
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
\(r_{n} = r_{n-2}\;mod\;r_{n-1}; q_n= \lfloor r_{n-2}/r_{n-1} \rfloor\)	\(r_{n-2}=q_nr_{n-1}+r_n\)	\(x_n=x_{n-2} -q_nx_{n-1}; y_n=y_{n-2} -q_ny_{n-1}\)	\(r_n = ax_{n} + by_{n}\)
\(r_{n+1} = r_{n-1}\;mod\;r_{n} = 0; q_{n+1}= \lfloor r_{n-1}/r_{n} \rfloor\)	\(r_{n-1}=q_{n+1}r_{n}+0\)

Solution

\(d = gcd(a,b) = r_n; x = x_n; y = y_n\)

Extended Euclidean Algorithm - Example \(gcd(1759,550)\)

\(i\)	\(r_i\)	\(q_i\)	\(x_i\)	\(y_i\)
-1	1759		1	0
0	550		0	1
1	109	3	1	-3
2	5	5	-5	16
3	4	21	106	-339
4	1	1	-111	355
5	0	4

Result: \(d=1; x= -111; y = 355\)

Prime Numbers

Prime numbers only have divisors of 1 and itself.
They cannot be written as a product of other numbers
Prime numbers are central to number theory
Any integer a > 1 can be factored in a unique way as: \(a=p_1^{a_1} \times p_2^{a_2} \times \dots \times p_t^{a_1}\) where \(p_1 < p_2 < . . . < p_t\) are prime numbers and where each \(a_i\) is a positive integer
This is known as the fundamental theorem of arithmetic.

Fermat's (little) theorem

States the following:

If p is prime and a is a positive integer not divisible by p then \(a^{p-1} \equiv 1 (mod\;p)\)

Alternative form:

If p is prime and a is a positive integer then \(a^p \equiv a(mod\; p)\)

Some values of Euler's Totient Function \(\phi(n)\)

Euler's totient function (\(\phi(n)\).) is defined as the number of positive integers less than n and relatively prime to n; by convention \(\phi(1) = 1\).

𝜑(n)	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+	/	1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

cf. https://de.wikipedia.org/wiki/Eulersche_Phi-Funktion

Euler's Theorem

States that for every a and n that are relatively prime:

\begin{equation*} a^{\phi(n)} \equiv 1(mod\; n) \end{equation*}

An alternative form is:

\begin{equation*} a^{\phi(n)+1} \equiv a (mod\; n) \end{equation*}

Miller-Rabin Algorithm

Many cryptographic algorithms require one or more very large prime numbers at random.
The Miller-Rabin primality test is a probabilistic primality test that is fast and simple.
Background: Any positive odd integer \(n \geq 3\) can be expressed as \(n-1 = 2^kq \qquad with\; k > 0, q\; odd\)

Miller-Rabin Algorithm

TEST(n, k) # n > 2, an odd integer to be tested for primality
           # k, the number of rounds of testing to perform

let s > 0 and d odd > 0 such that n−1 = pow(2,s)*d
repeat k times:
    a ← random(2, n−2)
    x ← pow(a,d) mod n
    repeat s times:
        y ← sqr(x) mod n
        if y = 1 and x ≠ 1 and x ≠ n−1 then return “composite”
        x ← y
    if y ≠ 1 then return “composite”
return “probably prime”

Deterministic Primality Algorithm

Prior to 2002 there was no known method of efficiently proving the primality of very large numbers.
All of the algorithms in use produced a probabilistic result
In 2002 Agrawal, Kayal, and Saxena developed an algorithm that efficiently determines whether a given large number is prime:
- Known as the AKS algorithm.
- Does not appear to be as efficient as the Miller-Rabin algorithm.

Chinese Remainder Theorem (CRT)

Believed to have been discovered by the Chinese mathematician Sun-Tsu in around 100 A.D.
One of the most useful results of number theory.
Says it is possible to reconstruct integers in a certain range from their residues modulo a set of pairwise relatively prime moduli.
Can be stated in several ways.

Chinese Remainder Theorem (CRT) - Example in \(Z_{10}\)

Let's assume that the (relatively prime/coprime) factors of a number \(x\) are \(2\) and \(5\) and

that the known residues of the decimal digit \(x\) are \(r_2 = 0\) and \(r_5 = 3\).

Hence, \(x\; mod \;2 = 0\); i.e., \(x\) has to be an even number; furthermore, \(x\; mod\; 5 = 3\).

The unique solution is: \(8\) (\(3\) is not a solution, because it is odd!)

+	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	2	3	4	5	6	7	0
2	2	3	4	5	6	7	0	1
3	3	4	5	6	7	0	1	2
4	4	5	6	7	0	1	2	3
5	5	6	7	0	1	2	3	4
6	6	7	0	1	2	3	4	5
7	7	0	1	2	3	4	5	6

×	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7
2	2	4	6	0	2	4	6
3	3	6	1	4	7	2	5
4	4	0	4	0	4	0	4
5	5	2	7	4	1	6	3
6	6	4	2	0	6	4	2
7	7	6	5	4	3	2	1

𝜑(n)	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+	/	1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

+	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	2	3	4	5	6	7	0
2	2	3	4	5	6	7	0	1
3	3	4	5	6	7	0	1	2
4	4	5	6	7	0	1	2	3
5	5	6	7	0	1	2	3	4
6	6	7	0	1	2	3	4	5
7	7	0	1	2	3	4	5	6

×	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7
2	2	4	6	0	2	4	6
3	3	6	1	4	7	2	5
4	4	0	4	0	4	0	4
5	5	2	7	4	1	6	3
6	6	4	2	0	6	4	2
7	7	6	5	4	3	2	1

𝜑(n)	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+	/	1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

+	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	2	3	4	5	6	7	0
2	2	3	4	5	6	7	0	1
3	3	4	5	6	7	0	1	2
4	4	5	6	7	0	1	2	3
5	5	6	7	0	1	2	3	4
6	6	7	0	1	2	3	4	5
7	7	0	1	2	3	4	5	6

×	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7
2	2	4	6	0	2	4	6
3	3	6	1	4	7	2	5
4	4	0	4	0	4	0	4
5	5	2	7	4	1	6	3
6	6	4	2	0	6	4	2
7	7	6	5	4	3	2	1

𝜑(n)	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+	/	1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60