Hubbry Logo
search
logo
Semiprime avatar
Semiprime
Semiprime
current hub
S

Semiprime

logo
Community Hub0 Subscribers
Read side by side
Semiprime
View on Wikipedia
from Wikipedia

In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime numbers, there are also infinitely many semiprimes. Semiprimes are also called biprimes,[1] since they include two primes, or second numbers,[2] by analogy with how "prime" means "first". Alternatively non-prime semiprimes are called almost-prime numbers, specifically the "2-almost-prime" biprime and "3-almost-prime" triprime.[3]

Examples and variations

[edit]

The semiprimes less than 100 are:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, and 95 (sequence A001358 in the OEIS)

Semiprimes that are not square numbers are called discrete, distinct, or squarefree semiprimes:

6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, ... (sequence A006881 in the OEIS)

The semiprimes are the case of the -almost primes, numbers with exactly prime factors. However some sources use "semiprime" to refer to a larger set of numbers, the numbers with at most two prime factors (including unit (1), primes, and semiprimes).[4] These are:

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, ... (sequence A037143 in the OEIS)

Formula for number of semiprimes

[edit]

A semiprime counting formula was discovered by E. Noel and G. Panos in 2005.[5] Let denote the number of semiprimes less than or equal to n. Then where is the prime-counting function and denotes the kth prime.[6]

Properties

[edit]

Semiprime numbers have no composite numbers as factors other than themselves.[7] For example, the number 26 is semiprime and its only factors are 1, 2, 13, and 26, of which only 26 is composite.

For a squarefree semiprime (with ) the value of Euler's totient function (the number of positive integers less than or equal to that are relatively prime to ) takes the simple form This calculation is an important part of the application of semiprimes in the RSA cryptosystem.[8] For a square semiprime , the formula is again simple:[8]

Applications

[edit]
The Arecibo message

Semiprimes are highly useful in the area of cryptography and number theory, most notably in public key cryptography, where they are used by RSA and pseudorandom number generators such as Blum Blum Shub. These methods rely on the fact that finding two large primes and multiplying them together (resulting in a semiprime) is computationally simple, whereas finding the original factors appears to be difficult. In the RSA Factoring Challenge, RSA Security offered prizes for the factoring of specific large semiprimes and several prizes were awarded. The original RSA Factoring Challenge was issued in 1991, and was replaced in 2001 by the New RSA Factoring Challenge, which was later withdrawn in 2007.[9]

In 1974 the Arecibo message was sent with a radio signal aimed at a star cluster. It consisted of binary digits intended to be interpreted as a bitmap image. The number was chosen because it is a semiprime and therefore can be arranged into a rectangular image in only two distinct ways (23 rows and 73 columns, or 73 rows and 23 columns).[10]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Semiprime

View on Grokipedia
from Grokipedia
In number theory, a semiprime is a natural number that is the product of exactly two prime numbers, which may be equal or distinct.[1] Examples include 4 = 2 × 2, 6 = 2 × 3, 9 = 3 × 3, 10 = 2 × 5, 14 = 2 × 7, 15 = 3 × 5, 21 = 3 × 7, and 22 = 2 × 11.[1] Semiprimes form a significant subclass of composite numbers, bridging primes and more highly composite forms in the study of integer factorization and distribution.[1] The counting function π₂(x), which tallies the number of semiprimes less than or equal to x, has an asymptotic approximation of x (log log x) / log x, indicating their relative abundance compared to primes but sparsity relative to all integers.[2] This density arises from the multiplicative structure, where semiprimes include both squares of primes (such as 4, 9, 25) and square-free semiprimes (products of distinct primes, such as 6, 10, 15).[1] Beyond pure mathematics, semiprimes are foundational to computational number theory and cryptography, as factoring a large semiprime into its constituent primes is computationally intractable for sufficiently large instances, a property exploited in algorithms like RSA.[3] In the RSA cryptosystem, the public key modulus is typically a semiprime formed by multiplying two large distinct primes, ensuring security relies on the presumed hardness of this factorization problem.[4] Notable challenges, such as the factorization of RSA-129 (a 129-digit semiprime) in 1994, underscore both historical progress and ongoing research into semiprime properties.[1]

Definition and Fundamentals

Definition

