量子アニーリングの理論を学んでみる-その1最適化問題とイジング模型(数式)

「量子アニーリングの基礎 西森秀稔 大関真之」という本を読み始めたので、学んだことのアウトプットも兼ねつつ、記事を書いてみることにしました。量子力学についてある程度知っている方を対象にしていますが、数学的素養があれば理解できると思います。

本記事「量子アニーリングの理論を学んでみる-その1最適化問題とイジング模型(数式)」では、最適化問題をイジング模型に帰着できる、つまり、なぜ最適化問題を量子アニーリングの方法で探索できるのかを示します。

 

量子アニーリングとは、端的に言えば、\(\pm1\)の値をとるスピンを利用して、最適化問題を解こうと言う技術のことです。

電子の、スピンという、物質の磁性に関係する物理量は、量子力学的に\(\pm 1\)の値だけとりうることが知られています。そして、系(取り扱う物質全体のなすものを一塊と見たもの)のエネルギーに関係する、ハミルトニアン\(H\)という関数が最小になる固有状態(これを基底状態と言います。)を目指すように系を操作します。ハミルトニアンを、解きたい最小化問題の関数と同じになるように最初から設定しておけば、これは最小化問題が解けたことになります。

この”系”をD-waveという会社が実用化し、既に市販されているのはニュースでご存知かも知れません。

その理論的背景を、数式を用いながら説明していきます。

 

イジング模型

イジング模型とは、磁場の作用する環境下における、複数の電子のなす系を抽象化したモデルです。

おのおのの電子のスピン\(\sigma_i\)は\(\pm1\)の値をとり得ますが、これを\(\pm1\)の値をとり得るイジング変数\(\sigma_i=(\pm1)\)と考えます。他にもイジング変数を実現する方法はありますが、この記事では電子の系を考えます。

電子スピン相互作用を考えます。\(i,j\)間の相互作用の比例定数を\(J_{ij}\)とすると、ハミルトニアンへの寄与として、

\[-J_{ij}\sigma_i \sigma_j\]

と書けます。これは、スピンがそろうと系のエネルギーへの寄与は小さくなり、逆を向けば大きくなることを表しています。(\(J_{ij}>0\)の場合、これは強磁性的相互作用と呼ばれます。負の場合は今言ったことが逆になります。)

また、おのおのの電子における局所磁場に関するハミルトニアンへの寄与も考えます。局所磁場とは、外部磁場と系(自分と周りの電子たちの作るスピン)が作る磁場を合わせた磁場の、そのおのおのの電子のいる地点での磁場です。比例定数を\(h_i\)として、

\[-h_i \sigma_i\]

と書けます。これも、磁場にスピンの向きがそろえばエネルギーへの寄与は小さくなり、逆を向けば大きくなることを表しています。

よって、系全体のハミルトニアンは、

\[H(\mathbb{\sigma})=-\sum_{i<j}J_{ij}\sigma_i \sigma_j-\sum_{i=1}^N h_i \sigma_i\]

と書けます。

第一項の\(i<j\)は、同じ組を2回数えないためのものです。

 

フラストレーション

単純な系として\(J_{ij}=const>0\)の場合を考えれば、系の基底状態は自明、全てのスピンが同じ値をとれば最適化問題が解けたことになります。実際の最適化問題はそんなに単純ではありません。ここで、フラストレーションという概念を導入します。

まず、局所磁場のない(\(h_i=0\))、電子が2つ(\(N=2\))の簡単な場合を考えてみましょう。相互作用のある(\(J_{ij}\neq0\)の)電子対を、ボンドと呼びます。

\[H=-J\sigma_1\sigma_2\]この場合は簡単で、\(J_{ij}>0\)の場合はスピンがそろえば、\(J_{ij}<0\)の場合はスピンが逆になれば系全体の基底状態を実現できます。局所的な基底状態が系全体の基底状態を実現する、という言い方もできます。

電子が3つ(\(N=3)\)の場合はどうでしょうか。

