■ 量子コンピュータ（暗号解読）

１９９４年にIEEE誌に発表された素因数分解に関するShorの論文は，高速な暗号解読を可能とする量子コンピュータの研究を推進する起爆剤となった。ショアの論文の骨子は，（量子フーリエ変換）を使って，ｎ桁の整数の素因数分解の位数ｒを効率よく求めるアルゴリズムを示したことにあり，因数分解の時間がｎの多項式の程度でおさまることが証明されている。これは，現在のRSA方式が数分で解読されることを意味し，このことにより量子コンピュータの研究が多いに加速されることになった。ショアの論文に入るまえに，現在のRSAの公開鍵暗号システムがどのようなアルゴリズムで構成されているのかを最初に確認しておく。

（１）RSAの公開鍵暗号システム

ＲＳＡ(MITのRivest, Shamir, Adleman3名の頭文字）公開鍵暗号システムは，大きな数の素因数分解が困難（非常に時間がかかる）ことに依拠したセキュリティシステムである。暗号システムの動作原理を「鍵のついた秘密箱」で考えてみる。送信者(Alice)は受信者(Bob)にＭというメッセージを箱に入れて，鍵ｅをかけて送るとする。Bobが合鍵ｄを持っていれば箱は簡単に開けられるが，Bobが遠くに離れている場合，合鍵ｄを事前に送る上での紛失・盗難のリスクがある。通常鍵ｅと合鍵ｄは同じ物であるが，箱を開ける合鍵ｄが，閉める鍵ｅと異なるシステムがＲＳＡ方式である。ＲＳＡでは，閉める鍵ｅはいくらでも複製を作れる（一般に公開するので公開鍵と呼ぶ）が，開ける鍵ｄはただ一つ（秘密鍵）である。 Bob宛に送ることはBobの知人であれば誰でもよいので鍵ｅを予めコピーしておいて知人に配っておくのであるが，Bob宛の秘密箱を開けられるのはBobだけである，という仕組みである。

AliceがBobに，Ｍ mod ｎというメッセージを送るとする。ｎは後で説明する理由によって，素数ｐとｑの積であるとする。Bobはあらかじめ素数ｐとｑをもっていて，それは秘密になっている。Aliceは通信文を送る前に，Bobにｎを送り，Bobは通信文が自分宛であることをｐｑ= ｎの計算により確認する。傍受者（Eve)はｎをしることができるが，因数分解が難しいので，実際上ｐとｑを知ることができない。次にAliceは，公開鍵ｅを送る。これを受けて，受信者Bobは直ちにｅｄ = 1 mod (p - 1)(q - 1)を満たすｄを計算する。ここで，mod (p - 1)(q - 1) = Φ(n)（p-1,q-1の最小公倍数であり，ｎ以下の数で，ｎと互いに素である整数の数を表す）であり，Φ(n)をオイラー数と呼ぶ。ここで，暗号を復号化するのはｄであるが，このｄを計算できるのは素数ｐとｑを知っている者，即ちBobのみ，ということがポイントである。具体的に以下のような手順である。

Aliceは通信文Ｍ mod ｎ(=pq)を暗号化してＭ^e mod n をBobに送る。Bobは鍵ｄを用いて，(Ｍ^e )^d= Ｍ^ed = Ｍ^{kΦ(n) +1} = Ｍ mod nと復号化できる。傍受者Eveは鍵ｄを計算できないので復号化できない。具体的に数字を当てはめてみる。
十分大きな素数ｎとして143, p = 11, q = 13（たいして大きくはないか！）をとる。暗号化したい通信文（平文）を適当に数字列に変換し，ｎより小さい整数Ｍとする。Ｍが5であったとする。オイラー数Φ(n)=最小公倍数(p - 1)(q - 1) = 10 x 12 = 60 と互いに素な定数ｅをとり，ｂ = Ｍ^e mod ｎを作るとこれが暗号文である。60と互いに素な定数ｅとして７をとると，
ｂ = ５⁷ mod 143 = 78125 mod 143 = (546 x 143 + 47) mod 143 = 47
となり，暗号文ｂとしては47が作成された。ここで，143（=ｎ）と７（=ｅ）は公開鍵として公表する。
次に復号化であるが，ｅｄ = 1 mod (p - 1)(q - 1)となるｄを探すことになる。これは，7・ｄ = １ mod 60 であるが，ｄとして43をとると，7 x 43 = 301 = 5 x 60 + 1であり，たしかに7・ｄ = １ mod 60 を満たしている。この43を使うと，
暗号文47⁴³ mod 143 = 5 となりもとの平文を数字化したＭを得る。ＲＳＡにおいては２つの素数の積ｐｑ= ｎを用いるのがポイントである。ｎが公開されていてもｐ，ｑを逆計算するのは，ｎの桁数が大きいと非常に困難である。一説によれば200桁の整数の因数分解には現在最高速のスーパーコンピュータを使っても数十億年はかかると言われている。RSAでは1024ビットが普通であるから1024Log₁₀2 (約30桁）でも実用上ほとんど問題ない。RSAの最高は2048ビットなので６０桁の整数に相当する。2048ビットは電子署名の証明書を発行する認証局の暗号化に使われている。

（２）素因数分解の原理

（Step1）互いに素な数Ｎ，ａを見つける。

複合数Ｎの素因数分解をするには，まずその因数を一つ見つけ，Ｎをそれで割り，あとはこれを繰り返す。どのようにして因数を見つけるか，というと，Ｎより小さい整数ａを選んで，Ｎとａの最大公約数gcd（Ｎ，ａ）をユークリッドの互除法（最大公約数を引き算で計算する方法）で計算する。これが１でなかったら因数が見つかったことになる。gcd（Ｎ，ａ）が１ならＮとａは互いに素であるから次のステップに進む。

（Step2）位数ｒを見つける。

Ｎとａが互いに素であるとき，

ａ^r = 1 mod N   ---①

であるような最小なｒを位数（Order)と呼ぶ。Ｎとａが互いに素であるとき，位数ｒが必ず存在する。これを整数論では，フェルマーの小定理と呼ぶ（〔証明〕）。