A semiprime is a natural number that is the product of exactly two prime numbers, not necessarily distinct.[1] For instance, 4=2×24 = 2 \times 2 and 6=2×36 = 2 \times 3 are semiprimes.[1] Formally, a semiprime nn can be expressed as n=p×qn = p \times q, where pp and qq are prime numbers with p≤qp \leq q.[5] Semiprimes differ from prime numbers, which have only one prime factor (themselves), and from higher prime powers such as 8=238 = 2^3, which involve more than two identical prime factors.[1] The number 1 is excluded, as it is not the product of any primes.[5] The term "semiprime" derives from "semi-" combined with "prime" and is used in number theory to describe such numbers with exactly two prime factors, counting multiplicity.[6]

Types

Semiprimes can be classified based on whether their prime factors are identical or distinct, as well as by their parity and square-freeness. A square semiprime is the square of a prime number, denoted as $ n = p^2 $ where $ p $ is prime; examples include 4 ($ 2^2 ),9(), 9 ( 3^2 ),and25(), and 25 ( 5^2 $).[1] These form the sequence of prime squares, cataloged in OEIS A001248. In contrast, a non-square semiprime, also known as a distinct or discrete semiprime, is the product of two distinct primes, $ n = p \times q $ with $ p \neq q $ and both prime. Examples include 6 ($ 2 \times 3 ),10(), 10 ( 2 \times 5 ),and15(), and 15 ( 3 \times 5 $).[1] These are precisely the square-free semiprimes, meaning they have no squared prime factors, and they constitute the sequence in OEIS A006881.[7] Semiprimes can further be categorized by parity. An even semiprime is divisible by 2, which implies one of its prime factors must be 2, yielding forms like $ 2 \times p $ where $ p $ is an odd prime (or $ 2^2 = 4 $ for the square case); representative examples are 6, 10, and 14.[1][8] Conversely, an odd semiprime has both prime factors odd, resulting in products like $ p \times q $ with $ p $ and $ q $ odd primes (or $ p^2 $ for odd $ p );examplesinclude15,21(); examples include 15, 21 ( 3 \times 7 $), and 25.[1]

Examples

Small Semiprimes

The smallest semiprimes are the natural numbers greater than 1 that have exactly two prime factors, counted with multiplicity, denoted by the condition Ω(n)=2\Omega(n) = 2, where Ω(n)\Omega(n) is the total number of prime factors of nn (with repetition).[9] This includes both squares of primes (p2p^2) and products of two distinct primes (p×qp \times q). The sequence of semiprimes begins with 4, 6, 9, 10, and continues, with all terms up to 100 listed below along with their factorizations.[5][1] Among these, even semiprimes except for 4 are all of the form 2×p2 \times p, where pp is an odd prime, since any even number greater than 2 must include 2 as a factor and, to remain a semiprime, the cofactor must be prime.[1] The density of semiprimes appears to increase initially in this range, with 34 such numbers up to 100, illustrating their relative frequency among small composites.[5]
SemiprimeFactorization
4222^2
62×32 \times 3
9323^2
102×52 \times 5
142×72 \times 7
153×53 \times 5
213×73 \times 7
222×112 \times 11
25525^2
262×132 \times 13
333×113 \times 11
342×172 \times 17
355×75 \times 7
382×192 \times 19
393×133 \times 13
462×232 \times 23
49727^2
513×173 \times 17
555×115 \times 11
573×193 \times 19
582×292 \times 29
622×312 \times 31
655×135 \times 13
693×233 \times 23
742×372 \times 37
777×117 \times 11
822×412 \times 41
855×175 \times 17
862×432 \times 43
873×293 \times 29
917×137 \times 13
933×313 \times 31
942×472 \times 47
955×195 \times 19

Notable Examples

