The process of decomposing a composite integer into a product of smaller integers, typically into prime factors; for n>1 this means producing a multiset {p_i} of primes with n=∏ p_i^{e_i}.

Principle

Integer factorization leverages arithmetic structure (divisibility, order of elements modulo n, algebraic factorizations) and algorithmic techniques (trial division, sieves, Pollard's rho, elliptic curve methods, number field sieve) to recover nontrivial factors; its hardness underlies many cryptographic assumptions.

Demonstration

Concrete algorithms: trial division quickly finds small prime factors; Pollard's rho finds moderate factors via pseudorandom walks; elliptic curve factorization (ECM) is effective for medium-size prime factors; the general number field sieve (GNFS) is the asymptotically fastest known method for large general integers used in record factorizations.

Misapplication

Assuming that a single heuristic or small-parameter algorithm will factor all integers efficiently (for example expecting Pollard's rho to succeed on semiprimes with very large prime factors), or confusing integer factorization with polynomial factorization or with primality testing.

Consequence

Successful factorization yields complete arithmetic information about n (its prime decomposition) and breaks cryptographic schemes relying on presumed factoring hardness; algorithmic advances change the threshold of practical security and motivate key-size recommendations.

Reversal

The reversal is primality testing: instead of producing factors, one decides if n is prime; a positive primality decision obviates factorization, while factorization is strictly stronger information and generally harder to obtain.

Boundary

Task applies to integers given in standard representation; excludes factoring ideals in number fields, factoring polynomials over fields (distinct algorithms and complexity), and problems where the arithmetic context or auxiliary structure (special form integers) can be exploited separately.

Semantic Tension

Tension between worst-case theoretical complexity and practical 'typical' hardness: some integers (special forms) factor easily while random large semiprimes resist all known algorithms; also confusion arises between factoring an integer and computing multiplicative structure in other algebraic objects.

Synthesis

Integer factorization is the computational task of breaking an integer into prime constituents using a spectrum of algorithms that exploit divisibility and algebraic structure; its practical difficulty depends on the size and special form of factors and has central implications for computational number theory and cryptography.