【教えて先生】ショアのアルゴリズムとは何か～量子コンピュータが暗号を破る仕組み

ひなたさん、鋭いですね。資料には「ショアのアルゴリズム」というものが出てきます。これは量子コンピュータで暗号を解読するための計算方法のことです。たとえるなら、金庫の鍵の組み合わせを当てずっぽうで試すやり方です。これだと何百年もかかってしまいます。でも特別な近道を知っていれば、一瞬で分かるんです。そんなイメージです。正確に言うと、計算には2つの種類があります。一つは、大きな数を掛け算前の数に分解する計算です。これを素因数分解と言います。

もう一つは、楕円曲線という計算に使う図形を使った問題です。楕円曲線とは、なめらかな曲線でできた図形のことです。この図形の上のある点から、特別な計算を何度も繰り返して別の点にたどり着くとします。何回計算したかを当てるのがとても難しく、これを離散対数問題と呼びます。この二つの計算を、量子コンピュータで速く解けるようにしたのがショアのアルゴリズムです。これが暗号を破る力につながるんです。ここ、もう少し気になりますか。