1 is excluded from the class of semiprimes, as it is not the product of two prime numbers; semiprimes require exactly two prime factors, counting multiplicity, and 1 has none.[1] The smallest odd semiprime with distinct prime factors is 15 = 3 × 5, marking an early historical example in the study of composite numbers beyond even semiprimes like 4 = 2 × 2 or 6 = 2 × 3.[1] In number theory puzzles and primality testing, semiprimes like 91 = 7 × 13 serve as notable examples of Fermat pseudoprimes; specifically, 91 is a pseudoprime to base 3, satisfying 3^{90} ≡ 1 (mod 91) despite being composite, which highlights their role in deceiving certain primality tests.[10] In contrast, the first Carmichael number, 561 = 3 × 11 × 17, is a product of three primes and passes Fermat's test for all bases coprime to it, but semiprimes like 91 illustrate similar deceptive behavior for specific bases. Semiprimes appear infrequently as Mersenne numbers Mn=2n−1M_n = 2^n - 1, but notable cases include M11=2047=23×89M_{11} = 2047 = 23 \times 89, the smallest Mersenne number that is a strong pseudoprime to base 2, and M4=15=3×5M_4 = 15 = 3 \times 5, the smallest such semiprime overall. Other indices yielding Mersenne semiprimes include 9 (511=7×73511 = 7 \times 73), 23 (8388607=47×1784818388607 = 47 \times 178481), and 37, underscoring their rarity and utility in studying composite Mersenne forms.[11] Among large-scale records, the RSA-250 semiprime, a 250-decimal-digit number (~829 bits) from the RSA Factoring Challenge, represents a milestone as the largest such semiprime fully factored to date (as of 2025), achieved in February 2020 using the general number field sieve after approximately 2700 core-years of computation; its prime factors are two 125-digit primes, demonstrating the practical limits of classical factoring algorithms.[12]

Properties

Arithmetic Properties

A semiprime n=pqn = p q, where pp and qq are primes (not necessarily distinct), exhibits specific divisibility properties determined by its prime factorization. If nn is square-free, meaning p≠qp \neq q, then the positive divisors of nn are exactly 11, pp, qq, and pqpq, yielding precisely four divisors.[13] In contrast, if nn is the square of a prime, so n=p2n = p^2, the divisors are 11, pp, and p2p^2, resulting in exactly three divisors.[13] These counts distinguish semiprimes from primes (two divisors) and numbers with more prime factors (more than four divisors for square-free cases).[14] The sum of divisors function σ(n)\sigma(n), which sums all positive divisors of nn, takes a straightforward form for semiprimes due to the multiplicativity of σ\sigma. For a square-free semiprime n=pqn = p q with distinct primes pp and qq, σ(n)=(1+p)(1+q)\sigma(n) = (1 + p)(1 + q).[15] For a prime square n=p2n = p^2, σ(n)=1+p+p2\sigma(n) = 1 + p + p^2.[15] These expressions arise directly from the geometric series sum for each prime power factor.[14] Euler's totient function ϕ(n)\phi(n), counting the integers up to nn that are coprime to nn, is also multiplicative and simplifies for semiprimes. For n=pqn = p q with p≠qp \neq q, ϕ(n)=(p−1)(q−1)\phi(n) = (p - 1)(q - 1).[16] When n=p2n = p^2, ϕ(n)=p(p−1)\phi(n) = p(p - 1).[16] These formulas reflect the exclusion of multiples of pp and qq from the count of coprimes. The greatest common divisor (GCD) and least common multiple (LCM) of a semiprime with another integer follow from their prime factorizations. For two square-free semiprimes n=pqn = p q and m=rsm = r s with all distinct primes, gcd⁡(n,m)=1\gcd(n, m) = 1 and lcm⁡(n,m)=pqrs\operatorname{lcm}(n, m) = p q r s. If they share one prime, say p=rp = r but q≠sq \neq s, then gcd⁡(n,m)=p\gcd(n, m) = p and lcm⁡(n,m)=pqs\operatorname{lcm}(n, m) = p q s. In general, gcd⁡(n,m)\gcd(n, m) is the product of the shared prime factors raised to the minimum exponent, while lcm⁡(n,m)\operatorname{lcm}(n, m) uses the maximum exponents. Semiprimes are not closed under multiplication: the product of two semiprimes is generally not a semiprime. For instance, the product of two square-free semiprimes n=pqn = p q and m=rsm = r s (all distinct primes) equals pqrsp q r s, which has four distinct prime factors and thus more than two.[1] Even if some primes coincide, the result typically has more than two prime factors counting multiplicity, unless specifically arranged to reduce to exactly two.[1]

Analytic Properties

