On the Linear Complexity of the Power Generator

Igor Shparlinski

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)


We obtain a lower bound on the linear complexity of the power generator of pseudo-random numbers, which in some special cases is also known as the RSA generator and as the Blum-Blum-Shub generator. In some very important cases this bound is essentially the best possible. In particular, this implies that lattice reduction attacks on such generators are not feasible.

Original languageEnglish
Pages (from-to)5-10
Number of pages6
JournalDesigns, Codes and Cryptography
Issue number1
Publication statusPublished - 2001


  • Blum-Blum-Shub generator
  • Cryptography
  • Linear complexity
  • Power generator
  • RSA generator


Dive into the research topics of 'On the Linear Complexity of the Power Generator'. Together they form a unique fingerprint.

Cite this