ｒが偶数なら①式を変形して，

(a^r/2 + 1)(a^r/2 - 1) = 整数  x  Ｎ

を得るので，a^r/2 ± 1=0 mod Nでないかぎり最大公約数gcd(a^r/2 + 1, N)またはgcd(a^r/2 - 1, N)が因数を与える。

ｒが奇数またはa^r/2 ± 1=0 mod Nなら別のａを選んで，ｒが偶数であり，a^r/2 ± 1=0 mod Nでないような数ａを得るまでａを変えてやればよい。大雑把には，確率50%以上で望ましいａを得ることができるので，この試行はすぐに終わる。 具体的に例を挙げる。

Ｎを35とし，素因数分解したいとする。ａとして4をとると， ４^p mod 35をｐを１から始めて計算する。
4¹ mod 35 = 4,
4² mod 35 = 16,
4³ mod 35 = 64 mod 35 = (1 x 35 + 29) mod 35 = 29,
4⁴ mod 35 = 256 mod 35 = (7 x 35 +11) mod 35 = 11,
4⁵ mod 35 = 1024 mod 35 = (29 x 35 +9) mod 35 = 9,
4⁶ mod 35 = 4096 mod 35 = (117 x 35 + 1) mod 35 = 1,
4⁷ mod 35 = 16384 mod 35 = (468 x 35 + 4) mod 35 = 4,
となり，このあとは16, 29, 11, 9, 1, 4…と続くことになる。ｐが6，12，18，…のときに４^p mod 35が１になることが分かる。従って最小のｐは6であり，偶数であることから，これが位数である。
このとき，最大公約数はユークリッドの互除法で計算して，
gcd(a^r/2 + 1, N)=gcd(4³ + 1, 35)=gcd(65, 35)=5，かつ
gcd(a^r/2 - 1, N)=gcd(4³ － 1, 35)=gcd(63, 35)=7
となってＮ＝３５の素因数として５と７を得ることができた。

以上が古典的な素因数分解のアルゴリズムであるが，実際やればわかるが大きな数の場合にｒを求めるのは容易ではない。ためしにＮを２２１，ａを２０としてみればｒは４８である（筆算でやると気が遠くなる！）。ａが１６８ならｒは８と小さいが，５０でｒは12，９２でｒは１６である。上記のアルゴリズムをそのままプログラムしても計算には相当の時間を要することが理解できよう。

（３）ショアのアルゴリズム

ショアは，複合数Ｎが与えられた場合に，ランダムに選ばれたＮと互いに素であるａの位数ｒが存在するならば，そのｒを与える量子アルゴリズムを考案した。即ち，Ｎとａが互いに素であるとき，

ａ^r = 1 mod N   ---①



を満足するｒを多項式時間（log N）^kの範囲内で与える，確率的アルゴリズムを考案したのである。

ショアはmod ｑの離散フーリエ変換（DFT_qと記す）と呼ばれるユニタリー変換から出発した。DFT_qは，ｑ次元ヒルベルト空間上で作用し，基底|0>,…,|q-1>に関して，次のように定義される：

