Furkan's Blog

Part 2: Prime Numbers | Public-Key Cryptography

Part 2: Prime Numbers | Public-Key Cryptography

A smooth introduction to prime numbers

Furkan Akal's photo
Furkan Akal
·

10 min read

Hello everyone! Welcome to the second part of the public-key cryptography series! This part is intended to give an introduction for prime numbers and their pivotal role in public-key cryptography. Additionally, you’ll find some relevant code snippets (written in Rust) to support the given mathematical idea.

Contents

  1. What is a prime number, though?

    1. Definition and Basic Properties

      1. Definition

      2. Unique Factorization

      3. Infinitude of Prime Numbers

    2. History

  2. How to find them?

    1. Trial Division

    2. Sieve of Eratosthenes

    3. Probabilistic Tests

  3. Modular Arithmetic

    1. Definition

    2. Example

    3. Modular Inverse

    4. Euclidean Algorithm

    5. Extended Euclidean Algorithm

  4. From Theory to Hands-On Practice

    1. Rust Code

  5. Conclusion

What is a prime number, though?

Definition and Basic Properties

Definition: A natural number is called a prime number (or prime) if it is greater than 1 and cannot be written as the product of two smaller natural numbers.

For example, 13 is prime because the only way of writing it as a product, 1 × 13 or 13 × 1. However, 14 is not prime because it can be written as a product, 7 × 2 or 2 × 7.

Prime Factorization

Writing a natural number as a product of prime numbers is called a prime factorization of the number. For example:

The terms in the expression are called prime factors.

The fundamental significance of prime numbers to number theory in general comes from the fundamental theorem of arithmetic.

Fundamental Theorem of Arithmetic: Every integer larger than 1 can be written as a product of one or more primes.

More strongly, this product is unique in the sense that any two prime factorizations of the same number will have the same numbers of copies of the same primes, although their ordering may differ. So, although there are many different ways of finding a factorization using an integer factorization algorithm, they all must produce the same result. Primes can thus be considered the "basic building blocks" of the natural numbers.

Infinitude of Prime Numbers

There are infinitely many prime numbers, so the following sequence never ends:

We have many proofs for this statement.

Euclid’s Proof: Euclid proposed a proof published in his well-known Elements.

Consider any finite list of prime numbers:

Let P be the product of all the prime numbers in this list:

Now, let q = P + 1. Then q is either prime, or not:

  • If q is prime, then there is at least one more prime that is not in the list, q itself.

  • If q is not prime, then some prime factor p is supposed to divide q. But p also divides P + 1 = q, as just proposed. If p divides P and also q, then p must also divide the difference (that is equal to 1). Since no prime number divides 1, p cannot be in the list. This means that at least one more prime number exists beyond those in the list.

History

The Rhind Mathematical Papyrus, from around 1550 BC, has Egyptian fraction expansions of different forms for prime and composite numbers. However, the earliest surviving records of the study of prime numbers come from the ancient Greek mathematians, who called them prōtos arithmòs (πρῶτος ἀριθμὸς). Euclid's Elements (c. 300 BC) proves the infinitude of primes and the fundamental theorem of arithmetic, and shows how to construct a perfect number from a Mersenne prime.

Around 1000 AD, the Islamic mathematician Ibn al-Haytham (Alhazen) found Wilson's theorem, characterizing the prime numbers as the numbers n that evenly divide

He also conjectured that all even perfect numbers come from Euclid's construction using Mersenne primes, but was unable to prove it.

In 1640, Pierre de Fermat stated Fermat’s Little Theorem.

Fermat’s Little Theorem: If p is a prime and a is any integer not divisible by p, then a p − 1 − 1 is divisible by p.

In 1742, Christian Goldbach formulated Goldbach’s conjecture:

Goldbach’s Conjecture: Every even natural number greater than 2 is the sum of two prime numbers.

How to find them?

Trial Division

It is the most intuitive and straightforward method to determine if an integer is prime. You basically;

  1. begin with the smallest prime number 2,

  2. divide the given number by the prime number to check if it’s a divisor,

  3. repeat the process by performing the division by the next prime.

As you may notice, this method is effective for small numbers or numbers with small factors. It becomes impractical for large numbers as the number of divisions (and the time required) increase rapidly.

Sieve of Eratosthenes

It is one of the ancient methods to find all prime numbers up to a specified integer. You;

  1. start by listing all the numbers from 2 to the maximum number N you' chose,

  2. identify the first prime in the list, which is 2,

  3. remove all multiples of this prime number from the list except the prime itself (2, 4, 6, 8, …),

  4. move to the next number in the list that has not been removed, that is the next prime,

  5. repeat the process.

Probabilistic Tests

Modular Arithmetic

Definition: Given an integer n > 1, called a modulus, two integers a and b are said to be congruent modulo n, if n is a divisor of their difference; that is, if there is an integer k such that

Congruence modulo n is denoted as

Example

In modulus 17:

Because the difference is 62 - 28 = 34 = 2 × 17, a multiple of 17.

Equivalently, 62 and 28 have the same remainder when 11 when divided by 17.

Modular Inverse

Notion of modular inverse and finding the modular inverse of an integer are crucially important in cryptography.

A modular inverse of an integer a is an integer b such that the product ab is congruent to 1 with respect to the modulus m.

This congruence is written as

Our goal is to find such b for an integer a for given modulo m.

Euclidean Algorithm

Recall from high school that greatest common divisor (GCD) of two integers x and y is the largest integer that divides both x and y.

