|
|
| Line 1: |
Line 1: |
| In [[computational number theory]], the '''index calculus algorithm''' is a [[probabilistic]] [[algorithm]] for computing [[discrete logarithm]]s.
| | Not much to say about me really.<br>Enjoying to be a part of wmflabs.org.<br>I just wish I am useful at all<br><br>My homepage: [http://tsis.ac.th/i/?attachment_id=367 fifa 15 coin Hack] |
| Dedicated to the discrete logarithm in <math>(\mathbb{Z}/q\mathbb{Z})^*</math> where <math>q</math> is a prime, Index calculus lead 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.
| |
| | |
| == Description ==
| |
| Roughly speaking, the [[Discrete logarithm|discrete log]] problem asks us to find an ''x'' such that <math>g^x \equiv h \pmod{n}</math>, where ''g'', ''h'', and the modulus ''n'' are given.
| |
| | |
| The algorithm (described in detail below) applies to the group <math>(\mathbb{Z}/q\mathbb{Z})^*</math> 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 ''r'' [[linearly independent]] ''relations'' between the factor base and power of the [[Generating set of a group|generator]] ''g''. 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. Although a minor computation compared to the other stages, 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.
| |
| | |
| 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<sup>s</sup>h'' = (−1)<sup>''f''<sub>0</sub></sup> 2<sup>''f''<sub>1</sub></sup> 3<sup>''f''<sub>2</sub></sup>···''p''<sub>''r''</sub><sup>''f''<sub>''r''</sub></sup>.
| |
| | |
| 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''<sub>0</sub>log<sub>''g''</sub>(−1) + ''f''<sub>1</sub>log<sub>''g''</sub>2 + ''f''<sub>2</sub>log<sub>''g''</sub>3 + ··· + ''f''<sub>''r''</sub>log<sub>''g''</sub>''p<sub>r</sub>'' − ''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.
| |
| | |
| === Applications in other groups ===
| |
| | |
| It is noteworthy that the lack of the notion of ''prime elements'' in the group of points on [[elliptic curves]], makes it impossible to find an efficient ''factor base'' to run index calculus method as presented here in these groups. Therefore this algorithm is incapable of solving discrete logarithms efficiently in elliptic curve groups. However: For special kinds of curves (so called [[supersingular elliptic curve]]s) there are specialized algorithms for solving the problem faster than with generic methods. While the use of these special curves can easily be avoided, in 2009 it has been proven that for certain fields the discrete logarithm problem in the group of points on ''general'' elliptic curves over these fields can be solved faster than with generic methods. The algorithms are indeed adaptations of the index calculus method.<ref>{{cite journal|last=Diem|first=C|title=On the discrete logarithm problem in elliptic curves|journal=Compositio Mathematica|year=2010}}</ref>
| |
| | |
| == The algorithm ==
| |
| '''Input:''' Discrete logarithm generator ''g'', modulus ''q'' and argument ''h''. Factor base {−1,2,3,5,7,11,...,''p<sub>r</sub>''}, of length ''r''+1.<br/>
| |
| '''Output:''' ''x'' such that ''g<sup>x</sup>'' ≡ ''h'' (mod ''q'').
| |
| | |
| * relations ← empty_list
| |
| * for ''k'' = 1, 2, ...
| |
| ** Using an [[integer factorization]] algorithm optimized for [[smooth numbers]], try to factor <math>g^k \mod q</math> (Euclidian residue) using the factor base, i.e. find <math>e_i</math>'s such that <math>g^k \mod q= (-1)^{e_0}2^{e_1}3^{e_2}\cdots p_r^{e_r}</math>
| |
| ** Each time a factorization is found:
| |
| *** Store ''k'' and the computed <math>e_i</math>'s as a vector <math>(e_0,e_1,e_2,\ldots,e_r,k)</math> (this is a called a relation)
| |
| *** If this relation is [[linearly independent]] to the other relations:
| |
| **** Add it to the list of relations
| |
| **** If there are at least ''r''+1 relations, exit loop
| |
| * Form a matrix whose rows are the relations
| |
| * Obtain the [[reduced echelon form]] of the matrix
| |
| ** The first element in the last column is the discrete log of −1 and the second element is the discrete log of 2 and so on
| |
| * for ''s'' = 0, 1, 2, ...
| |
| ** Try to factor <math>g^s h \mod q= (-1)^{f_0}2^{f_1}3^{f_2}\cdots p_r^{f_r}</math> over the factor base
| |
| ** When a factorization is found:
| |
| *** Output <math>x = f_0 \log_g(-1) + f_1 \log_g2 + \cdots + f_r \log_g p_r - s.</math>
| |
| | |
| == Complexity ==
| |
| Assuming an optimal selection of the factor base, the expected running time (using [[L-notation]]) of the index-calculus algorithm can be stated as
| |
| <math>L_n[1/2,\sqrt{2}+o(1)] </math>.
| |
| | |
| ==History==
| |
| The first to discover the idea was Kraitchik in 1922.<ref>M. Kraitchik, ''Théorie des nombres'', Gauthier--Villards, 1922</ref> After [[Discrete logarithm|DLP]] became important in 1976 with the creation of the [[Diffie-Hellman]] cryptosystem, R. Merkle from Stanford University rediscovered the idea in 1977. The first publications came in the next two years from Merkle's colleagues.<ref>Pohlig, S. ''Algebraic and combinatoric aspects of cryptography''.
| |
| Tech. Rep. No. 6602-1, Stanford Electron. Labs., Stanford, Calif., Oct. 1977.</ref><ref>M.E. Hellman and J.M. Reyneri, ''Fast computation of discrete logarithms in GF
| |
| (q),Advances in Cryptology--Proceedings of Crypto, 1983</ref> Finally, [[Leonard Adleman|Adleman]] optimized the algorithm and presented it in the form we know it today.<ref>L. Adleman, ''A subexponential algorithm for the discrete logarithm problem with applications to cryptography'', In 20th Annual Symposium on Foundations of Computer Science, 1979</ref>
| |
| | |
| | |
| ==The Index Calculus family==
| |
| Index Calculus inspired a large family of algorithms. In finite fields <math>\mathbb{F}_{q} </math> with <math>q=p^n</math> for some prime <math>p</math>, the state-of-art algorithms are
| |
| the Number Field Sieve for Discrete Logarithms, <math> L_{q}\left[1/3,\sqrt[3]{64/9}\right]</math>, when <math> p </math> is large compared to <math>q</math>, the [[function field sieve]], <math>L_{q}\left[1/3,\sqrt[3]{32/9}\right]</math>, and Joux,<ref> A. Joux, ''A new index calculus algorithm with complexity'' <math>L(1/4+o(1))</math> ''in very small characteristic'' [http://eprint.iacr.org/2013/095]</ref> <math>L_{q}\left[1/4+\epsilon,c\right] </math> for <math>c>0</math>, when <math>p</math> is small compared to <math>q </math> and the Number Field Sieve in High Degree, <math>L_q[1/3,c]</math> for <math>c>0</math> when <math>p </math> is middle-sided. Discrete logarithm in some families of elliptic curves can be solved in time <math>L_q\left[1/3,c\right]</math> for <math> c>0</math>, but the general case remains exponential.
| |
| | |
| == External links ==
| |
| *[http://www.dtc.umn.edu/~odlyzko/doc/arch/discrete.logs.pdf Discrete logarithms in finite fields and their cryptographic significance], by [[Andrew Odlyzko]]
| |
| *[http://www.cs.toronto.edu/~cvs/dlog/ Discrete Logarithm Problem], by Chris Studholme, including the June 21, 2002 paper "The Discrete Log Problem".
| |
| *{{cite book | authors=A. Menezes, P. van Oorschot, S. Vanstone | title=Handbook of Applied Cryptography | url=http://www.cacr.math.uwaterloo.ca/hac/ | publisher=[[CRC Press]] | year=1997 | pages=107–109 | isbn=0-8493-8523-7}}
| |
| | |
| | |
| | |
| ==Notes==
| |
| {{Reflist}}
| |
| | |
| {{Number-theoretic algorithms}}
| |
| | |
| {{DEFAULTSORT:Index Calculus Algorithm}}
| |
| [[Category:Group theory]]
| |