On the discrepancy and linear complexity of some counter-dependent recurrence sequences

Igor E. Shparlinski*, Arne Winterhof

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

2 Citations (Scopus)

Abstract

We prove a discrepancy bound "on average" over all initial values aα(0) = α of congruential pseudorandom numbers obtained from the sequences aα(n) over a finite field of prime order defined by aα(n) = naα(n - 1) + 1, n = 1, 2,..., using new bounds on certain exponential sums. Moreover, we prove a lower bound on the linear complexity of this sequence showing that its structural properties are close to be best possible.

Original languageEnglish
Title of host publicationSequences and Their Applications, SETA 2006 - 4th International Conference, Proceedings
EditorsGuang Gong, Tor Helleseth, Hong-Yeop Song, Kyeongcheol Yang
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Pages295-303
Number of pages9
Volume4086 LNCS
ISBN (Print)3540445234, 9783540445234
Publication statusPublished - 2006
Event4th International Conference on Sequences and Their Applications, SETA 2006 - Beijing, China
Duration: 24 Sep 200628 Sep 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4086 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other4th International Conference on Sequences and Their Applications, SETA 2006
CountryChina
CityBeijing
Period24/09/0628/09/06

Fingerprint

Dive into the research topics of 'On the discrepancy and linear complexity of some counter-dependent recurrence sequences'. Together they form a unique fingerprint.

Cite this