DFT_q：|a> → 1/√ｑΣ_c=0^q-1exp(2πiac/q)|c>

この（量子フーリエ変換）は，状態|a> が|0>のときは，基底|0>,…,|q-1>の等しい重みで重ね合わされていることに注意する。従って，ａ mod Nを適当に選んで，|0>にDFT_qを施すと，

1/√ｑΣ_m=0^q-1|N,a>|m>

を得る。この状態からａ^m mod Nを各成分毎に計算し，直積をとると，

1/√ｑΣ_m=0^q-1|N,a>|m>|ａ^m mod N>

を得ることができる。この状態において，|ａ^m mod N>の観測を行う。その結果として，ａ^j mod N (= y mod N)という値を得たとする。ｒが位数とすると，このときａ^j≡ａ^kr+j（ｋは整数）が成立している。従って，ｍの値としては，ｊ，j + r, j + 2r,…,j + Arが観測により選ばれたことになる。ここで，Aは(q - j)/rより小さい最大の整数とする。

ｊは観測によって選択されていることが本質的である。ｊ≦ ｒであり，ｊ≦ ｒ ＜ N かつ ｑ ≒ N²であるから，A ≒ (q - j)/r = ｑ/r - 1であることに注意すると，観測後の状態は，

|Ψ_j> = 1/√(A+1)Σ_k=0^A|N,a>|kr+j>|y>
   = √r/√qΣ_k=0^{q/r - 1}|k r + j>    ---②

と表すことができる。以降，状態|N,a>|y>は固定されているので記載は省略する。

【位数ｒの抽出】

ショアのアルゴリズムの本質は位数ｒの抽出を量子コンピュータで行うことにある。上記②式までを，状態|0>にDFT_qを施し（量子フーリエ変換を行う），結果を観測することで得ることができた。ショアは，②に再度DFT_qを施すことで位数ｒが抽出できることを示した。Ｍ = q/rとおき，②に再度DFT_qを施すと，

|Ψ_out> = √r/qΣ_c=0^q-1Σ_k=0^{M - 1}exp(2πi(k r + j)c/q)|c>
= √r/qΣ_c=0^q-1exp(2πijc/q)Σ_k=0^{M - 1}exp(2πikc/M)|c>
= Σ_c=0^q-1 α_c |c>

このとき，以下のことが成り立つ。

Σ_k=0^{M - 1}exp(2πikc/M)
= Ｍ （ｃがＭの倍数の時）または
= ０ （それ以外の時）

従って，|c>の振幅である α_c は，

α_c = Ｍexp(2πijc/q)（ｃがＭの倍数の時）
    = ０ （それ以外の時）

となる。従って，|Ψ_out> はｃがＭの倍数(c = sM)の時のみ値を持つので，

|Ψ_out> = √r/q・ＭΣ_c=0^q-1exp (2πijc/q)|c>
= 1/√r Σ_s=0^r-1exp (2πijsM/q)|sM>
= 1/√r Σ_s=0^r-1 exp(2πijs/r)|sq/r>   ---③

となって，周期ｑの状態から周期ｒの状態に変換されることが分かる。この状態で観測を行うと，ｓ = 0, 1, 2, …, r - 1 なる倍数sq/rが等確率1/rで選ばれる。最初のシフトｊは，もはやどこにも出てこないことが重要である。つまり，最初の観測の値は重要ではない。重要なのは，ｓ = 0, 1, 2, …, r - 1 なる倍数sq/rが等確率1/rで選ばれることである。数式で書くと，

ｃ = 整数・q/r，即ち，

c/q = 整数・(1/r)   ---④

ｃは観測値，ｑはｑ ≒ N²で既知であることから，観測を繰り返すことにより④の周期性(1/r)を計算で求めることができる。即ち，位数ｒを求めることができる。

ここで注意すべきことは，④からｒが正しく求められるのは，整数（ｓ）とｒが互いに素の場合に限ることである。c/q < １なので④の右辺の整数はｒより小さい。ｒよりも小さい数で，ｒと互いに素な数の総数はオイラー数Φ(r)と呼ばれ，その数は e^-γr / log(logr)より多いことが数論で知られている（γはオイラー定数）。言い換えると，log(logr)回も試行すれば互いに素な整数に当たる，ということである。ｒはＮより小さいので，最大でもlog(logN)回の試行で正しいｒを得ることができる。この試行を検算と呼ぶ。

以上見てきたように，ショアのアルゴリズムを量子コンピュータで実行するのにかかる時間は，フーリエ変換，検算，最大公約数gcd，観測時間の総数である。いずれも多項式時間で実行可能であることがポイントである。



（２００２年６月１６日；第一版 Copyright 寒泉）