Linear complexity of the discrete logarithm

DOI10.1023/A:1022584306676MaRDI QIDQ1869823zbMATH OpenFDO

Authors Tanja Lange, Igor E. Shparlinski, Sergei Konyagin

Publication date 28 April 2003

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/A:1022584306676

zbMATH Keywords

discrete logarithmlinear complexitylinear recurrence sequences

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Review text

The authors prove several lower bounds on the linear complexity of finite sequences consisting of consecutive values of the discrete logarithm modulo a prime. The method and the results are new and deserve highest notice in mathematical cryptography. In particular, several previously known results are improved. For complementary results on the linear complexity of the discrete logarithm see \textit{C. Ding} and \textit{T. Helleseth} [On cyclotomic generator of order \(r\), Inf. Proc. Lett. 66, 21-25 (1998)], \textit{W. Meidl} and \textit{A. Winterhof} [IEEE Trans. Inf. Theory 47, 2807-2811 (2001; Zbl 1032.94004)], \textit{I. Shparlinski} [Number theoretic methods in cryptography. Complexity lower bounds. Progress in Computer Science and Applied Logic. 17. Basel: Birkhäuser (1999; Zbl 0912.11057)], and \textit{I. Shparlinski} [Cryptographic applications of analytic number theory. Complexity lower bounds and pseudorandomness. Progress in Computer Science and Applied Logic. 22. Basel: Birkhäuser (2003; Zbl 1036.94001)].

Recommendations

• Lower bounds on the linear complexity of the discrete logarithm in finite fields
• On the \(k\)-error linear complexity of binary sequences derived from the discrete logarithm in finite fields
• Number theoretic methods in cryptography. Complexity lower bounds
• scientific article; zbMATH DE number 1866875
• scientific article; zbMATH DE number 2127885

Cited in

(7)

• Aitken and Neville inverse interpolation methods for the Lucas logarithm problem
• Number theoretic methods in cryptography. Complexity lower bounds
• On the complexity of the discrete logarithm and Diffie-Hellman problems
• Polynomial representations of the Lucas logarithm
• Generic Hardness of the Multiple Discrete Logarithm Problem
• Lower bounds on the linear complexity of the discrete logarithm in finite fields
• On the k-error linear complexity of cyclotomic sequences

This page was built for publication: Linear complexity of the discrete logarithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1869823)