一言でいうと
Shows a quantum computer can factor large integers exponentially faster than the best known classical algorithm — the result that launched quantum cryptanalysis.
要点
- ▸Gives a polynomial-time quantum algorithm for integer factoring and discrete logarithms.
- ▸Uses the quantum Fourier transform to find the period of a modular exponential function.
- ▸Directly threatens RSA and elliptic-curve cryptography, which rely on these problems being hard.
やさしい解説
Classical computers struggle to factor very large numbers, and that difficulty is what keeps RSA encryption secure. Shor showed that a sufficiently large, error-corrected quantum computer could factor those numbers quickly by turning factoring into a period-finding problem and solving it with quantum interference. No such machine exists yet — breaking RSA-2048 would need millions of high-quality qubits — but the algorithm proves the threat is mathematical, not hypothetical.
なぜ重要か
Shor's algorithm is the single biggest reason quantum computing is treated as strategically important. It is why NIST standardized post-quantum cryptography and why 'harvest-now, decrypt-later' is a real concern today.
関連用語
Shor's Algorithm
AlgorithmsA quantum algorithm for integer factorization with exponential speedup over the best known classical algorithms.
QFT
AlgorithmsQuantum Fourier Transform — the quantum analog of the discrete Fourier transform, exponentially faster.
Post-Quantum Cryptography
AlgorithmsClassical cryptographic algorithms designed to be secure against attacks from both classical and quantum computers.