Geodesic
On the asymptotic complexity of computing discrete logarithms in the field $\operatorname{\mathit{GF}}(p)$
Diskretnaya Matematika, Tome 15 (2003) no. 1, pp. 28-49
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We analyse the modification of an algorithm for finding discrete logarithms over the field $\mathit{GF}(p)$ ($p$ is a prime number) which has been described by the author previously. It is shown that this modification gives the best estimate at the present time of the complexity of finding discrete logarithms over finite prime fields which coincides with the best known estimate of the complexity of factoring integers obtained by D. Coppersmith. 
@article{DM_2003_15_1_a1,
     author = {D. V. Matyukhin},
     title = {On the asymptotic complexity of computing discrete logarithms in the field $\operatorname{\mathit{GF}}(p)$},
     journal = {Diskretnaya Matematika},
     pages = {28--49},
     year = {2003},
     volume = {15},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_1_a1/}
}
TY  - JOUR
AU  - D. V. Matyukhin
TI  - On the asymptotic complexity of computing discrete logarithms in the field $\operatorname{\mathit{GF}}(p)$
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 28
EP  - 49
VL  - 15
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_1_a1/
LA  - ru
ID  - DM_2003_15_1_a1
ER  - 
%0 Journal Article
%A D. V. Matyukhin
%T On the asymptotic complexity of computing discrete logarithms in the field $\operatorname{\mathit{GF}}(p)$
%J Diskretnaya Matematika
%D 2003
%P 28-49
%V 15
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2003_15_1_a1/
%G ru
%F DM_2003_15_1_a1
D. V. Matyukhin. On the asymptotic complexity of computing discrete logarithms in the field $\operatorname{\mathit{GF}}(p)$. Diskretnaya Matematika, Tome 15 (2003) no. 1, pp. 28-49. http://geodesic.mathdoc.fr/item/DM_2003_15_1_a1/

[1] Matyukhin D. V., Murashov N. N., “Modifikatsiya metoda resheta chislovogo polya dlya diskretnogo logarifmirovaniya v pole $GF(p)$”, Obozrenie prikladnoi i promyshlennoi matematiki, 7:2 (2000), 387–389

[2] Coppersmith D., “Modifications to the number field sieve”, J. Cryptology, 6 (1993), 169–180 | DOI | MR | Zbl

[3] Schirokauer O., “Discrete logarithms and local units”, Phil. Trans. Royal Soc. Lond., 345 (1993), 409–423 | DOI | MR | Zbl

[4] Cohen H., A course in computational algebraic number theory, Springer, New York, 1993 | MR

[5] Dedekind R., Gesammelte mathematische Werke, Bd. I, Braunschweig, 1930

[6] Gordon D., “Discrete logarithms in $GF(p)$ using the number field sieve”, SIAM J. Disc. Math., 6 (1993), 124–138 | DOI | MR | Zbl

[7] Lenstra H. W., “Factoring integers with elliptic curves”, Ann. Math., 126 (1987), 649–673 | DOI | MR | Zbl

[8] Cohen H., Lenstra H. W., “Heuristics on class groups of number fields”, Lect. Notes Math., 1068, 1984, 33–62 | MR | Zbl

[9] LaMacchia B., Odlyzko A. M., “Solving large sparse linear systems over finite fields”, Lect. Notes Computer Sci., 537, 1991, 109–133 | MR | Zbl

[10] Pohlig S., Hellman M., “An improved algorithm for computing logarithms over $GF(p)$ and its cryptographic significance”, IEEE Trans. Inform. Theory, 24 (1978), 106–110 | DOI | MR | Zbl

[11] Shoup V., “Searching for primitive roots in finite fields.”, Math. Comp., 58:197 (1992), 369–380 | DOI | MR | Zbl

[12] Lenstra A. K., Lenstra H. W., Lovász L., “Factoring polynomials with rational coefficients”, Math. Ann., 261 (1982), 515–534 | DOI | MR | Zbl