\[H=-J(\sigma_1\sigma_2+\sigma_2\sigma_3+\sigma_3\sigma_1)\]

\(J_{ij}=const<0\)とします。うち2つは、スピンが逆になれば局所的には基底状態を実現できます。ところが、もう1つの電子を考えると、これはどっちを向こうが、どちらかもう一方の電子と同じ向きになってしまいます。これがフラストレーションです。フラストレーションとは、全体の基底状態が実現しているとき、必ずしも局所的な基底状態が実現されているとは限らないということです。

フラストレーションが発生すると、エネルギーの縮退(異なる状態が同じエネルギーを持ちうること)が起きます。例の電子3つの系では、\(\sigma_i=\pm1(i=1,2,3)\)ですから異なる状態の数は8つありますが、全てのスピンが同じ向きを持つ場合の2つ以外は、全て基底状態になります。

 

最適化問題とイジング模型

ところで、みなさんは電子のスピンと2進数が、相性がいいのに気がついたでしょうか。つまり、\(0\)をスピン\(-1\),\(1\)をスピン\(+1\)に対応させればよいのですから、2進変数を\(q=0,1\)とすれば、\(q=\frac{\sigma+1}{2}(\sigma=2q-1)\)と考えればよいだけです。

 

最適化問題(組み合わせ最小化問題)、つまり\(F(q_0,q_1,…q_N)\)の最小化(最大化の時は符号を逆転すればよい)について考えるために、テーラー展開

\[F(q_0,q_1,…q_N)=c_0+ \sum_{i=1}^N c_i^{(1)}q_i+\sum_{i,j}c_{ij}^{(2)}q_i q_j+\sum_{i,j,k} c_{ijk}^{(3)}q_i q_j q_k +\cdots\]

を、電子のスピンで表現することを考えます。上式に\(q_i=\frac{\sigma_i+1}{2}\)を代入すると、\(\sigma^2=1\)の関係から\(N+1\)次以上の項が消え、以下の式に変換できることがわかります。

\[F(\sigma_0,\sigma_1,…\sigma_N)=c^\prime_0+\sum_{i=1}^N c_i^{\prime(1)}\sigma_i+\sum_{i<j}c_{ij}^{\prime(2)}\sigma_i \sigma_j+\sum_{i<j<k} c_{ijk}^{\prime(3)}\sigma_i \sigma_j \sigma_k +\cdots+ c_{123\cdots N}^{(N)}\sigma_1 \sigma_2 \cdots \sigma_N\]

よって最適化問題は、多体相互作用を持つイジング模型の基底状態を探す問題に帰着できることが分かりました。

量子アニーリングの理論を学んでみる-その2量子アニーリングを語るための、数学的準備(数式)

に続きます。

量子アニーリングの理論を学んでみる-その2量子アニーリングを語るための数学的準備(数式)

量子アニーリングの理論を学んでみるシリーズ

量子アニーリングの理論を学んでみる-その1最適化問題とイジング模型(数式)

の続きです。

前回、最適化問題を量子アニーリングの手法で解ける、つまり最適化問題はイジング模型の基底状態を求めることに帰着できることを学びました。

次の記事では、量子アニーリングの手法でどのように計算するか、具体的にどのようにして基底状態を求めるのかを説明します。

まずこの記事で、そのために必要な程度に、量子力学を簡単に説明します。量子力学をある程度知っている人は、あまり読む必要はないかもしれません。下の()は興味のある方だけ読んでください。

 

