# Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials

Nina Brandstätter; Arne Winterhof

Archivum Mathematicum (2006)

- Volume: 042, Issue: 1, page 43-50
- ISSN: 0044-8753

## Access Full Article

top## Abstract

top## How to cite

topBrandstätter, Nina, and Winterhof, Arne. "Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials." Archivum Mathematicum 042.1 (2006): 43-50. <http://eudml.org/doc/249775>.

@article{Brandstätter2006,

abstract = {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.},

author = {Brandstätter, Nina, Winterhof, Arne},

journal = {Archivum Mathematicum},

keywords = {Discrete logarithm; polynomial approximation; character sums; discrete logarithm; polynomial approximation; character sums},

language = {eng},

number = {1},

pages = {43-50},

publisher = {Department of Mathematics, Faculty of Science of Masaryk University, Brno},

title = {Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials},

url = {http://eudml.org/doc/249775},

volume = {042},

year = {2006},

}

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

PB - Department of Mathematics, Faculty of Science of Masaryk University, Brno

VL - 042

IS - 1

SP - 43

EP - 50

AB - 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.

LA - eng

KW - Discrete logarithm; polynomial approximation; character sums; discrete logarithm; polynomial approximation; character sums

UR - http://eudml.org/doc/249775

ER -

## References

top- Cochrane T., On a trigonometric inequality of Vinogradov, J. Number Theory 27 (1987), 9–16. (1987) Zbl0629.10030MR0904002
- Coppersmith D., Shparlinski I., On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping, J. Cryptology 13 (2000), 339–360. Zbl1038.94007MR1768482
- Ding C., Helleseth T., On cyclotomic generator of order $r$, Inform. Process. Lett. 66 (1998), 21–25. (1998) Zbl1078.94511MR1626061
- Kiltz E., Winterhof A., Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem, Discrete Appl. Math. 154 (2006), 326–336. Zbl1092.94024MR2194405
- Konyagin S., Lange T., Shparlinski I., Linear complexity of the discrete logarithm, Des. Codes Cryptogr. 28 (2003), 135–146. Zbl1024.11078MR1962801
- Lange T., Winterhof A., Polynomial interpolation of the elliptic curve and XTR discrete logarithm, Lecture Notes in Comput. Sci. 2387 (2002), 137–143. Zbl1077.94518MR2064510
- 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. Zbl0998.11070MR1875841
- 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. MR1991426
- 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. Zbl1032.94004MR1872841
- Meletiou G. C., Explicit form for the discrete logarithm over the field $\text{G}F(p,k)$, Arch. Math. (Brno) 29 (1993), 25–28. (1993) Zbl0818.11049MR1242625
- Meletiou G. C., Explicit form for the discrete logarithm over the field $\text{G}F(p,k)$, Bul. Inst. Politeh. Iaşi. Secţ. I. Mat. Mec. Teor. Fiz. 41(45) (1995), 1–4. (1995) MR1491193
- Meletiou G. C., Mullen G. L., A note on discrete logarithms in finite fields, Appl. Algebra Engrg. Comm. Comput. 3 (1992), 75–78. (1992) Zbl0749.11055MR1325748
- Menezes A. J., van Oorschot P. C., Vanstone S. A., Handbook of applied cryptography, CRC Press, Boca Raton, FL 1997. (1997) Zbl0868.94001MR1412797
- Mullen G. L., White D., A polynomial representation for logarithms in $\text{G}F\left(q\right)$, Acta Arith. 47 (1986), 255–261. (1986) MR0870668
- Niederreiter H., A short proof for explicit formulas for discrete logarithms in finite fields, Appl. Algebra Engrg. Comm. Comput. 1 (1990), 55–57. (1990) Zbl0726.11079MR1325511
- Niederreiter H., Winterhof A., Incomplete character sums and polynomial interpolation of the discrete logarithm, Finite Fields Appl. 8 (2002), 184–192. (192.) MR1894512
- Risler J.-J., Khovansky’s theorem and complexity theory, Rocky Mountain J. Math. 14 (1984), 851–853. (1984) MR0773123
- Risler J.-J., Additive complexity of real polynomials, SIAM J. Comp. 14 (1985), 178–183. (1985) MR0774937
- Rojas J. M., Additive complexity and p-adic roots of polynomials, Lecture Notes in Comput. Sci. 2369 (2002), 506–516. MR2041107
- Rojas J. M., Arithmetic multivariate Descartes’ rule, Amer. J. Math. 126 (2004), 1–30. Zbl1046.12001MR2033562
- Shparlinski I., Number theoretic methods in cryptography. Complexity lower bounds, Birkhäuser, Basel 1999. (1999) Zbl0912.11057MR1707287
- Shparlinski I., Cryptographic applications of analytic number theory. Complexity lower bounds and pseudorandomness, Birkhäuser, Basel 2003. MR1954519
- Winterhof A., Some estimates for character sums and applications, Des. Codes Cryptogr. 22 (2001), 123–131. Zbl0995.11067MR1813781
- Winterhof A., Incomplete additive character sums and applications, In: Jungnickel, D. and Niederreiter, H. (eds.): Finite fields and applications, 462–474, Springer, Heidelberg 2001. Zbl1019.11034MR1849268
- Winterhof A., Polynomial interpolation of the discrete logarithm, Des. Codes Cryptogr. 25 (2002), 63–72. Zbl1017.11065MR1881340
- 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. Zbl1063.11052MR2090662

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.