| Title:
|
Approximation of the discrete logarithm in finite fields of even characteristic by real polynomials (English) |
| Author:
|
Brandstätter, Nina |
| Author:
|
Winterhof, Arne |
| Language:
|
English |
| Journal:
|
Archivum Mathematicum |
| ISSN:
|
0044-8753 (print) |
| ISSN:
|
1212-5059 (online) |
| Volume:
|
42 |
| Issue:
|
1 |
| Year:
|
2006 |
| Pages:
|
43-50 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
Discrete logarithm |
| Keyword:
|
polynomial approximation |
| Keyword:
|
character sums |
| MSC:
|
11T24 |
| MSC:
|
11T71 |
| MSC:
|
94A60 |
| idZBL:
|
Zbl 1164.11073 |
| idMR:
|
MR2227111 |
| . |
| Date available:
|
2008-06-06T22:47:09Z |
| Last updated:
|
2012-05-10 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/107980 |
| . |
| Reference:
|
[1] Cochrane T.: On a trigonometric inequality of Vinogradov.J. Number Theory 27 (1987), 9–16. Zbl 0629.10030, MR 0904002 |
| Reference:
|
[2] Coppersmith D., Shparlinski I.: On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping.J. Cryptology 13 (2000), 339–360. Zbl 1038.94007, MR 1768482 |
| Reference:
|
[3] Ding C., Helleseth T.: On cyclotomic generator of order $r$.Inform. Process. Lett. 66 (1998), 21–25. Zbl 1078.94511, MR 1626061 |
| Reference:
|
[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. Zbl 1092.94024, MR 2194405 |
| Reference:
|
[5] Konyagin S., Lange T., Shparlinski I.: Linear complexity of the discrete logarithm.Des. Codes Cryptogr. 28 (2003), 135–146. Zbl 1024.11078, MR 1962801 |
| Reference:
|
[6] Lange T., Winterhof A.: Polynomial interpolation of the elliptic curve and XTR discrete logarithm.Lecture Notes in Comput. Sci. 2387 (2002), 137–143. Zbl 1077.94518, MR 2064510 |
| Reference:
|
[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. Zbl 0998.11070, MR 1875841 |
| Reference:
|
[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 1991426 |
| Reference:
|
[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. Zbl 1032.94004, MR 1872841 |
| Reference:
|
[10] Meletiou G. C.: Explicit form for the discrete logarithm over the field ${\text GF}(p,k)$.Arch. Math. (Brno) 29 (1993), 25–28. Zbl 0818.11049, MR 1242625 |
| Reference:
|
[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 1491193 |
| Reference:
|
[12] Meletiou G. C., Mullen G. L.: A note on discrete logarithms in finite fields.Appl. Algebra Engrg. Comm. Comput. 3 (1992), 75–78. Zbl 0749.11055, MR 1325748 |
| Reference:
|
[13] Menezes A. J., van Oorschot P. C., Vanstone S. A. : Handbook of applied cryptography.CRC Press, Boca Raton, FL 1997. Zbl 0868.94001, MR 1412797 |
| Reference:
|
[14] Mullen G. L., White D.: A polynomial representation for logarithms in ${\text GF}(q)$.Acta Arith. 47 (1986), 255–261. MR 0870668 |
| Reference:
|
[15] Niederreiter H.: A short proof for explicit formulas for discrete logarithms in finite fields.Appl. Algebra Engrg. Comm. Comput. 1 (1990), 55–57. Zbl 0726.11079, MR 1325511 |
| Reference:
|
[16] Niederreiter H., Winterhof A.: Incomplete character sums and polynomial interpolation of the discrete logarithm.Finite Fields Appl. 8 (2002), 184–192. MR 1894512 |
| Reference:
|
[17] Risler J.-J.: Khovansky’s theorem and complexity theory.Rocky Mountain J. Math. 14 (1984), 851–853. MR 0773123 |
| Reference:
|
[18] Risler J.-J.: Additive complexity of real polynomials.SIAM J. Comp. 14 (1985), 178–183. MR 0774937 |
| Reference:
|
[19] Rojas J. M.: Additive complexity and p-adic roots of polynomials.Lecture Notes in Comput. Sci. 2369 (2002), 506–516. MR 2041107 |
| Reference:
|
[20] Rojas J. M.: Arithmetic multivariate Descartes’ rule.Amer. J. Math. 126 (2004), 1–30. Zbl 1046.12001, MR 2033562 |
| Reference:
|
[21] Shparlinski I.: Number theoretic methods in cryptography. Complexity lower bounds.Birkhäuser, Basel 1999. Zbl 0912.11057, MR 1707287 |
| Reference:
|
[22] Shparlinski I.: Cryptographic applications of analytic number theory. Complexity lower bounds and pseudorandomness.Birkhäuser, Basel 2003. MR 1954519 |
| Reference:
|
[23] Winterhof A.: Some estimates for character sums and applications.Des. Codes Cryptogr. 22 (2001), 123–131. Zbl 0995.11067, MR 1813781 |
| Reference:
|
[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. Zbl 1019.11034, MR 1849268 |
| Reference:
|
[25] Winterhof A.: Polynomial interpolation of the discrete logarithm.Des. Codes Cryptogr. 25 (2002), 63–72. Zbl 1017.11065, MR 1881340 |
| Reference:
|
[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. Zbl 1063.11052, MR 2090662 |
| . |