(個人的に、論理を誤魔化して議論を進めるのが好きではないので、一応これを書いておきます。量子力学では、ヒルベルト空間\(\mathcal{H}\)における抽象的なベクトルの元として、系の状態を表現します。物理量は、ヒルベルト空間\(\mathcal{H}\)の元に対する作用素として定義されます。ただ、この記事では元が非可算無限個ある状態空間(例えば、粒子の運動)を考える必要がないので(可算無限でさえも)、この抽象的なベクトルは馴染み深い、普通のベクトル\(\mathbb{C}^N\)に対応付けて考えることができます。この場合、作用素は行列で表現できます。とくにスピンに関しては、状態空間の次元がたったの\(2\)なので、\(\mathbb{C}^2\)ととることができます。他の量子コンピュータの教科書を見てみても、量子力学の枠組みに関してはこの記事の程度の説明です。詳細は、「現代の量子力学 J・Jサクライ」などが詳しいです。以下は、このような枠組みのもとでの状態の一つの表現形式であり、多くの量子力学の教科書で採用されています。)

 

これから量子力学を語るために、まずはそのための言葉を準備しましょう。

\(z\)方向のスピンの\(\pm1\)に対応するベクトルを、

\[\mid \uparrow \rangle=\begin{pmatrix} 1\\0\end{pmatrix},\mid \downarrow \rangle =\begin{pmatrix}0\\1\end{pmatrix}\]

とおきます。

次に、パウリ行列と呼ばれる、スピンを表現するための行列を導入します。

\[\sigma_z=\begin{pmatrix}1 & 0 \\ 0 &-1\end{pmatrix}\]

これを、上で導入したベクトルたちに作用させると、

\[\sigma_z \mid \uparrow \rangle=\begin{pmatrix}1 & 0 \\ 0 &-1\end{pmatrix} \begin{pmatrix} 1\\0\end{pmatrix}=\begin{pmatrix} 1\\0\end{pmatrix}\]

\[\sigma_z \mid \downarrow \rangle =\begin{pmatrix}1 & 0 \\ 0 &-1\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix}=-\begin{pmatrix}0\\1\end{pmatrix}\]

となりますから、これらは固有値\(\pm1\)に対応する固有ベクトルになっていることがわかります。この固有値こそ、スピンの実際にとりうる値を表しています。

これら固有ベクトルの、規格化された(\(\alpha^2+\beta^2=1\)とした)線形結合

\[\mid \psi \rangle =\alpha \mid \uparrow \rangle+\beta \mid \downarrow \rangle \]

は、状態の重ね合わせを表現します。

規格化とは、全体の確率を\(1\)にするためのものです。今まで例に挙げてきた状態ベクトルも、全て規格化されています。実は、このベクトル\(\mid \psi \rangle\)に現れた\(\alpha^2\)は上向きスピン、\(\beta^2\)は下向きスピンを観測する確率になっています。それが量子力学の枠組みです。規格化とは、これらの和が\(1\)になるように設定することです。(正確には、一般に係数\(\alpha\)は複素数のため、係数の絶対値の二乗\(\mid \alpha \mid^2\)です。)

また、\(x\)方向のスピンを表す行列

\[\sigma_x=\begin{pmatrix}0 & 1 \\ 1 &0\end{pmatrix}  \]

を導入します。

この行列の\(\pm1\)に対応する固有ベクトルは、
\[\mid + \rangle=\begin{pmatrix}1\\1\end{pmatrix},\mid – \rangle=\begin{pmatrix}1\\-1\end{pmatrix}\]

です。確認してみてください。

\(\sigma_y\)も、もちろんありますがここでは使わないので省略します。

 

また量子力学の枠組みにおいて最も重要な仮定、時間に依存する状態ベクトルのシュレディンガー方程式は、

\[i\frac{\partial}{\partial t}\mid \psi(t)\rangle=\hat{H}(t)\mid\psi(t)\rangle\]

です。

時間に依存しないシュレディンガー方程式は、

\[\hat{H}\mid\psi\rangle=E\mid\psi\rangle\]

です。

詳しい解説は量子力学の専門書に譲りますが、これらの式にそこまで深く立ち入る必要もないので、これで十分でしょう。

量子アニーリングの理論を学んでみる-その3実際に、どのように量子計算を実行するのか(数式)

に続きます。

 

量子アニーリングの理論を学んでみる-その3実際に、どのように量子計算を実行するのか(数式)

