AHdark Blog

Due to being busy with company affairs and the architectural design of a new system recently, the blog has not been updated for several months. The past few months have brought significant changes to my personal life, and while it's hard to articulate the specifics, they will likely be reflected in future blog updates.

However, I believe that not updating is not a good thing and should be avoided. Therefore, I am taking a moment today to write the first article for a blog that has not been updated for five months.

Preface#

Mathematics is the foundation of science, and prime numbers are one of the cornerstones of mathematics. Although the concept of prime numbers is simple and intuitive—natural numbers that have only two positive factors: 1 and themselves—they play an important role in mathematics and computer science.

Prime numbers are not something we discovered independently; they exist in nature according to complex rules. Through understanding and applying prime numbers, we can solve various problems, from cryptographic algorithms in cryptography to data structures in search engines, and even to the future development of quantum computing. Therefore, effectively determining whether a number is prime is a crucial skill in programming.

In this blog article, we will delve into the implementation of prime number verification in program design. We will start with basic mathematical theory and gradually move into the optimization of various algorithms. We will also explore different prime number testing algorithms, from the most basic trial division to more complex and efficient algorithms (such as the Miller–Rabin primality test), to appreciate the history and evolution of algorithms.

Basic Knowledge of Prime Numbers#

Before we dive into how to verify prime numbers in programs, we need to understand what prime numbers are and why they are so important in computer science.

A prime number is a special type of number that has only two factors: 1 and itself. The simplest prime number is 2, followed by 3, 5, 7, 11, 13, and so on. In the ocean of natural numbers, prime numbers are like scattered pearls, waiting for us to discover and appreciate them.

The importance of these numbers in mathematics is undeniable, and their role in computer science is equally significant. Many fields of computer science, including but not limited to cryptography, data structures, and parallel computing, extensively use prime numbers. For example, in cryptography, large prime numbers are used to generate public and private keys, providing strong security. In data structures, prime numbers are often used as parameters for hash functions to improve hashing efficiency and reduce the likelihood of collisions.

So, how do we determine whether a number is prime? This is the topic we will discuss next: verifying prime numbers in programs.

Exhaustive Search#

Before we explore more efficient prime number testing algorithms, it is necessary to understand the most basic and intuitive method of prime number verification—exhaustive search. Although this method does not excel in time and space complexity, its straightforward logic makes it an important tool for understanding prime numbers.

The core idea of exhaustive search is to test all positive integers less than $n$ to determine whether $n$ is prime. If we find a positive integer less than $n$ that can divide $n$, then $n$ is not prime; if all positive integers less than $n$ cannot divide $n$, then $n$ is a prime number.

Here is an example:

bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i < n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

In this code, we first check whether $n$ is less than or equal to $1$. If it is, we return false directly, because by definition, prime numbers must be greater than $1$. Then, the code loops through all integers from $2$ to $n-1$, checking whether $n$ can be divided by any of these integers. If it can, then $n$ is not prime, and we return false; if none of these numbers can divide $n$, then $n$ is prime, and we return true.

However, the efficiency of exhaustive search is not high. Its time complexity is $O(n)$, and its space complexity is $O(1)$. In terms of time complexity, since it requires testing all positive integers less than $n$, this method's efficiency is extremely low when $n$ is particularly large.

Trial Division#

Having understood exhaustive search, we can continue to explore a more efficient method of prime number verification—trial division. Compared to exhaustive search, trial division optimizes the process of prime number verification by reducing the numbers that need to be tested, thus significantly improving computational complexity.

The core idea of trial division is: if a number $n$ is composite (i.e., not prime), then it must have a factor that is not greater than its square root. Therefore, to determine whether a number $n$ is prime, we only need to test all integers between $2$ and $\sqrt{n}$. If none of these numbers can divide $n$, then $n$ is a prime number.

Here is an example:

#include <cmath>

bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

This code first checks whether $n$ is less than or equal to $1$. If it is, it returns false directly, because by definition, prime numbers must be greater than $1$. Then, the program loops through all integers from $2$ to $\sqrt{n}$. If $n$ can be divided by any of these integers, then $n$ is not prime, and we return false; if none of these numbers can divide $n$, then $n$ is prime, and we return true.

The improvement in time complexity with trial division is significant; its time complexity is $O(\sqrt{n})$, which means that when dealing with large numbers, trial division is more efficient than exhaustive search. Its space complexity remains $O(1)$, as we only need to store a constant number of variables during the execution of the algorithm.

Although trial division improves upon exhaustive search in terms of time complexity, its efficiency still needs improvement for extremely large numbers. To achieve better efficiency in primality testing for large numbers, scientists have proposed more efficient algorithms, such as the Miller–Rabin primality test. In the following sections, we will discuss these more efficient prime number testing algorithms in detail.

Fermat Primality Test#

