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

Igor E. Shparlinski; Arne Winterhof

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

Igor E. Shparlinski^*, Arne Winterhof

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-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 language	English
Title of host publication	Sequences and Their Applications, SETA 2006 - 4th International Conference, Proceedings
Editors	Guang Gong, Tor Helleseth, Hong-Yeop Song, Kyeongcheol Yang
Place of Publication	Berlin; Heidelberg
Publisher	Springer, Springer Nature
Pages	295-303
Number of pages	9
Volume	4086 LNCS
ISBN (Print)	3540445234, 9783540445234
Publication status	Published - 2006
Event	4th International Conference on Sequences and Their Applications, SETA 2006 - Beijing, China Duration: 24 Sept 2006 → 28 Sept 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4086 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	4th International Conference on Sequences and Their Applications, SETA 2006
Country/Territory	China
City	Beijing
Period	24/09/06 → 28/09/06

Cite this

Shparlinski, I. E., & Winterhof, A. (2006). On the discrepancy and linear complexity of some counter-dependent recurrence sequences. In G. Gong, T. Helleseth, H-Y. Song, & K. Yang (Eds.), Sequences and Their Applications, SETA 2006 - 4th International Conference, Proceedings (Vol. 4086 LNCS, pp. 295-303). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4086 LNCS). Springer, Springer Nature.

Shparlinski, Igor E. ; Winterhof, Arne. / On the discrepancy and linear complexity of some counter-dependent recurrence sequences. Sequences and Their Applications, SETA 2006 - 4th International Conference, Proceedings. editor / Guang Gong ; Tor Helleseth ; Hong-Yeop Song ; Kyeongcheol Yang. Vol. 4086 LNCS Berlin; Heidelberg : Springer, Springer Nature, 2006. pp. 295-303 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{18b812d1f3bb4066b9f8fac539f33a91,

title = "On the discrepancy and linear complexity of some counter-dependent recurrence sequences",

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.",

author = "Shparlinski, {Igor E.} and Arne Winterhof",

year = "2006",

language = "English",

isbn = "3540445234",

volume = "4086 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "295--303",

editor = "Guang Gong and Tor Helleseth and Hong-Yeop Song and Kyeongcheol Yang",

booktitle = "Sequences and Their Applications, SETA 2006 - 4th International Conference, Proceedings",

address = "United States",

note = "4th International Conference on Sequences and Their Applications, SETA 2006 ; Conference date: 24-09-2006 Through 28-09-2006",

}

Shparlinski, IE & Winterhof, A 2006, On the discrepancy and linear complexity of some counter-dependent recurrence sequences. in G Gong, T Helleseth, H-Y Song & K Yang (eds), Sequences and Their Applications, SETA 2006 - 4th International Conference, Proceedings. vol. 4086 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4086 LNCS, Springer, Springer Nature, Berlin; Heidelberg, pp. 295-303, 4th International Conference on Sequences and Their Applications, SETA 2006, Beijing, China, 24/09/06.

On the discrepancy and linear complexity of some counter-dependent recurrence sequences. / Shparlinski, Igor E.; Winterhof, Arne.
Sequences and Their Applications, SETA 2006 - 4th International Conference, Proceedings. ed. / Guang Gong; Tor Helleseth; Hong-Yeop Song; Kyeongcheol Yang. Vol. 4086 LNCS Berlin; Heidelberg: Springer, Springer Nature, 2006. p. 295-303 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4086 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

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

AU - Shparlinski, Igor E.

AU - Winterhof, Arne

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33749676851&partnerID=8YFLogxK

M3 - Conference proceeding contribution

AN - SCOPUS:33749676851

SN - 3540445234

SN - 9783540445234

VL - 4086 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 295

EP - 303

BT - Sequences and Their Applications, SETA 2006 - 4th International Conference, Proceedings

A2 - Gong, Guang

A2 - Helleseth, Tor

A2 - Song, Hong-Yeop

A2 - Yang, Kyeongcheol

PB - Springer, Springer Nature

CY - Berlin; Heidelberg

T2 - 4th International Conference on Sequences and Their Applications, SETA 2006

Y2 - 24 September 2006 through 28 September 2006

ER -

Shparlinski IE, Winterhof A. On the discrepancy and linear complexity of some counter-dependent recurrence sequences. In Gong G, Helleseth T, Song H-Y, Yang K, editors, Sequences and Their Applications, SETA 2006 - 4th International Conference, Proceedings. Vol. 4086 LNCS. Berlin; Heidelberg: Springer, Springer Nature. 2006. p. 295-303. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

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

Abstract

Publication series

Other

Other files and links

Fingerprint

Cite this