Integer Factorisation

mathematics number-theory cryptography

Definition

Integer Factorisation

The integer factorisation problem is the problem of decomposing a positive integer into a product of prime numbers. Given a composite integer $n$, find primes $p_1,p_2,\dots ,p_k$ and positive integers $e_1,e_2,\dots ,e_k$ such that

$$n=p_1^{e_1}\cdot p_2^{e_2}\cdots p_k^{e_k}$$

Cryptographic Significance

Computational Hardness

For sufficiently large integers (e.g. products of two large primes), no efficient classical algorithm is known for integer factorisation. This hardness assumption underlies the security of RSA and other asymmetric cryptographic schemes.