In prime number testing, we can not only search for a number's factors through trial division but also utilize mathematical theory for more efficient verification. The Fermat primality test is one such method that uses Fermat's little theorem for prime number verification.

Fermat's little theorem states that if $p$ is a prime number and $a$ is any positive integer less than $p$, then the remainder of $a^{p-1}$ divided by $p$ is equal to $1$. If a number $n$ does not satisfy this property, we can conclude that $n$ is not prime; however, conversely, if a number satisfies this property, we cannot conclude that it is definitely prime; we can only say it might be prime. Therefore, the Fermat primality test does not guarantee the correctness of the result, but its error rate is acceptable in practical applications.

Here is an example:

#include <cmath>
#include <random>

/**
 * @brief Function for performing modular exponentiation
 *
 * @param int base Base
 * @param int exponent Exponent
 * @param int modulus Modulus
 * @return int Returns the result of (base ^ exponent) mod modulus
 */
int modular_pow(int base, int exponent, int modulus) {
    int result = 1;
    while (exponent > 0) {
        if (exponent & 1) result = (result * base) % modulus;
        exponent >>= 1;
        base = (base * base) % modulus;
    }
    return result;
}

/**
 * @brief Function for performing the Fermat primality test
 *
 * @param int n The number to be tested for primality
 * @param int iterations The number of iterations for primality testing, default is 5
 * @return bool Returns true if n might be prime; otherwise, returns false
 */
bool is_prime(int n, int iterations = 5) {
    if (n < 4) return n == 2 || n == 3;

    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(2, n-2);

    for (int i = 0; i < iterations; ++i) {
        int a = distribution(generator);
        if (modular_pow(a, n-1, n) != 1) {
            return false;
        }
    }
    return true;
}

In this code, the modular_pow function implements modular exponentiation, i.e., calculating $base^{exponent} \mod modulus$. The is_prime function implements the Fermat primality test. It first checks whether $n$ is less than $4$; if it is, it directly returns whether $n$ is $2$ or $3$. Then, it randomly selects an integer $a$ between $2$ and $n-2$ and calculates $a^{n-1} \mod n$. If the result is not equal to $1$, then $n$ is not prime, and we return false; if the result equals $1$ in all iterations, we return true, indicating that $n$ might be prime.

The time complexity of the Fermat primality test is $O(k \log^2 n \log \log n)$, where $k$ is the number of iterations and $n$ is the number we are testing. Its space complexity is $O(1)$. Compared to trial division, the Fermat primality test shows a significant improvement in time complexity, especially when dealing with large numbers. However, it is important to note that the Fermat primality test may return false positives, i.e., numbers that satisfy Fermat's little theorem but are not actually prime. Nevertheless, by increasing the number of iterations, we can reduce the probability of such errors to meet practical application needs.

In the following chapters, we will introduce another more efficient and accurate prime number testing method—the Miller–Rabin primality test.

Miller–Rabin Primality Test#

Although the Fermat primality test is already quite useful in prime number testing, it still has certain limitations, especially when dealing with specific "pseudoprimes," which may lead to misjudgments. To improve this issue, we introduce a more powerful primality testing algorithm—the Miller-Rabin primality test.

The Miller-Rabin test is based on Fermat's little theorem but further introduces an additional check to improve the accuracy of the verification. This method utilizes a mathematical fact: for any odd prime $p$ and any factor $q$ of $p-1$, if we select a random integer $a$, then the value of $a^{q}$ modulo $p$ will either be $1$ or $-1$, or during the successive squaring of $a^{2^iq}$, there exists some result that equals $-1$.

Here is an example:

#include <cmath>
#include <random>

/**
 * @brief Calculate modular exponentiation
 *
 * @param int base Base
 * @param int exponent Exponent
 * @param int modulus Modulus
 * @return int Returns the result of (base ^ exponent) mod modulus
 */
int modular_pow(int base, int exponent, int modulus) {
    int result = 1;
    while (exponent > 0) {
        if (exponent & 1) result = (result * base) % modulus;
        exponent >>= 1;
        base = (base * base) % modulus;
    }
    return result;
}

/**
 * @brief Function for performing the Miller-Rabin primality test
 *
 * @param int n The number to be tested for primality
 * @param int iterations The number of iterations for primality testing, default is 5
 * @return bool Returns true if n might be prime; otherwise, returns false
 */
bool miller_rabin(int n, int iterations = 5) {
    if (n < 4) return n == 2 || n == 3;

    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(2, n-2);

    int r = 0;
    int d = n - 1;
    while (d % 2 == 0) {
        d /= 2;
        ++r;
    }

    for (int i = 0; i < iterations; ++i) {
        int a = distribution(generator);
        int x = modular_pow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        for (int j = 0; j < r - 1; ++j) {
            x = modular_pow(x, 2, n);
            if (x == n - 1) break;
        }
        if (x != n - 1) return false;
    }

    return true;
}

