Offensive Security Researcher & Quantum Cryptography Analyst

Prime Number Generation Algorithm: Working, Explanation, and Number Theory

Abdul Wahab Junaid
prime number generation algorithm and working of this algorithm.

prime number generation algorithm and working of this algorithm.

I think prime numbers are the quiet workhorses behind almost every public-key cryptosystem I’ve ever studied. Whenever I generate an RSA key pair, or set up Diffie-Hellman parameters, the very first thing that has to happen behind the scenes is finding a large prime number — often 1024, 2048, or even 4096 bits long. What I find genuinely interesting is that we don’t actually prove these huge numbers are prime in the strict mathematical sense most of the time; instead, we use probabilistic primality tests that make the chance of error so astronomically small that it’s considered secure enough for real-world cryptography. In this file, I want to walk through how large primes are generated and tested in practice.

History and Background

I trace the mathematical study of primality testing back centuries, to the Sieve of Eratosthenes from ancient Greece, which is still the simplest method for finding all small primes up to some bound. But the modern cryptographic need — testing whether an enormous, randomly chosen number (hundreds of digits long) is prime, quickly — is a much more recent story. Fermat’s Little Theorem, from the 17th century, provided an early necessary (but not sufficient) condition for primality, which became the basis of the Fermat primality test. In 1976, Gary Miller proposed a primality test based on the (then-unproven) extended Riemann hypothesis; Michael Rabin turned it into a practical probabilistic algorithm in 1980, giving us the Miller-Rabin test, which remains the most widely used primality test in cryptographic libraries today. Meanwhile, in 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena published the AKS primality test, which was the first algorithm proven to determine primality in deterministic polynomial time for any input — a landmark theoretical result, even though it’s slower in practice than probabilistic tests for cryptographic-sized numbers.

Problem Statement

The problem I need to solve is twofold: first, given a candidate integer, determine (with very high confidence, or with certainty for smaller numbers) whether it is prime; second, generate a large random integer that is prime, suitable for use as a cryptographic parameter (like an RSA modulus factor). Because truly deterministic primality proofs for enormous numbers were historically slow, cryptography almost universally relies on probabilistic tests that can be made arbitrarily confident by repeating them, trading a vanishingly small (and controllable) error probability for dramatically better performance.

Core Concepts

How It Works

I typically generate a large prime for cryptographic use with a pipeline like this:

  1. I generate a random odd integer of the desired bit length (odd because even numbers greater than 2 can never be prime).
  2. I run quick trial division by small primes (2, 3, 5, 7, 11, … up to some small bound like a few hundred or a thousand) to immediately reject candidates with small factors — this is cheap and filters out the vast majority of composite candidates before I invest in expensive probabilistic testing.
  3. For any candidate surviving the sieve step, I run the Miller-Rabin test with several randomly chosen witness bases.
  4. If the candidate passes all the Miller-Rabin rounds, I accept it as prime (with an error probability I control by choosing the number of rounds — commonly 20+ rounds are used in cryptographic libraries, driving the false-positive probability down to less than $4^{-20}$, astronomically small).
  5. If the candidate fails at any stage, I discard it and generate a new random candidate, repeating the whole process.
  6. For applications requiring extremely high assurance, I may follow up with a deterministic primality proof (like a Lucas-based certificate or, more rarely, AKS) on the final candidate, though in most cryptographic practice, sufficiently many Miller-Rabin rounds are considered adequate.

Working Principle

The Miller-Rabin test, which I rely on most, works by refining Fermat’s Little Theorem to also check the behavior of square roots of unity. If $n$ is prime, then the only square roots of 1 modulo $n$ are $1$ and $-1$ (this follows because $\mathbb{Z}_n$ is a field when $n$ is prime, and $x^2 \equiv 1 \pmod n$ factors as $(x-1)(x+1) \equiv 0$, meaning $x \equiv \pm 1$). Miller-Rabin writes $n – 1 = 2^s \cdot d$ (factoring out all powers of 2), then computes $a^d \bmod n$ and repeatedly squares it, checking at each step whether the sequence unexpectedly produces a square root of 1 other than $\pm 1$ — if it does, $n$ is definitely composite (this is called a “nontrivial square root,” and its existence is impossible modulo a prime). If no such violation occurs across all the squarings for a given witness $a$, the number passes that round; repeating with multiple independent random witnesses drives down the probability that a composite number could pass every round purely by chance.

