9.3 Prime Numbers, Factorization, and the Mathematical Boundaries of RSA

Prime numbers are fundamental building blocks of integer factorization and appear in discussions of public-key cryptography and hash tables. However, simply using primes does not automatically yield security or uniform distribution; the actual security and behavior of the algorithm depend entirely on the full construction.

Prime Numbers and the Fundamental Theorem of Arithmetic

An integer greater than 1 that has no positive divisors other than 1 and itself is called a prime number. An integer greater than 1 that is not prime is called a composite number.

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a product of prime numbers, and this factorization is unique up to the order of the factors.

360 = 2³ · 3² · 5

Prime factorization enables a clear understanding of gcd, lcm, and simplification operations in terms of prime exponents. However, factoring large integers into their prime components can be computationally challenging in practice.

Trial Division and Sieve Methods

Reject n<2 first. For the remaining integers, if n has a nontrivial factor, at least one is no greater than √n. Thus, we can test divisors up to the square root.

To avoid floating-point square root boundaries, use:

d <= n // d   // positive integer division, d >= 2

And first handle 2, then only test odd numbers.

To find all primes in a given range, the Eratosthenes sieve marks multiples starting from small primes, with typical time complexity O(N log log N) and space complexity O(N). Segment sieving reduces memory usage for large intervals.

Python 3.8+ provides isqrt for an exact integer square root. When processing prime p, smaller prime factors have already marked its composite multiples below p²:

from math import isqrt

def primes_up_to(n):
    if n < 2:
        return []
    prime = bytearray(b"\x01") * (n + 1)
    prime[0] = prime[1] = 0
    for p in range(2, isqrt(n) + 1):
        if prime[p]:
            for multiple in range(p * p, n + 1, p):
                prime[multiple] = 0
    return [p for p in range(2, n + 1) if prime[p]]

print(primes_up_to(20))       # [2, 3, 5, 7, 11, 13, 17, 19]
print(len(primes_up_to(100))) # 25

This implementation allocates flags for 0 through n plus the output list. A segmented sieve can reduce the flag range, but retaining every output prime still consumes space.

Trial division works well for small numbers but is not suitable for cryptographic-scale values.

Primality Testing Does Not Equal Factorization

Primality testing answers the question "Is n a prime number?" whereas factorization requires producing the actual factors of a composite number. The former has deterministic polynomial-time algorithms, and in practice, efficient probabilistic tests are widely used. In contrast, no known classical polynomial-time algorithm exists for the general factorization of large integers.

The Miller–Rabin test expresses an odd integer n≥3 as:

n - 1 = 2^s * d, where d is odd

For a base 1≤a<n, first compute x=a^d mod n. This round passes if x is 1 or n-1; otherwise square at most s-1 times and pass only if n-1 appears. Failure gives a compositeness witness. For a fixed odd composite and independently uniform bases from this range, the probability of passing k rounds is at most 4^-k. This conditions on the input being composite; it is not the posterior probability of compositeness after passing. See MIT’s primality-testing lecture.

For example, 2047=23×89 and 2046=2×1023. Base 2 gives 2^1023 mod 2047=1 and passes. Base 3 gives 1565, neither 1 nor 2046, with no further squaring rounds; it proves compositeness. Passing one base is an early result, not a prime certificate.

For fixed machine integer ranges, a known set of deterministic bases can be used to achieve a definitive judgment. The specific combination of bases depends on the numerical upper bound and cannot be simply extended from 64-bit rules to arbitrary large integers.

Cryptographic key generation should use established standards and mature libraries (including candidate generation, random source selection, additional validation, and parameter length specifications) rather than manually combining Miller–Rabin tests.

RSA's Mathematical Backbone

Teaching model:

1. Select distinct odd primes p,q; real keys must meet the standard’s size requirements;
2. Compute n=pq;
3. Calculate λ(n)=lcm(p-1,q-1);
4. Choose 3≤e<n such that gcd(e,λ(n))=1;
5. Compute d≡e⁻¹ (mod λ(n)).

The public key contains (n,e), while the private key includes d and commonly used CRT parameters. Basic operations:

c ≡ m^e (mod n)
m ≡ c^d (mod n)

The message representative satisfies 0≤m<n, and the private exponent is positive. Modulo p, if p|m, both sides are zero; otherwise Fermat’s theorem and ed≡1 (mod p-1) give m^(ed)≡m (mod p). Repeat modulo q and combine by CRT. This covers messages not coprime to n, which a direct appeal to Euler’s theorem alone would miss.

