Semiprimes¶
A semiprime is an integer that is the product of two primes (not necessarily distinct), i.e.
Semiprimes sit at the center of practical factorization hardness and are the basic objects behind RSA-style moduli. [Rivest et al., 1978, The OEIS Foundation Inc., 2025]
Key facts¶
Sequence: The semiprimes form OEIS sequence A001358. [The OEIS Foundation Inc., 2025]
RSA context: RSA uses \(N=pq\) and the difficulty of factoring \(N\) (when \(p,q\) are large and random-looking). [Rivest et al., 1978]
Special cases: \(p=q\) yields squares of primes; \(p\ne q\) yields “RSA-like” semiprimes.
What to experiment with¶
Distribution: Count semiprimes up to \(X\) and compare empirical growth with simple heuristic approximations.
Factorization methods: Benchmark trial division, Pollard’s rho, and (for larger sizes) ECM bindings if you later allow optional deps.
RSA-style generation: Generate balanced semiprimes (\(p,q\) same bitlength) and compare factorization difficulty vs unbalanced ones.
Smoothness: Explore how often \(p-1\) or \(q-1\) is smooth (motivates \(p-1\) factoring methods).