factorization
The process of finding the prime factors of a large number; computationally easy in reverse (multiplying factors gives the product quickly) but very difficult to solve (given a product, find the factors); the basis for RSA encryption security
As defined in The Map of Quantum Computing - Quantum Computing Explained
Where it comes up · 1
Most important claims · 3 of 3Search all claims for “factorization” →
- Classical computers are very versatile devices, and there is nothing to say that someone may not find a very clever classical algorithm that could solve the hardest problems like integer factorization more efficiently than currently known algorithms; people think it is very unlikely, but it is not ruled out.The Map of Quantum Computing - Quantum Computing Explained
- Post-quantum encryption schemes are being developed which don't use integer factorization, and quantum cryptography is another technology from quantum physics that can help with cryptographic security without relying on factorization hardness.The Map of Quantum Computing - Quantum Computing Explained
- Integer factorization is a problem where there is a very fast classical algorithm for multiplying two large numbers together, but finding the original factors is much more difficult because the search space of possible factors is so large, and there is no efficient classical algorithm for finding the factors of large numbers.The Map of Quantum Computing - Quantum Computing Explained