前々回では、最適化問題を量子アニーリングの手法で解ける、つまり最適化問題はイジング模型の基底状態を求めることに帰着できることを学びました。

前回では、この記事の理解に必要な、多少の量子力学を解説しました。

この記事では、実際に、どのようにして量子アニーリングの計算を実行するのか、つまりイジング模型の基底状態をいかにしてもとめるかを解説します。

量子アニーリングの理論を学んでみる-その2量子アニーリングを語るための数学的準備(数式)

の続きです。

 

目標は、イジング模型

\[\hat{H}_0=-\sum_{i<j}\hat{\sigma}_i^z \hat{\sigma}_j^z\]

の基底状態を求めることでした。ちなみに量子力学では、表現したいものがただの数ではない(演算子や行列など)であることを強調するため、上に\(\hat{}\)をつける習慣があります。

そこで、時間とともに変化するハミルトニアン

\[\hat{H}(t)=-\sum_{i<j}\hat{\sigma}_i^z \hat{\sigma}_j^z-\Gamma(t)\sum_i^N \hat{\sigma}_i^x=\hat{H}_0-\Gamma(t)\sum_i^N \hat{\sigma}_i^x\]

を導入します。

添え字\(i\)は、それぞれの電子(サイト)のみにしか作用しないことを表します。もとの\(z\)軸方向のみのハミルトニアンに加え、電子に\(x\)方向に磁場がかかっている状況と同じですから、横磁場イジング模型のハミルトニアンと呼ばれます。

初期状態として、\(\Gamma(0)\)が第一項に比べて十分大きい場合を選ぶと、ハミルトニアンは

\[\hat{H}(0)=-\Gamma(0)\sum_i^N \hat{\sigma}_i^x\]

となり、この基底状態は自明、それぞれのサイトの基底状態の積(複数のサイトの状態を同時に表しすためのもの。\(\otimes\)を用いる。)であるから、\(\mid +\rangle=\frac{\mid \uparrow\rangle+\mid\downarrow\rangle}{\sqrt{2}}\)を用いて、

\[\mid \psi (0)\rangle=\mid++\cdots+\rangle=\mid+\rangle_1 \otimes \mid+\rangle_2 \otimes \cdots \otimes \mid+\rangle_N=\prod_{i=1}^N \mid + \rangle_i=\frac{1}{2^{\frac{N}{2}}}\prod_{i=1}^N(\mid \uparrow\rangle_i+\mid\downarrow\rangle_i)\]

となります。

これは、

\[\mid \psi (0)\rangle=\frac{1}{2^{\frac{N}{2}}}(\mid\uparrow\uparrow\cdots\uparrow\rangle+\cdots\mid\downarrow\downarrow\cdots\downarrow\rangle)\]

とも表せるように、サイト\(1\)から\(N\)までがそれぞれ上スピンか下スピンであるかの、全ての組み合わせ\(2^N\)個を等しく足し合わせたものです。もとめたいイジング模型のハミルトニアン\(\hat{H}_0\)を求めたいのだから、同じ重みの状態から出発するのは理に適います。

あとは、\(\hat{H}(t)=-\sum_{i<j}\hat{\sigma}_i^z \hat{\sigma}_j^z-\Gamma(t)\sum_i^N \hat{\sigma}_i^x\)における\(\Gamma(t)\)を徐々に\(0\)に近づければ、系は(状態ベクトルの時間に依存する)シュレーディンガー方程式

\[i\frac{\partial}{\partial t}\mid \psi(t)\rangle=\hat{H}(t)\mid\psi(t)\rangle\]

に従い、自然に、求めたいハミルトニアン\(\hat{H}_0\)の基底状態へと変化します。

各時刻において、\(\Gamma(t)\)の変化が十分小さい(これを、量子断熱と言います)ならば、各時刻における状態は、時間に依存しないシュレディンガー方程式

\[\hat{H}(t)\mid\psi(t)\rangle=E(t)\mid\psi(t)\rangle\]