Semiprimes are asymptotically equidistributed between the odd residue classes modulo 4, with the number ≤ x congruent to 1 mod 4 and to 3 mod 4 each ∼ (1/2) x (log log x) / log x. While temporary biases may occur due to the distribution of primes, the leading asymptotics show no disparity. More generally, semiprimes ≤ x are asymptotically equidistributed among the residue classes a mod q with gcd(a, q) = 1, each with asymptotic ∼ [1/φ(q)] x (log log x) / log x.[17] A direct link exists between Sophie Germain primes and semiprimes: if pp is a Sophie Germain prime (i.e., both pp and 2p+12p + 1 are prime), then the product p(2p+1)p(2p + 1) is a semiprime.[18] This construction yields specific semiprimes where the factors are related by the doubling relation, and such products appear in studies of prime chains and Cunningham chains of length 2.[18] Semiprimes can behave like primes under certain probabilistic tests, notably as Fermat pseudoprimes. A composite number nn is a Fermat pseudoprime to base bb if bn−1≡1(modn)b^{n-1} \equiv 1 \pmod{n}, despite nn not being prime; the smallest such semiprime is 341 = 11 × 31, which satisfies 2340≡1(mod341)2^{340} \equiv 1 \pmod{341}.[19] These instances arise when the factors of the semiprime share compatible orders in the multiplicative group, fooling the Fermat test and illustrating analytic similarities to primes in modular exponentiation.[19] The density of semiprimes in arithmetic progressions follows from extensions of the prime number theorem, with positive asymptotic density in progressions a(modq)a \pmod{q} where gcd⁡(a,q)=1\gcd(a, q) = 1. This mirrors the equidistribution of primes but scaled by the semiprime counting function π2(x)∼xlog⁡log⁡xlog⁡x\pi_2(x) \sim \frac{x \log \log x}{\log x}, first established by Landau.[17] Landau's foundational work on this asymptotic underpins related unsolved problems, such as the infinitude of primes in certain forms that influence semiprime distributions.[17]

Enumeration

Counting Formulas

The number of semiprimes less than or equal to a given positive real number xx, denoted π2(x)\pi_2(x), can be exactly determined using the prime-counting function π(y)\pi(y), which gives the number of primes less than or equal to yy. The formula is
π2(x)=∑p′p≤x(π(xp)−π(p−1)), \pi_2(x) = \sum_{\substack{p \prime \\ p \le \sqrt{x}}} \left( \pi\left( \frac{x}{p} \right) - \pi(p-1) \right),
where the sum is taken over all prime numbers p≤xp \le \sqrt{x}.[1] This expression arises from counting the products pq≤xp q \le x where pp and qq are primes with p≤qp \le q. For each fixed prime p≤xp \le \sqrt{x}, the number of suitable q≥pq \ge p is the number of primes in the interval [p,x/p][p, x/p], which is π(x/p)−π(p−1)\pi(x/p) - \pi(p-1). The formula naturally includes the prime squares p2≤xp^2 \le x, as each such square is counted when q=pq = p in the term for that pp; the total number of such squares is π(x)\pi(\sqrt{x}).[1] The enumeration of semiprimes, including this exact counting formula, was first systematically studied by Edmund Landau in his 1909 monograph Handbuch der Lehre von der Verteilung der Primzahlen. For practical computation of π2(x)\pi_2(x), especially for moderate xx, sieve methods are effective. First, generate all primes up to xx using the Sieve of Eratosthenes. Then, to count semiprimes, initialize an array of size x+1x+1 to zero and, for each prime pp, iterate over primes q≥pq \ge p such that pq≤xp q \le x, incrementing the array at position pqp q. The number of non-zero entries in the array up to xx (or specifically those marked exactly once, ensuring no overcounting from multiple representations) gives π2(x)\pi_2(x). Alternatively, a modified sieve can track the number of prime factors for each number up to xx, counting those with exactly two (counting multiplicity for squares). These methods have time complexity O(xlog⁡log⁡x)O(x \log \log x). Recurrence relations for π2(x)\pi_2(x) are less common, but the formula itself allows recursive computation if π(y)\pi(y) values are precomputed or approximated for smaller yy, leveraging known recurrences or tabulations for the prime-counting function. The following table provides computed values of π2(x)\pi_2(x) for small xx using the exact formula:
xxπ2(x)\pi_2(x)
104
10034
1000299
10410^42625
These values establish the scale of semiprime distribution for small limits; for x=106x = 10^6, π2(x)=210035\pi_2(x) = 210035.[20]

Distribution