Mathematical Foundation

Fermat’s Little Theorem: for prime $p$ and integer $a$ with $\gcd(a,p)=1$:

$$a^{p-1} \equiv 1 \pmod{p}$$

Miller-Rabin setup: write $n – 1 = 2^s d$ with $d$ odd. A number $n$ is declared “probably prime” with respect to witness $a$ if either:

$$a^d \equiv 1 \pmod{n}$$

or there exists some $r$ with $0 \le r

$$a^{2^r d} \equiv -1 \pmod{n}$$

If neither condition holds for any $r$, then $n$ is definitely composite (this is a mathematically rigorous conclusion, not probabilistic — a composite fails to satisfy Fermat/Miller-Rabin identically to how a prime does, and this test’s structure guarantees the violation is detected).

Error bound: for a random odd composite $n$, the probability that a single randomly chosen witness $a$ fails to detect compositeness is at most $\frac{1}{4}$. Repeating with $k$ independent witnesses reduces the false-positive probability to at most:

$$4^{-k}$$

So for $k = 20$ rounds, the probability of incorrectly declaring a composite number prime is at most $4^{-20} \approx 9.1 \times 10^{-13}$, a risk considered negligible for essentially all cryptographic purposes.

Density of primes (Prime Number Theorem): the number of primes less than $x$ is approximately:

$$\pi(x) \sim \frac{x}{\ln x}$$

which tells me that the “density” of primes near a large number $N$ is roughly $\frac{1}{\ln N}$, so I expect, on average, to test about $\ln N$ random odd candidates near $N$ before finding one that’s prime — this is what makes random-candidate-generation-and-testing a practical strategy rather than a hopeless search.

Diagrams

flowchart TD
    A[Generate random odd candidate n of target bit length] --> B[Trial division by small primes]
    B --> C{Divisible by any small prime?}
    C -- Yes --> A
    C -- No --> D[Run Miller-Rabin with k random witnesses]
    D --> E{Passes all k rounds?}
    E -- No, composite detected --> A
    E -- Yes --> F[Accept n as prime with error less than 4^-k]

Pseudocode

function generate_large_prime(bit_length, rounds):
    while true:
        candidate = random_odd_integer(bit_length)
        if passes_small_prime_filter(candidate):
            if miller_rabin(candidate, rounds):
                return candidate

function passes_small_prime_filter(n):
    for p in small_primes_list:      // e.g., 2, 3, 5, 7, ..., 997
        if n mod p == 0 and n != p:
            return false
    return true

function miller_rabin(n, rounds):
    if n

Step-by-Step Example

I’ll test the small number n = 221 (which is 13 * 17, so it’s composite — a good test case since it’s known to fool the basic Fermat test with some bases) using Miller-Rabin.

  1. n - 1 = 220 = 2^2 * 55, so s = 2, d = 55.
  2. I pick a witness, say a = 174.
  3. I compute x = 174^55 mod 221. Working this out (using fast modular exponentiation), I get x = 47.
  4. Is x == 1 or x == 220? No, 47 is neither.
  5. I enter the squaring loop, for r = 1 (since s-1 = 1): x = 47^2 mod 221 = 2209 mod 221 = 2209 - 9*221 = 2209-1989=220.
  6. x == 220 == n-1, so this round passes (174 does not reveal 221 as composite).
  7. I try a second witness, say a = 137.
  8. I compute x = 137^55 mod 221 = 188 (via modular exponentiation).
  9. x is neither 1 nor 220.
  10. Squaring loop, r=1: x = 188^2 mod 221 = 35344 mod 221. 221*159 = 35139, so 35344-35139=205.
  11. x = 205, not 220, and I’ve exhausted my squaring rounds (s-1=1 iteration only) — so this witness reveals 221 as composite.
  12. Since witness 137 detected compositeness, Miller-Rabin correctly concludes n = 221 is not prime — matching the known factorization 13*17.

This example is a classic one I like because it also shows why a single witness (like 174) isn’t always enough — this is exactly why multiple independent rounds with different random witnesses are used in practice.

Time Complexity

Space Complexity

Both trial division and Miller-Rabin require only $O(\log n)$ space to store the candidate and intermediate values during modular exponentiation (since big-integer arithmetic representations scale with the bit-length of $n$), plus a small fixed table of small primes for the pre-filtering step. This makes primality testing very memory-efficient even for very large cryptographic key sizes.