と近似できる(ほぼ等しいと見なせる)から、基底状態の探索において、全ての時刻におけるハミルトニアンの基底状態をなめらかに移りながら変化していきます。

ちなみに、この近似ができる条件を、量子断熱条件と言います。

この条件の詳しい導出は、「量子アニーリングの基礎 西森秀稔 大関真之」を参照して下さい。

nemの楕円曲線暗号を基礎から学んでみる(数式)-その2 スカラー倍算の高速化

nemの楕円曲線暗号を基礎から学んでみる(数式)-その1 数学的準備続きです。

次は、スカラー倍算の高速化を考えます。

楕円曲線暗号を処理するプログラムでは、暗号を生成するにせよ、暗号を解読するにせよ、スカラー倍算の計算が重要です。そこで、方法を考えてみます。

素体\(\mathbb{F}_p\)上の四則演算では、加算・減算に比べ、乗算、さらには除算はもっと手間がかかります。自分で、適当な数字でやってみれば実感できます。しかし、楕円曲線の加法公式は除算の計算を必要とするため、その計算も長い時間を必要とします。そこで、この除算を避けるため、射影座標と言うものを導入します。

射影座標\((X,Y,Z)\)において、射影座標全体の集合を\(V\)とするとき、\((x,y,z),(X^\prime,Y^\prime,Z^\prime) \in V\)に関して、

\[(X^\prime,Y^\prime,Z^\prime)=(cx,cy,cz)\]

となる\(c\in \mathbb{F}_p\backslash \{0\}\)が存在するとき、この2点を同一視(同じと考える)します。つまり、

\[(X,Y,Z)=(2X,2Y,2Z)=\cdots =(X/Z,Y/Z,1)\]

となります。そこで、普通の座標(アフィン座標)上のある点\((x,y)\)と、射影座標における座標値\((x,y,1)\)を同一視します。このとき、射影座標における点\((X,Y,Z)\)は、アフィン座標上の\((X/Z,Y/Z)\)と同一視できます。

 

射影座標における楕円曲線の定義方程式は、\(y^2=x^3+ax+b\)に\(x=X/Z,y=Y/Z\)を代入して、

\[Y^2Z=X^3+aXZ^2+bZ^3\]

となります。

今までの様に、\(a=2,b=3\)として立体グラフを描いてみました。

目をボヤッと気を抜いた感じにして、重ねて見るヤツです。

\(z\)軸に平行な平面で輪切りにすると、前回のその1のグラフになることが想像できるでしょうか。

また射影座標では、無限遠点は\(X\)座標、\(Z\)座標がともに\(0\)の点と定義します。

射影座標における加法は、以下の様になります。

2点\(P(X_P,Y_P,Z_P),Q(X_Q,Y_Q,Z_Q)\)の和\(R=P+Q=(X_R,Y_R,Z_R)\)を以下の様に定義する。

\(P\neq Q\)のとき、

\(X_R=vA\)

\(Y_R=u(v^2X_P Z_Q-A)-v^3 Y_P Z_Q\)

\(Z_R=v^3 Z_P Z_Q\)

ただし、\(u=Y_Q Z_P-Y_P Z_Q ,v=X_Q Z_P-X_P Z_Q,A=u^2 Z_P Z_Q-v^3-2v^2 X_P Z_Q\)

\(P=Q\)のとき、

\(X_R=2hs\)

\(Y_R=w(4B-h)-8Y_P^2s ^2\)

\(Z_R=8s^3\)

ただし、\(w=aZ_P^2+3X_P^2,s=Y_P Z_P,B=sX_P Y_P,h=w^2-8B\)

では、この方法で\((1,1)+(1,1)\)を計算してみましょう。

射影座標では、\((1,1,1)+(1,1,1)\)

\(w=2\cdot 1^2+3\cdot 1^2=0\)

\(s=1\cdot 1=1\)

\(B=1\cdot 1\cdot 1=1\)

\(h=0^2-8\cdot 1=2\)

よって

\(X_R=4\)

