量子コンピューターはまだ実用化されていないが、暗号化がなされたデータを保存することは可能であり、これが将来的に復号される可能性がある。この手法を SNDL (store now, decrypt later) という。
量子コンピューターが RSA 暗号を解読するアルゴリズムは次の通り。目標は2つの素数の積 を素因数分解することだが、まず
と互いに素な整数
を用意する (適当に選べばまず互いに素となるはず) 。つぎに
となる
を探す。もし見つかれば
だが (和と差の積は平方の差) 、この式の2つの因数はそれぞれが
と因数を共有している可能性が高いので、最後にそれらをユークリッドの互除法で見つければ目標が達成される。
このアルゴリズム自体は古典コンピューターで実行可能であるものの、 の大きさによって実行時間を非現実的な長さにすることができていた。ところが量子コンピューターでは重ね合わせ (superposition) を利用することによって多数の
を同時に計算することができる。重ね合わせられた答えを読み出すためには、剰余が周期的であることによって、量子フーリエ変換を利用することができる。
量子コンピューターに対しても安全な暗号の候補として、格子点の性質を利用したものがある。数千もの次元をもつ多次元空間において、ベクトルの和を計算することはできるが、与えられた格子点を基底ベクトルに分解することは難しい。
以上が動画の内容の要約だが、以下に視聴中に記した擬似コード形式のメモを載せる。
N: p×q;
let g: coprime to N;
for r ∈ Z⁺:
if g**r ≡ 1 (mod N):
(g**(r/2) + 1)*(g**(r/2) - 1) ≡ 0 (mod N)
// likely to share factor with N: Euclid's algorithm
// remainder is cyclic: QFT
