Linear complexity of the discrete logarithm
type: Item
instance of: scholarly article
title: Linear complexity of the discrete logarithm
zbMATH Open document ID: 1024.11078
DOI: 10.1023/A:1022584306676
author: Tanja Lange
author: Igor E. Shparlinski
author: Sergei Konyagin
published in: Designs, Codes and Cryptography
publication date: 2003-04-28T00:00:00Z
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)].
reviewed by: Arne Winterhof
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 1902903
zbMATH Keywords: discrete logarithm
zbMATH Keywords: linear recurrence sequences
zbMATH Keywords: linear complexity
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1902903