\(Y_R=2\)

\(Z_R=3\)

ゆえに、\((x,y)=(\frac{4}{3},\frac{2}{3})=(3,4)\)

見事に、前回の計算と一致しました。

 

では、等しいはずの\((2,2,2)+(1,1,1)\)も、確認のために計算してみましょう。これは同じ点であることに注意して、

\(w=2\cdot 2^2+3\cdot 2^2=0\)

\(s=2\cdot 2=4\)

\(B=4\cdot 2\cdot 2=1\)

\(h=0-8\cdot 1=2\)

よって、

\(X_R=1\)

\(Y_R=3\)

\(Z_R=2\)

ゆえに、\((x,y)=(\frac{1}{2},\frac{3}{2})=(3,4)\)

やはり一致しました。

 

射影座標を用いてスカラー倍算を計算するには、アフィン座標\((x,y)\)を射影座標\((x,y,1)\)として計算し、最後にその結果\((X,Y,Z)\)をまたアフィン座標に戻せばよいので、除算は最後のみ必要になります。こうすることで、計算コストを削減できます。

さらに計算コストを削減するアルゴリズムもありますが、それらはここでは言及しません。

nemの楕円曲線暗号を基礎から学んでみる(数式)-その3 楕円曲線離散対数問題

に続きます。

nemの楕円曲線暗号を基礎から学んでみる(数式)-その3 楕円曲線離散対数問題

nemの楕円曲線暗号を基礎から学んでみるシリーズ

nemの楕円曲線暗号を基礎から学んでみる(数式)-その2 スカラー倍算の高速化の続きです。

次はいよいよ、楕円曲線暗号の解読が実質的に、ほとんど不可能な理由を考えていきましょう。

前回まで、素体\(\mathbb{F}_p\)上の楕円曲線の有理点の集合で、適当にベースポイント\(P\)を選びスカラー倍算を計算するのは、比較的簡単であることを学びました。

計算の分野では問題の難しさは、その問題が入力に対し、どれぐらいの時間で解けるかを目安に考えることが多いです。特に、ある入力の長さ\(n\)に対して平均でどれぐらい時間がかかるかとか、最悪どれぐらいかかるかなんかを考えたりします。ここでいう簡単とか難しいと言うのは、そういう意味です。

つまり、実質的に不可能とは、現在用いられているコンピュータの性能を以て問題に取り組んでも、入力の長さが大きい場合などは、現実的な時間(せいぜい数年)では解けないことを意味します。

 

ここでは今までとは逆に、点\(Q\)が点\(P\)の何倍になっているのかを求める問題を考えます。これは、楕円曲線離散対数問題と呼ばれます。

この問題に対する解法ですぐに思いつくのは、総当たり法です。

しかし、その1の\(p=5\)の場合など、点位数が小さい場合はいいですが、NEMのTechnical Referenceを見てみれば、

「曲線上の巡回群\(G\)に対応するベースポイントを\(B\)とします。この群は、\(q=2^{252}-27742317777372353535851937790883648493\)個の元を持ちます。」

とあります。CPUのクロック周波数は\(5GHz\)程度ですから、一秒に\(5\times10^{9}\)回命令を回せます。本当は命令と言うと語弊がありますが、ここでは無視しましょう。シングルコアを想定して、楕円曲線離散対数問題の正解が、\(d=2^{200}\)のところにあった場合を考えます。一年は\(3\times 10^7\)程度ですから、

\[{2^{200}}/{5\times 10^9}/{(3\times 10^7)}\simeq 10^{43}年\]

かかってしまいます。ベースポイントの位数を\(l\)とすれば、かかる時間は最悪の場合、最悪計算量\(O(l)\)(\(l\)に比例する程度の時間)になります。

(逆に今まで考えてきた掛け算の場合は、\(100\times P=(64+32+4)\times P\)のような計算ができますから、比較的簡単です。つまり、もとの問題の計算時間の\(log\)程度で抑えることができます。)