The Euclidean algorithm is a technique for finding the GCD of two integers.

  1. Given two integers a and b, ensure a\>b. If a<b, swap them.

  2. Divide a by b, and take note of the remainder, r.

  3. Replace a with b and b with r.

  4. Repeat steps 2 and 3 until b becomes 0. The non-zero remainder at this point, which will be in the place of a, is the GCD of the original a and b.

Example:

To find gcd⁡(48,18)gcd(48,18):

  • Step 1: 48 divided by 18 gives a remainder of 12 (48=18×2+12).

  • Step 2: Replace 48 with 18 and 18 with 12, then divide 18 by 12 giving a remainder of 6 (18=12×1+6).

  • Step 3: Replace 18 with 12 and 12 with 6, then divide 12 by 6 giving a remainder of 0 (12=6×2+0).

  • Since the remainder is 0, the GCD is the last non-zero remainder, which is 6.

Extended Euclidean Algorithm

The Extended Euclidean algorithm is an extension of the Euclidean Algorithm. It not only finds the GCD of two integers a and b but also finds integers x and y (coefficients) such that ax + by \= gcd(a, b).

Algorithm Steps:

  1. Initialize two pairs of coefficients (x1​, y1​)=(1, 0) and (x2​, y2​)=(0, 1). These represent the coefficients for a and b in the equation ax + by \= gcd(a, b).

  2. Perform the Euclidean Algorithm steps on a and b. Simultaneously, update the coefficients x1​, y1​, x2​, and y2​ with each division step.

    • After each division a\=bq + r, update a and b as in the Euclidean algorithm.

    • Update x1​ and y1​ to x2​ and y2​, respectively.

    • Update x2​ and y2​ to x1​ − q × x2​ and y1​ − q × y2​, respectively.

  3. Continue until b becomes 0. At this point, a is the GCD, and x1​ and y1​ will be the coefficients that satisfy ax + by \= gcd(a, b).

Example:

To find coefficients x and y such that 48x + 18y \= gcd(48, 18):

Following the steps of the algorithm will lead you to calculate the coefficients alongside finding the GCD. For this particular example, you'll end up with specific x and y values that, when multiplied by 48 and 18 respectively and added, equal 6 (the GCD).

From Theory to Hands-On Practice

Rust Code

Let us start by initializing our function with some initial variable assignments:

fn mod_inverse(a: i64, m: i64) -> i64 {
    let (mut m0, mut x0, mut x1) = (m, 0, 1);
    let mut a = a;
}

  • m0 is set to m to remember the original value of m throughout the algorithm.

  • x0 and x1 are initialized to 0 and 1, respectively. These variables are used to keep track of the coefficients of a and m in the Extended Euclidean algorithm. By the end of the algorithm, x1 will hold the modular inverse of a modulo m.

Before diving deeper, we need to handle an edge case.

    if m == 1 {
        return 0;
    }
  • If m is 1, the function immediately returns 0 as the modular inverse does not exist in this case.

Now, we can construct the algorithm using a loop:

    while a > 1 {
        let q = a / m;
        let t = m;
        m = a % m; a = t;
        let t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

  • The loop will iterate as long as a is greater than 1.

  • q is the quotient of the division of a by m.

  • The algorithm then updates a and m using the Euclidean algorithm to find the GCD. So m becomes a%m and a takes on the old value of m.

  • Simultaneously, it updates x0 and x1, which are tracking the coefficients for a and m that would be used to express the GCD as a linear combination of a and m. The goal here is to keep updating these coefficients until we find the modular inverse.

Before returning the modular inverse, let’s be cool and check if the result needs any sign adjustment:

    if x1 < 0 {
        x1 += m0;
    }
  • Once the loop exits, x1 may hold the modular inverse of a modulo m, but it might be negative. In such a case, we just add m0 to ensure the modular inverse is positive.

Now, it’s time to return the modular inverse, which is completing our function:

    return x1

OR

    x1

In Rust, the final expression in the function is used as return value.

So, final version of our code is as follows:

fn mod_inverse(mut a: i64, mut m: i64) -> i64 {
    let (m0, mut x0, mut x1) = (m, 0, 1);

    if m == 1 {
        return 0;
    }

    while a > 1 {
        let q = a / m;
        let t = m;
        m = a % m; a = t;
        let t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if x1 < 0 {
        x1 += m0;
    }

    x1
}

Let’s see if it’s working. We can try to find the modular inverse of 4 modulo 11:

fn main() {
    println!("{}", mod_inverse(4, 11));
}

Output:

3

It’s correct, right? If you multiply 4 by 3, you obtain 12 that is equivalent to 1 in mod 11.

You can test this code by yourself on Rust Playground.

Conclusion

In this post, we've delved into the world of prime numbers and modular arithmetic, exploring their pivotal roles within the historical evolution of mathematics. We've also discussed the Euclidean algorithm, a cornerstone for understanding how to compute the modular inverse—a critical operation in cryptographic systems. To bridge theory with practice, I've provided a Rust code snippet that demonstrates how to calculate the modular inverse of an integer modulo m.

Looking ahead, the next post will shift focus to cryptographic key pairs. We'll explore their significance in securing digital communication and walk through the process of generating them. This upcoming discussion promises to further demystify the complex yet intriguing field of cryptography, equipping you with the knowledge to understand and apply these concepts in real-world scenarios.

Image Reference

https://en.wikipedia.org/wiki/Rhind_Mathematical_Papyrus#/media/File:Rhind_Mathematical_Papyrus.jpg

https://en.wikipedia.org/wiki/Eratosthenes#/media/File:Eratosthenes_profile.png

Cryptographypublic key cryptography