Index calculus algorithm - Revision history

OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-25T19:06:51Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 19:06, 25 May 2025
Line 87:		Line 87:
	\|doi=10.1007/978-3-662-43414-7_18		\|doi=10.1007/978-3-662-43414-7_18
	\|doi-access=free		\|doi-access=free
			\|url-access=subscription
	}}</ref> <math>L_{q}\left[1/4+\varepsilon,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.		}}</ref> <math>L_{q}\left[1/4+\varepsilon,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.

BD2412: clean up spacing around commas and other punctuation fixes, replaced: ,A → , A, ,c → , c (3), ,e → , e (3), ,k → , k

2024-01-15T04:38:50Z

clean up spacing around commas and other punctuation fixes, replaced: ,A → , A, ,c → , c (3), ,e → , e (3), ,k → , k

← Previous revision		Revision as of 04:38, 15 January 2024
Line 50:		Line 50:

	==History==		==History==
	The basic idea of the algorithm is due to Western and Miller (1968),<ref>Western and Miller (1968) ''Tables of indices and primitive roots'', Royal Society Mathematical Tables, vol 9, Cambridge University Press.</ref> which ultimately relies on ideas from Kraitchik (1922).<ref>M. Kraitchik, ''Théorie des nombres'', Gauthier--Villards, 1922</ref> The first practical implementations followed the 1976 introduction of the [[Diffie-Hellman]] cryptosystem which relies on the discrete logarithm. Merkle's Stanford University dissertation (1979) was credited by Pohlig (1977) and Hellman and Reyneri (1983), who also made improvements to the implementation.<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> [[Leonard Adleman\|Adleman]] optimized the algorithm and presented it in the present form.<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 basic idea of the algorithm is due to Western and Miller (1968),<ref>Western and Miller (1968) ''Tables of indices and primitive roots'', Royal Society Mathematical Tables, vol 9, Cambridge University Press.</ref> which ultimately relies on ideas from Kraitchik (1922).<ref>M. Kraitchik, ''Théorie des nombres'', Gauthier--Villards, 1922</ref> The first practical implementations followed the 1976 introduction of the [[Diffie-Hellman]] cryptosystem which relies on the discrete logarithm. Merkle's Stanford University dissertation (1979) was credited by Pohlig (1977) and Hellman and Reyneri (1983), who also made improvements to the implementation.<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> [[Leonard Adleman\|Adleman]] optimized the algorithm and presented it in the present form.<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==		==The Index Calculus family==

Trappist the monk: cite repair;

2023-09-24T15:41:15Z

cite repair;

← Previous revision		Revision as of 15:41, 24 September 2023
Line 11:		Line 11:
	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 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. 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<ref>Thorsten Kleinjung, Claus Diem, Arlen K. Lenstra, Christine Priplata, Colin Stahlke, [https://eprint.iacr.org/2017/067.pdf ~~“Computation~~ of a 768-bit prime field discrete ~~logarithm”~~], IACR sprint, 2017</ref><ref>Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome, [https://eprint.iacr.org/2016/961.pdf “A kilobit hidden snfs discrete logarithm ~~computation”~~], IACR spring, July 2016</ref> 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 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<ref>Thorsten Kleinjung, Claus Diem, Arlen K. Lenstra, Christine Priplata, Colin Stahlke, [https://eprint.iacr.org/2017/067.pdf "Computation of a 768-bit prime field discrete logarithm"], IACR sprint, 2017</ref><ref>Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome, [https://eprint.iacr.org/2016/961.pdf "A kilobit hidden snfs discrete logarithm computation"], IACR spring, July 2016</ref> 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<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>.		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>.
Line 92:		Line 92:
	*[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.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".		*[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=https://archive.org/details/handbookofapplie0000mene/page/107 \| publisher=[[CRC Press]] \| year=1997 \| pages=[https://archive.org/details/handbookofapplie0000mene/page/107 107–109] \| isbn=0-8493-8523-7 \| url-access=registration }}		*{{cite book \|author=A. Menezes \|author2=P. van Oorschot \|author3=S. Vanstone \| title=Handbook of Applied Cryptography \| url=https://archive.org/details/handbookofapplie0000mene/page/107 \| publisher=[[CRC Press]] \| year=1997 \| pages=[https://archive.org/details/handbookofapplie0000mene/page/107 107–109] \| isbn=0-8493-8523-7 \| url-access=registration }}

	==Notes==		==Notes==

JCW-CleanerBot: /* History */task, replaced: Advances in Cryptology- → Advances in Cryptology –

2023-07-05T04:14:57Z

History: task, replaced: Advances in Cryptology- → Advances in Cryptology –

← Previous revision		Revision as of 04:14, 5 July 2023
Line 50:		Line 50:

	==History==		==History==
	The basic idea of the algorithm is due to Western and Miller (1968),<ref>Western and Miller (1968) ''Tables of indices and primitive roots'', Royal Society Mathematical Tables, vol 9, Cambridge University Press.</ref> which ultimately relies on ideas from Kraitchik (1922).<ref>M. Kraitchik, ''Théorie des nombres'', Gauthier--Villards, 1922</ref> The first practical implementations followed the 1976 introduction of the [[Diffie-Hellman]] cryptosystem which relies on the discrete logarithm. Merkle's Stanford University dissertation (1979) was credited by Pohlig (1977) and Hellman and Reyneri (1983), who also made improvements to the implementation.<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> [[Leonard Adleman\|Adleman]] optimized the algorithm and presented it in the present form.<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 basic idea of the algorithm is due to Western and Miller (1968),<ref>Western and Miller (1968) ''Tables of indices and primitive roots'', Royal Society Mathematical Tables, vol 9, Cambridge University Press.</ref> which ultimately relies on ideas from Kraitchik (1922).<ref>M. Kraitchik, ''Théorie des nombres'', Gauthier--Villards, 1922</ref> The first practical implementations followed the 1976 introduction of the [[Diffie-Hellman]] cryptosystem which relies on the discrete logarithm. Merkle's Stanford University dissertation (1979) was credited by Pohlig (1977) and Hellman and Reyneri (1983), who also made improvements to the implementation.<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> [[Leonard Adleman\|Adleman]] optimized the algorithm and presented it in the present form.<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==		==The Index Calculus family==

Taylor Riastradh Campbell: /* The Index Calculus family */ Improve sourcing for cost estimates.

2023-04-04T06:06:21Z

The Index Calculus family: Improve sourcing for cost estimates.

@@ Line 54: / Line 54: @@
 ==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 display="inline"> 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 display="inline">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+\varepsilon,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.
+the Number Field Sieve for Discrete Logarithms, <math display="inline"> L_{q}\left[1/3,\sqrt[3]{64/9}\,\right]</math>, when <math> p </math> is large compared to <math>q</math>,<ref name="barbulescu2013thesis">{{cite thesis
 == External links ==

Dalet 38: /* The algorithm */

2023-02-08T11:43:12Z

The algorithm

Dalet 38: /* The algorithm */

2023-02-08T10:09:19Z

The algorithm

← Previous revision		Revision as of 10:09, 8 February 2023
Line 27:		Line 27:
	== The algorithm ==		== 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/>		'''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'').		'''Output:''' <math>x</math> such that ''g<sup>x</sup>'' ≡ ''h'' (mod ''q'').

	* relations ← empty_list		* relations ← empty_list

Dalet 38: /* The algorithm */

2023-02-08T10:08:35Z

The algorithm

← Previous revision		Revision as of 10:08, 8 February 2023
Line 36:		Line 36:
	*** If this relation is [[linearly independent]] to the other relations:		*** If this relation is [[linearly independent]] to the other relations:
	**** Add it to the list of relations		**** Add it to the list of relations
	**** If there are at least ~~<math>~~r~~<\math>~~ + 1 relations, exit loop		**** If there are at least ''r'' + 1 relations, exit loop
	* Form a matrix whose rows are the relations		* Form a matrix whose rows are the relations
	* Obtain the [[reduced echelon form]] of the matrix		* Obtain the [[reduced echelon form]] of the matrix

Dalet 38: /* The algorithm */

2023-02-08T10:08:07Z

The algorithm

← Previous revision		Revision as of 10:08, 8 February 2023
Line 30:		Line 30:

	* relations ← empty_list		* relations ← empty_list
	* for ''k'' = 1, 2, ~~...~~		* for <math>k = 1, 2, \ldots</math>
	** Using an [[integer factorization]] algorithm optimized for [[smooth numbers]], try to factor <math>g^k \bmod q</math> (Euclidean residue) using the factor base, i.e. find <math>e_i</math>'s such that <math>g^k \bmod q= (-1)^{e_0}2^{e_1}3^{e_2}\cdots p_r^{e_r}</math>		** Using an [[integer factorization]] algorithm optimized for [[smooth numbers]], try to factor <math>g^k \bmod q</math> (Euclidean residue) using the factor base, i.e. find <math>e_i</math>'s such that <math>g^k \bmod q= (-1)^{e_0}2^{e_1}3^{e_2}\cdots p_r^{e_r}</math>
	** Each time a factorization is found:		** Each time a factorization is found:
Line 36:		Line 36:
	*** If this relation is [[linearly independent]] to the other relations:		*** If this relation is [[linearly independent]] to the other relations:
	**** Add it to the list of relations		**** Add it to the list of relations
	**** If there are at least ''r'' + 1 relations, exit loop		**** If there are at least <math>r<\math> + 1 relations, exit loop
	* Form a matrix whose rows are the relations		* Form a matrix whose rows are the relations
	* Obtain the [[reduced echelon form]] of the matrix		* 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		** 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'' = 1, 2, ~~...~~		* for <math>s = 1, 2, \ldots</math>
	** Try to factor <math>g^s h \bmod q= (-1)^{f_0}2^{f_1}3^{f_2}\cdots p_r^{f_r}</math> over the factor base		** Try to factor <math>g^s h \bmod 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:		** When a factorization is found:

Sheep8144402: fix linter error (1x missing end tag)

2023-01-06T23:26:52Z

fix linter error (1x missing end tag)

← Previous revision		Revision as of 23:26, 6 January 2023
Line 50:		Line 50:

	==History==		==History==
	The basic idea of the algorithm is due to Western and Miller (1968),<ref>Western and Miller (1968) ''Tables of indices and primitive roots'', Royal Society Mathematical Tables, vol 9, Cambridge University Press.</ref> which ultimately relies on ideas from Kraitchik (1922).<ref>M. Kraitchik, ''Théorie des nombres'', Gauthier--Villards, 1922</ref> The first practical implementations followed the 1976 introduction of the [[Diffie-Hellman]] cryptosystem which relies on the discrete logarithm. Merkle's Stanford University dissertation (1979) was credited by Pohlig (1977) and Hellman and Reyneri (1983), who also made improvements to the implementation.<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> [[Leonard Adleman\|Adleman]] optimized the algorithm and presented it in the present form.<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 basic idea of the algorithm is due to Western and Miller (1968),<ref>Western and Miller (1968) ''Tables of indices and primitive roots'', Royal Society Mathematical Tables, vol 9, Cambridge University Press.</ref> which ultimately relies on ideas from Kraitchik (1922).<ref>M. Kraitchik, ''Théorie des nombres'', Gauthier--Villards, 1922</ref> The first practical implementations followed the 1976 introduction of the [[Diffie-Hellman]] cryptosystem which relies on the discrete logarithm. Merkle's Stanford University dissertation (1979) was credited by Pohlig (1977) and Hellman and Reyneri (1983), who also made improvements to the implementation.<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> [[Leonard Adleman\|Adleman]] optimized the algorithm and presented it in the present form.<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==		==The Index Calculus family==

← Previous revision		Revision as of 11:43, 8 February 2023
Line 26:		Line 26:

	== The algorithm ==		== 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/>		'''Input:''' Discrete logarithm generator <math>g</math>, modulus <math>q</math> and argument <math>h</math>. Factor base <math>\{-1, 2, 3, 5, 7, 11, \ldots, p_r\}</math>, of length <math>r+1</math>.<br/>
	'''Output:''' <math>x</math> such that ~~''g~~<~~sup~~>x~~</sup>'' ≡ ''~~h'' (mod ''q~~'')~~.		'''Output:''' <math>x</math> such that <math>g^x=h \mod q</math>.

	* relations ← empty_list		* relations ← empty_list
Line 33:		Line 33:
	** Using an [[integer factorization]] algorithm optimized for [[smooth numbers]], try to factor <math>g^k \bmod q</math> (Euclidean residue) using the factor base, i.e. find <math>e_i</math>'s such that <math>g^k \bmod q= (-1)^{e_0}2^{e_1}3^{e_2}\cdots p_r^{e_r}</math>		** Using an [[integer factorization]] algorithm optimized for [[smooth numbers]], try to factor <math>g^k \bmod q</math> (Euclidean residue) using the factor base, i.e. find <math>e_i</math>'s such that <math>g^k \bmod q= (-1)^{e_0}2^{e_1}3^{e_2}\cdots p_r^{e_r}</math>
	** Each time a factorization is found:		** 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)		*** Store <math>k</math> 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:		*** If this relation is [[linearly independent]] to the other relations:
	**** Add it to the list of relations		**** Add it to the list of relations
	**** If there are at least ''r~~'' ~~+~~ ~~1 relations, exit loop		**** If there are at least <math>r+1</math> relations, exit loop
	* Form a matrix whose rows are the relations		* Form a matrix whose rows are the relations
	* Obtain the [[reduced echelon form]] of the matrix		* 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		** The first element in the last column is the discrete log of <math>-1</math> and the second element is the discrete log of <math>2</math> and so on
	* for <math>s = 1, 2, \ldots</math>		* for <math>s = 1, 2, \ldots</math>
	** Try to factor <math>g^s h \bmod q= (-1)^{f_0}2^{f_1}3^{f_2}\cdots p_r^{f_r}</math> over the factor base		** Try to factor <math>g^s h \bmod q= (-1)^{f_0}2^{f_1}3^{f_2}\cdots p_r^{f_r}</math> over the factor base