Primes!

Prime numbers are essential building blocks in number theory and have important applications in mathematics, cryptography, and computer science. Let’s dive deeper into what prime numbers are, their properties, methods to find them, and some interesting facts.

What Are Prime Numbers?

A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. In simpler terms, a prime number has exactly two distinct positive divisors: 1 and itself.

Properties of Prime Numbers

• Only 2 is an even prime: 2 is the only even prime number. Every other even number can be divided by 2, so they are not prime.
• There are infinite primes: There are infinitely many primes. This was proven by the Greek mathematician Euclid over 2000 years ago. Euclid's proof goes as follows: assume there are finitely many primes. Then, multiply all the primes together and add 1, i.e., \( X = \prod_{i=1}^{n} p_i + 1 \). This new number \( X \) must have prime factors not included in the original list, proving that new primes exist.
• Prime Gaps: The difference between consecutive primes can vary greatly. As numbers get larger, prime gaps (the difference between two consecutive primes) tend to increase.
• Fundamental Theorem of Arithmetic: Every natural number greater than 1 can be written uniquely as a product of prime numbers. This is known as the prime factorization of a number.
• Distribution of Primes: Prime numbers become less frequent as numbers increase, but there is no simple formula to predict where the next prime will be.

How to Find Prime Numbers

There are several ways to find prime numbers, depending on the size of the number and the purpose of the search. Here are some common methods:

1. Trial Division

One of the simplest methods is to divide a number by all primes smaller than its square root. If none divide it evenly, the number is prime.

To check if 29 is prime:

• Divide 29 by 2, 3, 5 (the primes less than \( \sqrt{29} \approx 5.39 \)).
• If 29 isn’t divisible by any of these primes, it is prime.

2. The Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm to find all primes up to a specified limit. It works by iteratively marking the multiples of each prime number starting from 2. The numbers that remain unmarked are primes.

3. Fermat Primality Test

The Fermat primality test is a probabilistic test used to determine if a number is likely to be prime. If a number passes this test for several values, it is probably prime. However, there are exceptions called Carmichael numbers that can trick the test.

It says that a number is a prime if \(a^n \equiv a \pmod n\)

4. The Miller-Rabin Test

The Miller-Rabin test is an advanced algorithm that improves on Fermat's test. It is often used in practice to check for primality, especially when working with large numbers in cryptography. It is also probabilistic, but less likely to produce false positives.

Steps of the Miller-Rabin Test

1. Write \( n-1 \) as \( 2^s \cdot d \) where \( d \) is odd.
2. Pick a random base \( a \) such that \( 2 \leq a \leq n-2 \).
3. Check the base condition by computing \( x = a^d \mod n \). If \( x = 1 \) or \( x = n-1 \), the number passes this round.
4. For \( r = 1 \) to \( s-1 \), square \( x \) and compute \( x = x^2 \mod n \). If \( x = n-1 \), the number passes this round.
5. If no condition is met, \( n \) is composite.

Example

Let’s say we want to test whether \( n = 561 \) is prime.

• Write \( 561-1 = 560 = 2^4 \cdot 35 \). So, \( s = 4 \) and \( d = 35 \).
• Pick \( a = 2 \) as a base. Calculate \( 2^{35} \mod 561 = 263 \).
• Square it: \( 263^2 \mod 561 = 166 \), \( 166^2 \mod 561 = 67 \), \( 67^2 \mod 561 = 1 \).
• The appearance of \( 1 \) without a \( -1 \) not at the end indicates that 561 is composite.

Python code for the Miller-Rabin Test In SymPy ntheory primetest.py

        def mrtest(n, base, s, t):
        """Miller-Rabin strong pseudoprime test for one base.
        Return False if n is definitely composite, True if n is
        probably prime, with a probability greater than 3/4.
    
        """
        # do the Fermat test
        b = pow(base, t, n)
        if b == 1 or b == n - 1:
            return True
        else:
            for j in range(1, s):
                b = pow(b, 2, n)
                if b == n - 1:
                    return True
                # see I. Niven et al. "An Introduction to Theory of Numbers", page 78
                if b == 1:
                    return False
        return False
    

In this Python implementation, \( n \) is the number to test, and \( base \) is the base. The algorithm returns True if \( n \) is "probably prime" and False if it is composite.

5. p+1 or p-1 tests

The test is very fast when the tested number plus or minus 1 is very easy to factor.

6. AKS Primality Test

The AKS primality test is a relatively recent discovery that can determine with certainty whether a number is prime in polynomial time. Although the algorithm is theoretically important, it is not practical for very large numbers due to its complexity.

Applications of Prime Numbers

Prime numbers have numerous practical applications, particularly in fields related to computer science and cryptography:

• Cryptography: Prime numbers are used in public-key cryptography, like RSA encryption, which is crucial for securing data on the internet.
• Random Number Generation: Prime numbers are used in algorithms that generate random numbers for simulations, cryptography, and games.
• Prime Factorization: The difficulty of factoring large numbers into primes forms the basis of the security of many encryption methods.

Interesting Mathematical Curiosities

• Twin Primes: Twin primes are pairs of primes that differ by 2, such as (3, 5) or (11, 13). It is unknown whether there are infinitely many twin primes.
• Goldbach Conjecture: This famous conjecture states that every even number greater than 2 is the sum of two primes. It has been tested for very large numbers but remains unproven.
• Mersenne Primes: A Mersenne prime is a prime of the form \(2^p - 1\), where \(p\) is also a prime. The largest known primes are often Mersenne primes, found using distributed computing projects like GIMPS.
• Perfect Numbers: A perfect number is a number that is the sum of its proper divisors. All even perfect numbers are related to Mersenne primes.

My prime-search project here.