This Python 3.8+ example checks raw RSA arithmetic for every message under a tiny modulus. Its factors are in the source and are also trivial to find by trial division; it offers no confidentiality:

from math import gcd

p, q = 61, 53  # Tiny public teaching values, unsuitable for security.
n = p * q
lam = (p - 1) // gcd(p - 1, q - 1) * (q - 1)
e = 17
d = pow(e, -1, lam)
m = 65
c = pow(m, e, n)
print(n, lam, d, c, pow(c, d, n))  # 3233 780 413 2790 65
assert all(pow(pow(m, e, n), d, n) == m for m in range(n))

Textbook RSA Cannot Be Used Directly

Raw m^e mod n is deterministic and does not provide semantic security required by modern encryption, making it vulnerable to structural and chosen-ciphertext attacks. Standard cryptographic schemes define encoding for basic RSA operations as follows:

• Encryption uses schemes like RSAES-OAEP;
• Signing uses schemes like RSASSA-PSS;
• In practice, large data volumes typically employ hybrid encryption, where RSA is used only to encrypt a randomly generated symmetric key.

Encryption and signing are not simply the same interface flipped, private-key encryption and public-key decryption. They have distinct security objectives and encoding mechanisms.

The security of RSA should not be stated as being "equivalent to the difficulty of integer factorization." Efficient factorization of n would reveal the private key, but the precise equivalence between RSA inversion and integer factorization has not been universally established as a general principle. Security assessments depend on the RSA problem, the specific encoding scheme, key length, implementation details, and the attack model.

Quantum Shor's algorithm poses a threat to RSA on sufficiently large, fault-tolerant quantum computers; migration strategies are discussed in the cryptography lessons in Volume 8.

Hash Table Capacity and Probe Cycles

Slot mapping typically follows one of two patterns:

index = floorMod(hash, m)
index = mixedHash & (m - 1), when m is a power of two

Fixed-stride probing (h+i·step) mod m visits m/gcd(step,m) slots, covering the table exactly when the stride and capacity are coprime. With prime capacity, every 1≤step<m qualifies. Linear probing has stride 1 and covers any table capacity; it does not require a prime. Probe coverage also says nothing by itself about uniform key distribution.

This Python 3 count shows how strides 2 and 3 differ at capacity 8:

from math import gcd

for m, step in [(8, 2), (8, 3), (7, 2)]:
    visited = {(i * step) % m for i in range(m)}
    assert len(visited) == m // gcd(m, step)
    print(m, step, len(visited))
# 8 2 4
# 8 3 8
# 7 2 7

A capacity that is a power of two enables fast indexing via masking and easy doubling when resizing. It performs well if the high and low bits are properly mixed; however, if only the low bits are used and the keys have strong low-order patterns, clustering can occur.

Therefore, it's incorrect to broadly claim that "primes always result in fewer collisions." Instead, one should:

• Follow the capacity strategy appropriate to the specific implementation;
• Use well-designed hash mixing;
• Implement anti-hash flooding defenses for keys under attacker control;
• Conduct stress testing with realistic load factors and actual key distributions.

The goals of cryptographic hashing and hash table lookup are fundamentally different, and their evaluation criteria should not be conflated.

The Minimum Boundary of Cryptographic Implementation

• Do not implement RSA padding, prime generation, or constant-time operations from scratch;
• Use well-maintained standard libraries with explicit algorithm identifiers;
• Select key lengths and signature/encryption schemes according to current best practices;
• Clearly distinguish between encryption, signing, and key exchange operations;
• Design key rotation, revocation, and algorithm migration strategies;
• Validate implementation through test vectors and interoperability testing.

A mathematical explanation of why an algorithm works cannot alone prove the security of its implementation.

Completion Checklist

1. Use the sieve method to list all prime numbers below 100;
2. Explain what "witnesses" and "probable primes" mean in the context of the Miller–Rabin test;
3. Manually compute a small RSA example using small primes, and clearly demonstrate why it is insecure;
4. Explain why OAEP/PSS is not merely optional padding, why it is essential;
5. Construct keys with shared low bits and compare direct masking with indexing after bit mixing;
6. Clarify the difference between "if you can factor, you can break RSA" and "RSA inversion has been proven equivalent to factoring."

References

• RFC 8017: PKCS #1 v2.2
• NIST FIPS 186-5: Digital Signature Standard
• GNU MP: Prime Testing Algorithm