The number of semiprimes not exceeding xx, denoted π2(x)\pi_2(x), satisfies the asymptotic formula
π2(x)∼xlog⁡log⁡xlog⁡x \pi_2(x) \sim \frac{x \log \log x}{\log x}
as x→∞x \to \infty.[2] This result was first established by Edmund Landau in 1909.[2] Semiprimes have natural density zero among the natural numbers, since π2(x)/x∼(log⁡log⁡x)/log⁡x→0\pi_2(x)/x \sim (\log \log x)/\log x \to 0 as x→∞x \to \infty.[2] However, their growth rate exceeds that of the primes for sufficiently large xx, as the prime counting function π(x)∼x/log⁡x\pi(x) \sim x / \log x is asymptotically smaller by a factor of log⁡log⁡x\log \log x.[2] The average gap between consecutive semiprimes up to xx is approximately log⁡x/log⁡log⁡x\log x / \log \log x.[2] Refinements to the asymptotic for π2(x)\pi_2(x) remain an active area of research, particularly concerning exact error terms. Current bounds on the error in π2(x)\pi_2(x) derive from those in the prime number theorem, such as ∣π(x)−li(x)∣≤d1x(log⁡x)3/4exp⁡(−d2log⁡x)|\pi(x) - \mathrm{li}(x)| \leq d_1 x (\log x)^{3/4} \exp(-d_2 \sqrt{\log x}) for explicit constants d1,d2>0d_1, d_2 > 0.[2] Under the Riemann hypothesis, sharper estimates like ∣π(x)−li(x)∣<xlog⁡x/(8π)|\pi(x) - \mathrm{li}(x)| < \sqrt{x} \log x / (8\pi) yield improved error terms for π2(x)\pi_2(x), though the precise connection to the hypothesis for semiprimes is unresolved.[2]

Applications

In Cryptography

Semiprimes play a pivotal role in public-key cryptography, most notably in the RSA cryptosystem introduced by Rivest, Shamir, and Adleman in 1978. In RSA, the public modulus $ n $ is constructed as the product of two large, distinct prime numbers $ p $ and $ q $, forming a semiprime whose factorization is computationally infeasible with current classical algorithms. The security of the system hinges on this hardness: while encryption and decryption rely on the ease of exponentiation modulo $ n $, an adversary who factors $ n $ into $ p $ and $ q $ can compute the private key and decrypt messages.[21] Key generation in RSA involves selecting $ p $ and $ q $ such that they are of comparable bit length to ensure balanced difficulty in factoring, typically producing an $ n $ of around 2048 bits to meet security standards as of 2025. According to NIST guidelines, a 2048-bit modulus provides at least 112 bits of security, sufficient for many applications through the mid-2020s, though migration to 3072 bits or larger is recommended by 2030 for sustained protection against advances in factoring. Trial division attacks, which test divisibility by small primes up to $ \sqrt{n} $, become utterly impractical for such sizes, requiring on the order of $ 2^{1024} $ operations for a 2048-bit $ n $. Instead, probabilistic methods like Pollard's rho algorithm, developed in 1975, are employed for potential factorization; it uses a pseudorandom sequence to detect cycles and find factors with expected time complexity $ O(\sqrt[4]{n}) $, but remains infeasible for well-chosen large semiprimes due to the immense runtime on classical hardware.[22] The historical factorization of RSA-129 in 1994 underscored both the resilience and evolving challenges of semiprime-based security. This 129-decimal-digit (approximately 426-bit) semiprime, part of an early RSA challenge, was factored after eight months of distributed computation using the quadratic sieve algorithm across over 1,600 workstations worldwide, revealing a 79-digit factor and a 77-digit factor. This event highlighted the practical hardness of semiprimes at the time but also spurred improvements in factoring techniques, prompting larger key sizes in subsequent RSA deployments. Looking ahead, quantum computing poses an existential threat to semiprime-based systems like RSA through Shor's algorithm, proposed in 1994. This quantum routine efficiently factors semiprimes in polynomial time by finding the period of a function related to $ n $, potentially breaking 2048-bit RSA on a sufficiently large, fault-tolerant quantum computer with thousands of logical qubits. While no such device exists as of 2025, the algorithm has driven the development of post-quantum cryptography standards to safeguard against this vulnerability.[23]

In Factoring and Computation