Correctness Analysis

Miller-Rabin’s correctness rests on the mathematical fact I described earlier: if $n$ is truly prime, every witness $a$ (coprime to $n$) will satisfy the test conditions, since $\mathbb{Z}_n^*$ being a field guarantees no nontrivial square roots of unity exist — so a prime number will never be incorrectly rejected (there are no false negatives). The one-sided error is in the other direction: it’s mathematically proven that for any composite $n$, at most 1/4 of the possible witnesses in $[2, n-2]$ will fail to reveal compositeness — this bound was proven rigorously by Rabin, building on Miller’s earlier deterministic version (which itself relied on the unproven extended Riemann hypothesis for a slightly different, deterministic guarantee). Because this per-round error is bounded and independent across randomly chosen witnesses, repeated rounds multiply the error bound down, giving me a provably tiny (though not literally zero) probability of error for any fixed number of rounds.

Advantages

Disadvantages

Applications

Prime generation underlies RSA key generation directly (an RSA modulus is the product of two large random primes), Diffie-Hellman and DSA parameter generation (finding a large prime modulus and a generator of appropriate order), and various other number-theoretic cryptographic constructions. Beyond cryptography, primality testing is also used in computational number theory research, in generating primes for hash table sizing and pseudo-random number generator design, and in recreational and competitive mathematics for search projects like finding new large Mersenne primes.

Implementation in C

#include stdio.h>
#include stdlib.h>
#include stdint.h>
#include time.h>

/* modular exponentiation: base^exp mod mod, using unsigned 64-bit
   with care to avoid overflow on multiplication (educational scale) */
uint64_t mulmod(uint64_t a, uint64_t b, uint64_t mod) {
    return (uint64_t)(( (__uint128_t)a * b ) % mod);
}

uint64_t pow_mod(uint64_t base, uint64_t exp, uint64_t mod) {
    uint64_t result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = mulmod(result, base, mod);
        base = mulmod(base, base, mod);
        exp >>= 1;
    }
    return result;
}

/* single Miller-Rabin round with a given witness */
int miller_rabin_round(uint64_t n, uint64_t a, uint64_t d, int s) {
    uint64_t x = pow_mod(a, d, n);
    if (x == 1 || x == n - 1) return 1; /* passes this round */

    for (int r = 1; r  s; r++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return 1;
    }
    return 0; /* composite, revealed by this witness */
}

int is_probable_prime(uint64_t n, int rounds) {
    if (n  2) return 0;
    if (n == 2 || n == 3) return 1;
    if (n % 2 == 0) return 0;

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

    for (int i = 0; i  rounds; i++) {
        uint64_t a = 2 + rand() % (n - 3); /* random witness in [2, n-2] */
        if (!miller_rabin_round(n, a, d, s)) {
            return 0; /* definitely composite */
        }
    }
    return 1; /* probably prime */
}

int main(void) {
    srand((unsigned)time(NULL));

    uint64_t test221 = 221;
    uint64_t test_prime = 104729; /* known prime (10000th prime) */

    printf("Is 221 probably prime? %s\n", is_probable_prime(test221, 20) ? "YES" : "NO");
    printf("Is 104729 probably prime? %s\n", is_probable_prime(test_prime, 20) ? "YES" : "NO");

    /* generate a random probable prime under 1,000,000 for demonstration */
    uint64_t candidate;
    do {
        candidate = (uint64_t)(rand() % 999999) | 1; /* force odd */
    } while (!is_probable_prime(candidate, 20));

    printf("Randomly generated probable prime: %llu\n", (unsigned long long)candidate);

    return 0;
}

I kept this implementation to 64-bit integers for clarity and portability; real cryptographic implementations use arbitrary-precision “big integer” libraries (like GMP or OpenSSL’s BIGNUM) to handle the 1024-4096 bit numbers actually used in RSA and Diffie-Hellman key generation.

Sample Input and Output

Input: testing n = 221 (composite, 13*17) and n = 104729 (a known prime) with 20 Miller-Rabin rounds, then generating a random probable prime under 1,000,000.

Output:

Is 221 probably prime? NO
Is 104729 probably prime? YES
Randomly generated probable prime: 613597

(The final randomly generated prime will vary between runs since it depends on the random seed, but it will always be a genuinely prime number, consistent with the Miller-Rabin guarantees described above.)

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version