The time complexity of the Miller-Rabin primality test is similar to that of the Fermat primality test, at $O(k \log^2 n \log \log n)$, where $k$ is the number of iterations and $n$ is the number we are testing. Its space complexity is $O(1)$.

Compared to the Fermat primality test, the Miller-Rabin primality test shows a significant improvement in accuracy, especially when dealing with large numbers. However, it remains a probabilistic algorithm, so for very large numbers or applications requiring very high accuracy, more advanced primality testing methods may be needed.

Elliptic Curve Primality Proving (ECPP)#

So far, we have explored several common and effective prime number testing algorithms, from basic trial division and exhaustive search to probabilistic methods like the Fermat primality test and the Miller-Rabin primality test. These methods can handle the vast majority of prime number testing needs. However, in certain special cases, such as very large numbers or applications requiring very high accuracy, we may need a more powerful primality testing algorithm. This is what we will introduce in this chapter—Elliptic Curve Primality Proving.

Elliptic Curve Primality Proving (ECPP) is a deterministic primality testing algorithm that can determine whether a number is prime in polynomial time. The advantage of the ECPP algorithm is that it can quickly and accurately determine whether very large numbers (e.g., over 100 digits) are prime without requiring any pre-known list of prime numbers.

The theoretical foundation of the elliptic curve primality test is profound and requires an understanding of the mathematical theory of elliptic curves. In practice, the implementation of this algorithm typically requires the use of advanced mathematical software libraries, such as the GMP library.

Due to the complexity of the elliptic curve primality test and the mathematical knowledge required, I do not intend to provide specific code implementations here. Readers interested in this topic can refer to relevant mathematical literature and code repositories.

In summary, the elliptic curve primality test provides a powerful and precise method for primality testing, especially suitable for scenarios that require handling large numbers and high accuracy.

Recommended Reading: Overview of the ECPP Algorithm#

The main idea of ECPP is to use elliptic curves and the Riemann hypothesis to find a proof factor (witness) for a number $n$. A proof factor is a number that satisfies specific conditions, and the existence of such a number can prove that $n$ is prime.

Before discussing the ECPP algorithm in detail, we need to understand some basic concepts.

• Elliptic Curve: In the ECPP algorithm, the elliptic curve we use is defined over the rational numbers, in the form $y^2 = x^3 + Ax + B$, where $A, B \in \mathbb{Q}$, and $4A^3 + 27B^2 \neq 0$ to ensure that the curve has no singular points.
• Point Addition on Elliptic Curves: The point addition defined on elliptic curves follows certain geometric rules. After defining such an addition operation, the points on the elliptic curve will form an abelian group.
• Hasse's Theorem: For an elliptic curve defined over a finite field $\mathbb{F}_q$, the number of points $N$ satisfies: $N - (q+1) \leq 2\sqrt{q}$. This theorem provides a potential way for us to find proof factors.

The steps of the ECPP algorithm are as follows:

1. Select an Elliptic Curve and Initial Point: Choose an elliptic curve $E$ defined over $\mathbb{Q}$ and an initial point $P \in E(\mathbb{Q})$. We need to ensure that the order of $P$ in the residue class ring $\mathbb{Z}/n\mathbb{Z}$ is prime, which can be achieved by selecting among multiple elliptic curves and initial points.
2. Find a Proof Factor: After finding a suitable elliptic curve and initial point, we compute the point $[m]P$, where $[m]P$ represents adding the point $P$ to itself $m$ times. We use $[m]P=O$ to find a proof factor $d$ for $n$. If we find a $d$ that satisfies $\gcd(n, d) = 1$ and $1 < d < n$, then $d$ is a proof factor for $n$.
3. Prove that $n$ is Prime: If we find a proof factor $d$, we can prove that $n$ is prime. First, we find a number $k$ such that $k^2 < d < (k+1)^2$, and then use Hasse's theorem to find a range $(k-2)\sqrt{d} < M < (k+2)\sqrt{d}$, and then prove that there exists a number $M$ in this range such that $[m]P = O$. This proves that $n$ is prime.

This is just an overview of the ECPP algorithm and does not cover many details, such as how to perform point addition in practice and how to implement various optimizations. For these details, I recommend consulting specialized literature in the field.

Conclusion#

Through our exploration, we have seen the importance of mathematics in program design. From the simplest exhaustive search and trial division to the slightly more complex Fermat primality test, and then to the more advanced Miller-Rabin primality test and Elliptic Curve Primality Proving (ECPP) method, mathematics and computer science combine to solve the problems we face.

Implementing these algorithms requires not only a deep understanding of mathematics but also proficiency in programming skills. Different prime number testing algorithms are suitable for different situations, and choosing the right algorithm can greatly improve the efficiency of programs. This is especially important when dealing with encryption and security-related issues, where effective prime number testing and generation techniques are crucial.