Facts
Why OpenWhen the numbers are sufficiently large, no efficient non quantum integer factorization algorithm is known, yet it has not been proven that no such algorithm exists. The presumed difficulty of this problem is what the security of RSA public key encryption and signatures rests on, so the gap between no algorithm known and no algorithm possible carries the weight of most of the world's encrypted traffic. Peter Shor showed in 1994 that a quantum computer could factor in polynomial time, which sharpens rather than settles the classical question. 1 What Would ResolveAn efficient classical factoring algorithm, which would break RSA, or a proof that none exists, which would put its security on solid ground; large scale quantum computers would change the practical stakes either way. 1 Discipline NeededComputational number theory, Cryptography 1 Question Kind Question Status Open Question
When the numbers are sufficiently large, no efficient non quantum integer factorization algorithm is known, yet it has not been proven that no such algorithm exists. The presumed difficulty of this problem is what the security of RSA public key encryption and signatures rests on, so the gap between no algorithm known and no algorithm possible carries the weight of most of the world's encrypted traffic. Peter Shor showed in 1994 that a quantum computer could factor in polynomial time, which sharpens rather than settles the classical question.
What would resolve this An efficient classical factoring algorithm, which would break RSA, or a proof that none exists, which would put its security on solid ground; large scale quantum computers would change the practical stakes either way.
OpenComputational number theory, CryptographyWikipedia: Integer Factorization
Cross-Tradition Connections
Sources
Reader Challenges (0 open reader challenges)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.
View At A Past Year
The atlas records no dated fact of its own for this entry, so there is no other year to choose.