Linear complexity of the discrete logarithm

Sergei Konyagin, Tanja Lange, Igor Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


We obtain new lower bounds on the linear complexity of several consecutive values of the discrete logarithm modulo a prime p. These bounds generalize and improve several previous results.

Original languageEnglish
Pages (from-to)135-146
Number of pages12
JournalDesigns, Codes and Cryptography
Issue number2
Publication statusPublished - Mar 2003


  • discrete logarithm
  • linear complexity
  • linear recurrence sequences

Fingerprint Dive into the research topics of 'Linear complexity of the discrete logarithm'. Together they form a unique fingerprint.

Cite this