Factoring semiprimes is a central problem in computational number theory, where the goal is to decompose a semiprime $ n = p \times q $ into its prime factors $ p $ and $ q $. This task is known to be in both NP and co-NP, but it is neither known to be solvable in polynomial time (in P) nor NP-complete, leading to the widespread belief that it is NP-intermediate.[24][25] For large semiprimes with balanced prime factors, efficient factorization relies on advanced general-purpose algorithms. The quadratic sieve, introduced by Carl Pomerance in 1984, is effective for semiprimes up to about 100 digits by finding smooth quadratic residues modulo $ n $ to construct relations for linear algebra over the factor base.[26] For even larger semiprimes exceeding 100 digits, the general number field sieve (GNFS) is the state-of-the-art method, leveraging algebraic number fields to sieve for smooth values in both rational and algebraic integers, achieving subexponential time complexity of approximately $ \exp(c (\log n)^{1/3} (\log \log n)^{2/3}) $ for constant $ c \approx 1.923 $.[27][28] Certain structural properties of semiprimes allow for faster factorization using specialized techniques. If one prime factor is small relative to $ n $, trial division—systematically testing divisibility by primes up to $ \sqrt{n} $—can efficiently identify it, though optimizations like the wheel factorization reduce the number of trials.[29] When the two prime factors are close in value (i.e., $ |p - q| $ is small), Fermat's factorization method exploits the identity $ n = ((p+q)/2)^2 - ((p-q)/2)^2 $ by searching for nearby squares whose difference yields $ n $.[30] The RSA Factoring Challenge, launched by RSA Laboratories in 1991, provided monetary incentives for factoring specific large semiprimes known as RSA numbers, ranging from 100 to 1024 bits, to benchmark progress in integer factorization. The challenge was discontinued in 2007 due to advances in cryptanalysis and the reduced publicity value of publicized breaks.[31] Despite its end, informal efforts persist, with researchers continuing to factor remaining RSA numbers to push computational boundaries.[32] As of 2025, the largest semiprime factored using general-purpose classical algorithms is RSA-250, a 829-bit (250-digit) number, achieved in February 2020 by an international team using the GNFS on a cluster requiring approximately 2,700 core-years of computation.[12] Practical implementations of these algorithms are available in open-source software suites. Msieve provides an optimized implementation of the quadratic sieve and early NFS variants, suitable for semiprimes up to around 80 digits on modest hardware.[33] CADO-NFS, developed by a collaboration including INRIA, offers a complete, parallelized GNFS framework for factoring semiprimes beyond 100 digits, incorporating advanced sieving and linear algebra phases.[34]

References

  1. Semiprime -- from Wolfram MathWorld
  2. [PDF] On the counting function of semiprimes - People
  3. New Semi-Prime Factorization and Application in Large RSA Key ...
  4. [PDF] About Efficient Algorithm for Factoring Semiprime Number
  5. A001358 - OEIS
  6. semiprime - Wiktionary, the free dictionary
  7. https://oeis.org/A006881
  8. Levy's conjecture - PlanetMath.org
  9. Prime Factor -- from Wolfram MathWorld
  10. How to show that 91 is a pseudoprime to the base 3?
  11. Mersenne Number -- from Wolfram MathWorld
  12. Comparing the difficulty of factorization and discrete logarithm: a 240 ...
  13. Semiprimes - OeisWiki
  14. Divisor Function -- from Wolfram MathWorld
  15. formula for sum of divisors - PlanetMath
  16. Euler's totient function - Algorithms for Competitive Programming
  17. Sophie Germain Prime -- from Wolfram MathWorld
  18. [PDF] Fermat Pseudoprimes and Carmichael Numbers 1. Introduction
  19. [PDF] Landau's problems on primes - Numdam
  20. Count the semiprime numbers in the given range [a..b]
  21. Semiprimes up to 1000 - Prime Numbers
  22. Can you derive a formula for the semiprime counting function from ...
  23. [PDF] A Method for Obtaining Digital Signatures and Public-Key ...
  24. https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r5.pdf
  25. [PDF] Algorithms for Quantum Computation: - Discrete Log and Factoring
  26. Reducing the integer factorization problem to an NP-Complete ...
  27. Problems known to be in both NP and coNP, but not known to be in P
  28. [PDF] The Quadratic Sieve Factoring Algorithm - Computer Science
  29. [PDF] A Beginner's Guide To The General Number Field Sieve - UMD CS
  30. [PDF] An Introduction to the General Number Field Sieve - Virginia Tech
  31. [PDF] Cracking RSA with Various Factoring Algorithms - UMD CS
  32. A modified Fermat factoring algorithm to allow initial guess of $P
  33. Projects - distributed.net
  34. Progress in general purpose factoring - AI Impacts
  35. Integer Factoring Records
  36. upiter/msieve: MSIEVE: A Library for Factoring Large Integers - GitHub
  37. CADO-NFS
User Avatar
No comments yet.