Geodesic
Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials
Archivum mathematicum, Tome 42 (2006) no. 1, pp. 43-50 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 11T24, 11T71, 94A60
Keywords: Discrete logarithm; polynomial approximation; character sums 
@article{ARM_2006_42_1_a4,
     author = {Brandst\"atter, Nina and Winterhof, Arne},
     title = {Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials},
     journal = {Archivum mathematicum},
     pages = {43--50},
     year = {2006},
     volume = {42},
     number = {1},
     mrnumber = {2227111},
     zbl = {1164.11073},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ARM_2006_42_1_a4/}
}
TY  - JOUR
AU  - Brandstätter, Nina
AU  - Winterhof, Arne
TI  - Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials
JO  - Archivum mathematicum
PY  - 2006
SP  - 43
EP  - 50
VL  - 42
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/ARM_2006_42_1_a4/
LA  - en
ID  - ARM_2006_42_1_a4
ER  - 
%0 Journal Article
%A Brandstätter, Nina
%A Winterhof, Arne
%T Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials
%J Archivum mathematicum
%D 2006
%P 43-50
%V 42
%N 1
%U http://geodesic.mathdoc.fr/item/ARM_2006_42_1_a4/
%G en
%F ARM_2006_42_1_a4
Brandstätter, Nina; Winterhof, Arne. Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials. Archivum mathematicum, Tome 42 (2006) no. 1, pp. 43-50. http://geodesic.mathdoc.fr/item/ARM_2006_42_1_a4/

[1] Cochrane T.: On a trigonometric inequality of Vinogradov. J. Number Theory 27 (1987), 9–16. | MR | Zbl

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

[3] Ding C., Helleseth T.: On cyclotomic generator of order $r$. Inform. Process. Lett. 66 (1998), 21–25. | MR | Zbl

[4] 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 | Zbl

[5] Konyagin S., Lange T., Shparlinski I.: Linear complexity of the discrete logarithm. Des. Codes Cryptogr. 28 (2003), 135–146. | MR | Zbl

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

[7] 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 | Zbl

[8] 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

[9] 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 | Zbl

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

[11] 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. | MR

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

[13] Menezes A. J., van Oorschot P. C., Vanstone S. A. : Handbook of applied cryptography. CRC Press, Boca Raton, FL 1997. | MR | Zbl

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

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

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

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

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

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

[20] Rojas J. M.: Arithmetic multivariate Descartes’ rule. Amer. J. Math. 126 (2004), 1–30. | MR | Zbl

[21] Shparlinski I.: Number theoretic methods in cryptography. Complexity lower bounds. Birkhäuser, Basel 1999. | MR | Zbl

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

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

[24] 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 | Zbl

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

[26] 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 | Zbl