Index calculus algorithm

In computational number theory, the index calculus algorithm is a probabilisticalgorithm for computing discrete logarithms. Dedicated to the discrete logarithm in ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}}$ where ${\displaystyle q}$ is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.

Roughly speaking, the discrete log problem asks us to find an x such that ${\displaystyle g^{x}\equiv h{\pmod {n}}}$, where g, h, and the modulus n are given.

The algorithm (described in detail below) applies to the group ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}}$ where q is prime. It requires a factor base as input. This factor base is usually chosen to be the number −1 and the first r primes starting with 2. From the point of view of efficiency, we want this factor base to be small, but in order to solve the discrete log for a large group we require the factor base to be (relatively) large. In practical implementations of the algorithm, those conflicting objectives are compromised one way or another.

The algorithm is performed in three stages. The first two stages depend only on the generator g and prime modulus q, and find the discrete logarithms of a factor base of r small primes. The third stage finds the discrete log of the desired number h in terms of the discrete logs of the factor base.

The first stage consists of searching for a set of rlinearly independentrelations between the factor base and power of the generatorg. Each relation contributes one equation to a system of linear equations in r unknowns, namely the discrete logarithms of the r primes in the factor base. This stage is embarrassingly parallel and easy to divide among many computers.

The second stage solves the system of linear equations to compute the discrete logs of the factor base. A system of hundreds of thousands or millions of equations is a significant computation requiring large amounts of memory, and it is not embarrassingly parallel, so a supercomputer is typically used. This was considered a minor step compared to the others for smaller discrete log computations. However, larger discrete logarithm records^[1][2] were made possible only by shifting the work away from the linear algebra and onto the sieve (i.e., increasing the number of equations while reducing the number of variables).

The third stage searches for a power s of the generator g which, when multiplied by the argument h, may be factored in terms of the factor base g^sh = (−1)^f₀ 2^f₁ 3^f₂···p_r^f_r.

Finally, in an operation too simple to really be called a fourth stage, the results of the second and third stages can be rearranged by simple algebraic manipulation to work out the desired discrete logarithm x = f₀log_g(−1) + f₁log_g2 + f₂log_g3 + ··· + f_rlog_gp_r − s.

The first and third stages are both embarrassingly parallel, and in fact the third stage does not depend on the results of the first two stages, so it may be done in parallel with them.

The choice of the factor base size r is critical, and the details are too intricate to explain here. The larger the factor base, the easier it is to find relations in stage 1, and the easier it is to complete stage 3, but the more relations you need before you can proceed to stage 2, and the more difficult stage 2 is. The relative availability of computers suitable for the different types of computation required for stages 1 and 2 is also important.

入力:離散対数発生器${\displaystyle g}$、モジュラス${\displaystyle q}$そして議論${\displaystyle h}$要素ベース${\displaystyle \{-1,2,3,5,7,11,\ldots ,p_{r}\}}$長さ${\displaystyle r+1}$出力: ${\displaystyle x}$そのため${\displaystyle g^{x}=h\mod q}$。

• 関係 ← 空のリスト
• のために${\displaystyle k=1,2,\ldots }$
  • 滑らかな数に最適化された整数因数分解アルゴリズムを使用して、因数分解を試みます。${\displaystyle g^{k}{\bmod {q}}}$（ユークリッド剰余）因数基底を用いて、すなわち、${\displaystyle e_{i}}$は、${\displaystyle g^{k}{\bmod {q}}=(-1)^{e_{0}}2^{e_{1}}3^{e_{2}}\cdots p_{r}^{e_{r}}}$
  • 因数分解が見つかるたびに：
    • 店${\displaystyle k}$そして計算された${\displaystyle e_{i}}$'sをベクトルとして${\displaystyle (e_{0},e_{1},e_{2},\ldots ,e_{r},k)}$（これは関係と呼ばれます）
    • この関係が他の関係と 線形独立である場合：
      • 関係リストに追加する
      • 少なくとも${\displaystyle r+1}$関係、ループ終了
• 関係を行とする行列を作成する
• 行列の 簡約階段形を取得する
  • 最後の列の最初の要素は、離散対数です。${\displaystyle -1}$そして2番目の要素は離散対数です${\displaystyle 2}$等々
• のために${\displaystyle s=1,2,\ldots }$
  • 因数分解を試みる${\displaystyle g^{s}h{\bmod {q}}=(-1)^{f_{0}}2^{f_{1}}3^{f_{2}}\cdots p_{r}^{f_{r}}}$要素ベースを超えて
  • 因数分解が見つかった場合：
    • 出力${\displaystyle x=f_{0}\log _{g}(-1)+f_{1}\log _{g}2+\cdots +f_{r}\log _{g}p_{r}-s.}$

因子基底の最適な選択を仮定すると、インデックス計算アルゴリズムの 期待実行時間（L記法を使用）は次のように表すことができます。${\displaystyle L_{n}[1/2,{\sqrt {2}}+o(1)]}$。

アルゴリズムの基本アイデアは Western と Miller (1968) ^{[ 4 ]}によるもので、これは最終的には Kraitchik (1922) のアイデアに基づいています。^{[ 5 ]} 最初の実用的な実装は、離散対数に基づくDiffie-Hellman暗号システムの 1976 年の導入に続きました。Merkle のスタンフォード大学の博士論文 (1979 年) は Pohlig (1977 年) と Hellman と Reyneri (1983 年) によって評価され、彼らは実装の改良も行いました。^{[ 6 ] [ 7 ]} Adleman はアルゴリズムを最適化し、現在の形で発表しました。^{[ 8 ]}

指数計算は、多くのアルゴリズムを生み出した。有限体では$\displaystyle \mathbb {F} _{q}}$と$q=p^n$一部のプライム${\displaystyle p}$最先端のアルゴリズムは離散対数に対する数体篩法であり、${\textstyle L_{q}\left[1/3,{\sqrt[{3}]{64/9}}\,\right]}$、 いつ${\displaystyle p}$に比べて大きい${\displaystyle q}$[ ^{9 ]}関数^{フィールド}篩、${\textstyle L_{q}\left[1/3,{\sqrt[{3}]{32/9}}\,\right]}$[ ^{9 ]}およびJoux ^{、[ 10 ]}${\displaystyle L_{q}\left[1/4+\varepsilon ,c\right]}$のために${\displaystyle c>0}$、 いつ${\displaystyle p}$に比べて小さい${\displaystyle q}$そして高次の数体篩、${\displaystyle L_{q}[1/3,c]}$のために${\displaystyle c>0}$いつ${\displaystyle p}$中辺です。楕円曲線のいくつかの族における離散対数は時間で解くことができます${\displaystyle L_{q}\left[1/3,c\right]}$のために${\displaystyle c>0}$しかし、一般的には指数関数的な増加が見られる。

• 有限体における離散対数とその暗号学的意義、アンドリュー・オドリツコ著
• クリス・スタッドホルム著『離散対数問題』、2002年6月21日発表の論文「離散対数問題」を含む。
• A. メネゼス、P. ファン・オールショット、S. ヴァンストーン (1997) 『応用暗号ハンドブック』CRC Press、pp. 107–109、ISBN  0-8493-8523-7。