Linked from

The 26 pages that link to Integer factorization, each with the reason it gives.

• IntegerRelated: Factoring reveals the multiplicative structure of integers and supports cryptographic methods.

• Number theoryRelated: Its computational difficulty for large inputs supports RSA while its algorithms draw on number theory.

• Prime factorizationNarrower topic: Prime factorization is the canonical endpoint of integer factorization.

• P versus NP problemRelated: Factoring is in NP and co-NP, but its status as NP-complete is unknown.

• Quadratic reciprocityRelated: Residue tests related to reciprocity help guide some factorization methods.

• Polynomial factorizationCompared with: Polynomial factors are expressions, not merely numerical divisors of coefficients.

• Primality testCompared with: Testing whether a number is prime is generally much easier than finding its factors when it is composite.

• Composite numberRelated: Factoring is the central computational task associated with composite integers.

• RSA cryptosystemRelated: Factoring RSA’s public modulus can reveal the primes needed to recover its private key.

• Quadratic residueRelated: Some factorization methods exploit modular square roots to reveal factors.

• Trial divisionNarrower topic: Trial division is a direct, general-purpose approach to this broader problem.

• Pythagorean tripleRelated: Factoring c² − a² into (c − a)(c + a) helps derive triple-generating formulas.

• Polynomial timeRelated: No classical polynomial-time algorithm is known, making its status relevant to cryptographic security.

• Shor's algorithmRelated: This is the best-known task Shor's algorithm solves in polynomial time.

• Discrete logarithmCompared with: It is a separate hardness assumption used by RSA rather than the usual discrete-logarithm systems.

• Unique factorizationRelated: Algorithms seek the prime factors guaranteed to exist and be unique.

• Édouard LucasRelated: Primality criteria associated with Lucas often rely on information about a number’s factors or related numbers.

• Fermat numberRelated: Factoring large terms is how many composite Fermat numbers are established.

• Solovay–Strassen primality testRelated: A compositeness result can motivate factor-finding methods, though this test itself does not generally produce a factor.

• Euler's four-square identityRelated: Multiplicative closure lets square representations be assembled across factors.

• Erdős–Straus conjectureRelated: Factoring n can expose divisibility patterns that yield unit-fraction identities.

• Aliquot sequenceRelated: Factoring large terms is a major computational cost in extending sequences.

• Brahmagupta–Fibonacci identityRelated: Sum-of-squares representations can expose factors through differences of squares.

• Markov numberCompared with: Factorization is a different arithmetic route to classifying integers than Markov-triple generation.

• Sophie Germain's identityRelated: Substituting integers produces an explicit product that can reveal composite values.

• Adi ShamirRelated: The difficulty of factoring large integers underlies RSA, which Shamir co-invented.