Multiplying primes is easy, and internet security depends on undoing it being hard
Multiplying two large prime numbers takes a computer a moment. Working backwards to find those primes is another matter: no machine today can split a 500-digit number built from two random primes. That lopsided difficulty is exactly what keeps RSA encryption, used across the internet, secure.
Factorization means rewriting something as a product of simpler pieces, as 15 becomes 3 times 5. Ancient Greek mathematicians proved that every whole number above 1 breaks down into primes in exactly one way, apart from the order of the factors. That result, the fundamental theorem of arithmetic, makes primes the atoms of multiplication.
The simplest method is trial division. You only need to test divisors up to the square root of the number, since any larger divisor pairs with a smaller one. Testing in increasing order guarantees that the first divisor found is prime. Take a number that halves to 693: 693 splits into 3 times 231, 231 into 3 times 77, and 77 into 7 times 11, where the search stops because 7 squared already exceeds 11. Shortcuts help, such as skipping numbers whose digits add up to a multiple of 3. But the method bogs down quickly: Pierre de Fermat never noticed that his sixth Fermat number, only 10 digits long, is not prime, and checking it this way would take more than 10,000 divisions.
In algebra, factoring turns one hard problem into several easy ones, because if a product equals zero, one of its factors must. Although al-Khwarizmi was simplifying equations in the 9th century, factoring was not used even for quadratics until the work of Thomas Harriot, published in 1631, ten years after his death. Every polynomial with complex coefficients splits into linear factors, one per root, yet the Abel and Ruffini theorem shows those roots generally cannot be written with nth roots, so they are usually approximated numerically.
Unique factorization does not always survive. Certain rings of algebraic integers lack it, though their ideals still factor uniquely into prime ideals.
Source: Factorization
