Why is integer factorization so hard for computers?

Integer factorization is the process of breaking down a composite positive integer into its prime number components. For large numbers, especially semiprimes, classical computers find this problem extremely difficult, which forms the foundation of modern cryptography. While no efficient classical algorithm is proven to be impossible, quantum algorithms like Shor's algorithm can solve it in polynomial time.

What we know

• Every positive integer greater than 1 is either a prime number or the product of prime factors. [2]
• When integers are sufficiently large, no efficient non-quantum integer factorization algorithm is currently known. [2]
• The hardest instances of integer factorization for current techniques involve large semiprimes formed by the product of two prime numbers. [2]
• Shor's algorithm is a quantum algorithm that can find the prime factors of an integer in polynomial time. [4]

Still open

• It has not been mathematically proven that an efficient non-quantum integer factorization algorithm does not exist.

Where to go next

• what followedHow does RSA public-key encryption use factoring?
• how it workedWhat is Shor's algorithm?
• a case in pointHow does Pollard's rho algorithm work?
• the bigger pictureWhat are prime numbers?
• whoWho was Peter Shor?
• an unexpected connectionHow does a quantum algorithm threaten bank security?Shor's quantum algorithm can efficiently solve integer factorization, which directly undermines the security of RSA public-key cryptography used globally for secure communications.

Sources

• [1]integer factorization (Wikidata Q4846249) · CC0 1.0
• [2]Integer factorization · CC BY-SA 4.0
• [3]Integer factorization records · CC BY-SA 4.0
• [4]Shor's algorithm · CC BY-SA 4.0
• [5]Pollard's rho algorithm · CC BY-SA 4.0