Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials
Brandstätter, Nina ; Winterhof, Arne
Archivum Mathematicum, Tome 042 (2006), p. 43-50 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

We obtain lower bounds on degree and additive complexity of real polynomials approximating the discrete logarithm in finite fields of even characteristic. These bounds complement earlier results for finite fields of odd characteristic.

Publié le : 2006-01-01
Classification:  11T24,  11T71,  94A60 
@article{107980,
     author = {Nina Brandst\"atter and Arne Winterhof},
     title = {Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials},
     journal = {Archivum Mathematicum},
     volume = {042},
     year = {2006},
     pages = {43-50},
     zbl = {1164.11073},
     mrnumber = {2227111},
     language = {en},
     url = {http://dml.mathdoc.fr/item/107980}
}

Brandstätter, Nina; Winterhof, Arne. Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials. Archivum Mathematicum, Tome 042 (2006) pp. 43-50. http://gdmltest.u-ga.fr/item/107980/

Cochrane T. On a trigonometric inequality of Vinogradov, J. Number Theory 27 (1987), 9–16. (1987) | MR 0904002 | Zbl 0629.10030

Coppersmith D.; Shparlinski I. On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping, J. Cryptology 13 (2000), 339–360. | MR 1768482 | Zbl 1038.94007

Ding C.; Helleseth T. On cyclotomic generator of order $r$, Inform. Process. Lett. 66 (1998), 21–25. (1998) | MR 1626061 | Zbl 1078.94511

Kiltz E.; Winterhof A. Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem, Discrete Appl. Math. 154 (2006), 326–336. | MR 2194405 | Zbl 1092.94024

Konyagin S.; Lange T.; Shparlinski I. Linear complexity of the discrete logarithm, Des. Codes Cryptogr. 28 (2003), 135–146. | MR 1962801 | Zbl 1024.11078

Lange T.; Winterhof A. Polynomial interpolation of the elliptic curve and XTR discrete logarithm, Lecture Notes in Comput. Sci. 2387 (2002), 137–143. | MR 2064510 | Zbl 1077.94518

Lange T.; Winterhof A. Incomplete character sums over finite fields and their application to the interpolation of the discrete logarithm by Boolean functions, Acta Arith. 101 (2002), 223–229. | MR 1875841 | Zbl 0998.11070

Lange T.; Winterhof A. Interpolation of the discrete logarithm in $F_q$ by Boolean functions and by polynomials in several variables modulo a divisor of $q-1$, Discrete Appl. Math. 128 (2003), 193–206. | MR 1991426

Meidl W.; Winterhof A. Lower bounds on the linear complexity of the discrete logarithm in finite fields, IEEE Trans. Inform. Theory 47 (2001), 2807–2811. | MR 1872841 | Zbl 1032.94004

Meletiou G. C. Explicit form for the discrete logarithm over the field ${\text GF}(p,k)$, Arch. Math. (Brno) 29 (1993), 25–28. (1993) | MR 1242625 | Zbl 0818.11049

Meletiou G. C. Explicit form for the discrete logarithm over the field ${\text GF}(p,k)$, Bul. Inst. Politeh. Iaşi. Secţ. I. Mat. Mec. Teor. Fiz. 41(45) (1995), 1–4. (1995) | MR 1491193

Meletiou G. C.; Mullen G. L. A note on discrete logarithms in finite fields, Appl. Algebra Engrg. Comm. Comput. 3 (1992), 75–78. (1992) | MR 1325748 | Zbl 0749.11055

Menezes A. J.; Van Oorschot P. C.; Vanstone S. A. Handbook of applied cryptography, CRC Press, Boca Raton, FL 1997. (1997) | MR 1412797 | Zbl 0868.94001

Mullen G. L.; White D. A polynomial representation for logarithms in ${\text GF}(q)$, Acta Arith. 47 (1986), 255–261. (1986) | MR 0870668

Niederreiter H. A short proof for explicit formulas for discrete logarithms in finite fields, Appl. Algebra Engrg. Comm. Comput. 1 (1990), 55–57. (1990) | MR 1325511 | Zbl 0726.11079

Niederreiter H.; Winterhof A. Incomplete character sums and polynomial interpolation of the discrete logarithm, Finite Fields Appl. 8 (2002), 184–192. (192.) | MR 1894512

Risler J.-J. Khovansky’s theorem and complexity theory, Rocky Mountain J. Math. 14 (1984), 851–853. (1984) | MR 0773123

Risler J.-J. Additive complexity of real polynomials, SIAM J. Comp. 14 (1985), 178–183. (1985) | MR 0774937

Rojas J. M. Additive complexity and p-adic roots of polynomials, Lecture Notes in Comput. Sci. 2369 (2002), 506–516. | MR 2041107

Rojas J. M. Arithmetic multivariate Descartes’ rule, Amer. J. Math. 126 (2004), 1–30. | MR 2033562 | Zbl 1046.12001

Shparlinski I. Number theoretic methods in cryptography. Complexity lower bounds, Birkhäuser, Basel 1999. (1999) | MR 1707287 | Zbl 0912.11057

Shparlinski I. Cryptographic applications of analytic number theory. Complexity lower bounds and pseudorandomness, Birkhäuser, Basel 2003. | MR 1954519

Winterhof A. Some estimates for character sums and applications, Des. Codes Cryptogr. 22 (2001), 123–131. | MR 1813781 | Zbl 0995.11067

Winterhof A. Incomplete additive character sums and applications, In: Jungnickel, D. and Niederreiter, H. (eds.): Finite fields and applications, 462–474, Springer, Heidelberg 2001. | MR 1849268 | Zbl 1019.11034

Winterhof A. Polynomial interpolation of the discrete logarithm, Des. Codes Cryptogr. 25 (2002), 63–72. | MR 1881340 | Zbl 1017.11065

Winterhof A. A note on the linear complexity profile of the discrete logarithm in finite fields, Progress Comp. Sci. Appl. Logic 23 (2004), 359–367. | MR 2090662 | Zbl 1063.11052