ちょっと現実的ではありません。もうちょっと簡単に暗号を打ち破る方法はないのでしょうか。

 

Baby-step Giant-step法

楕円曲線離散対数問題\(Q=d\times P\)に対し、ベースポイント\(P\)の位数\(l\)を用いて、\(m=[\sqrt{l}]\) ([]はガウス記号)とします。このとき、\(d=sm+t\)(\(s\)は\(d\)を\(m\)で割った商\(,t\)は\(d\)を\(m\)で割ったあまり)とします。

\(R=m\times P\)として、

\[Q=d\times P=(sm+t)\times P=s\times R+t\times P\]

となるから、\(s,t\)は以下を満たします。

\[Q-t\times P=s\times R\]

そこで、

\(\{Q-t\times P|t\in \mathbb{N},0\leq t\leq m-1\}\),

\(\{s\times R|s\in \mathbb{N},0\leq s\leq m-1\}\)

のデータベースをあらかじめ計算し、この中で互いに同じものがあれば、それは答えになります。

 

しかしこれでも、計算量は\(O(\sqrt{l})\)です。

ちなみに、\(y=log(x),y=x,y=\sqrt{x}\)のグラフはこんな感じです。

 

\(l\)がさらに大きいところだと、コイツらの差はアホみたいに大きくなります。それぐらい、計算量のオーダーは大事だと言うことです。

 

さらに、\(\rho\)法と言う、よりすぐれたアルゴリズムがあります。最近の、大きなサイズの離散対数問題を突破した手法に関しては、全てこの方法が用いられています。

楕円曲線離散対数問題\(Q=d\times P\)に対し、何らかの方法(実際にはランダム)で

\[s\times P+t\times Q=s^\prime \times P+t^\prime \times Q\]

となる、互いに異なる\(s,s^\prime,t,t^\prime\)が見つかったとします。

すると、

\[(t-t^\prime)\times Q=(s^\prime-s)\times P\]

よって、\(\frac{s^\prime-s}{t-t^\prime }\)(ベースポイント\(P\)の点位数\(l\)の\(mod(l)\)での除算)が答えになります。

\(i\)番目にランダムに選ばれた点を\(R_i=s_i\times P+t_i\times Q\)とすると、このような点同士をいかに早く見つけるかが問題です。この特別な点どうしを、コリジョンペアと言います。

ランダムな点を効率的に求めるためには、つぎの\(R\)として、以下の\(f(R)\)を用います。

\[f(R)=R+M_i(ここで、i=x(R)mod4)\]

ただし、\(M_0,M_1,M_2,M_3\)はあらかじめランダムにとった点であり、\(x(R)\)は\(R\)の\(x\)座標です。

 

この\(4\)という数字は、大規模な問題の場合はランダム性の向上のため\(20\)などの大きな数にします。

これは、線形合同法と言う基本的な乱数生成法で、C言語のrandは線形合同法を用いています。ちなみに、pythonはメルセンヌツイスタです。

 

この\(rho\)法を用いた攻撃は、誕生日攻撃と呼ばれます。

点の集合から2つの点をランダムに選んで試すのと、

クラスから2人同じ誕生日の人を選んでくるのが、同じ構造を持っているからです。

詳細は省きますが、誕生日攻撃において、\(50\%\)の確率で攻撃が成功する試行回数は\(O(\sqrt{N})\)であることが、それほど難しくない数理的解析から分かります。これはBaby-step Giant-step法と同じですが、ある方法を用いることで保存すべき情報が減らせるから、こちらの方が優れているとされています。

このように、暗号の生成(スカラー倍算)に比べ、楕円曲線離散対数問題を解くのにメチャクチャ時間がかかる(少なくとも、それよりいいアルゴリズムが見つかっていない)ため、楕円曲線暗号の安全性が保障されています。

ちなみに、量子計算機を用いた楕円曲線離散対数問題の効率的な解法はすでに知られているようで、これが最近ニュースでよく見る暗号の問題かと、やっと納得に至りました。