Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On Nearly Linear Recurrence Sequences Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Measures of Pseudorandomness: Arithmetic Autocorrelation and Correlation Measure

Authors : Richard Hofer, László Mérai, Arne Winterhof

Published in: Number Theory – Diophantine Problems, Uniform Distribution and Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We prove a relation between two measures of pseudorandomness, the arithmetic autocorrelation, and the correlation measure of order k. Roughly speaking, we show that any binary sequence with small correlation measure of order k up to a sufficiently large k cannot have a large arithmetic correlation. We apply our result to several classes of sequences including Legendre sequences defined with polynomials.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter On the Monoid Generated by a Lucas Sequence
next chapter On Multiplicative Independent Bases for Canonical Number Systems in Cyclotomic Number Fields
Literature
1.
N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira, V. Rödl, Measures of pseudorandomness for finite sequences: typical values. Proc. Lond. Math. Soc. (3) 95, 778–812 (2007)
2.
N. Brandstätter, A. Winterhof, Linear complexity profile of binary sequences with small correlation measure. Period. Math. Hungar. 52, 1–8 (2006)MathSciNetCrossRefMATH
3.
C. Diem, On the use of expansion series for stream ciphers. LMS, J. Comput. Math. 15, 326–340 (2012)
4.
G. Dorfer, A. Winterhof, Lattice structure and linear complexity profile of nonlinear pseudorandom number generators. Appl. Algebra Eng. Comm. Comput. 13, 499–508 (2003)MathSciNetCrossRefMATH
5.
J. Folláth, Construction of pseudorandom binary sequences using additive characters over GF(2 k ). Period. Math. Hungar. 57, 73–81 (2008)MathSciNetCrossRefMATH
6.
M. Goresky, A. Klapper, Arithmetic crosscorrelations of feedback with carry shift register sequences. IEEE Trans. Inf. Theory 43, 1342–1345 (1997)MathSciNetCrossRefMATH
7.
M. Goresky, A. Klapper, Some results on the arithmetic correlation of sequences (extended abstract). Sequences and Their Applications–SETA 2008. Lecture Notes in Computer Science, vol. 5203 (Springer, Berlin, 2008), pp. 71–80
8.
M. Goresky, A. Klapper, Statistical properties of the arithmetic correlation of sequences. Int. J. Found. Comput. Sci. 22, 1297–1315 (2011)MathSciNetCrossRefMATH
9.
M. Goresky, A. Klapper, Algebraic Shift Register Sequences (Cambridge University Press, Cambridge, 2012)MATH
10.
L. Goubin, C. Mauduit, A. Sárközy, Construction of large families of pseudorandom binary sequences. J. Number Theory 106, 56–69 (2004)MathSciNetCrossRefMATH
11.
K. Gyarmati, Measures of pseudorandomness, in Finite Fields and Their Applications, ed. by P. Charpin, A. Pott, A. Winterhof. Radon Series on Computational and Applied Mathematics, vol. 11 (de Gruyter, Berlin, 2013), pp. 43–64
12.
13.
14.
R. Hofer, A. Winterhof, Linear complexity and expansion complexity of some number theoretic sequences, in Arithmetic of Finite Fields (WAIFI 2016). Lecture Notes in Computer Science, vol. 10064 (Springer, Cham, 2016), pp. 67–74
15.
D. Mandelbaum, Arithmetic codes with large distance. IEEE Trans. Inf. Theory 13, 237–242 (1967)CrossRefMATH
16.
C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol. Acta Arith. 82, 365–377 (1997)
17.
18.
L. Mérai, A. Winterhof, On the Nth linear complexity of p-automatic sequences over \(\mathbb{F}_{p}\) (preprint 2016)
19.
L. Mérai, H. Niederreiter, A. Winterhof, Expansion complexity and linear complexity of sequences over finite fields. Cryptogr. Commun. (2016). doi:10.1007/s12095-016-0189-2MATH
20.
H. Niederreiter, A. Winterhof, Lattice structure and linear complexity of nonlinear pseudorandom numbers. Appl. Algebra Eng. Commun. Comput. 13, 319–326 (2002)MathSciNetCrossRefMATH
21.
J. Rivat, A. Sárközy, On pseudorandom sequences and their application, in General Theory of Information Transfer and Combinatorics. Lecture Notes in Computer Science, vol. 4123 (Springer, Berlin, 2006), pp. 343–361
22.
A. Topuzoğlu, A. Winterhof, Pseudorandom sequences, in Topics in Geometry, Coding Theory and Cryptography. Algebra and Applications, vol. 6 (Springer, Dordrecht, 2007), pp. 135–166
Metadata
Title
Measures of Pseudorandomness: Arithmetic Autocorrelation and Correlation Measure
Authors
Richard Hofer
László Mérai
Arne Winterhof
Copyright Year
2017
Book
Number Theory – Diophantine Problems, Uniform Distribution and Applications

Print ISBN: 978-3-319-55356-6

Electronic ISBN: 978-3-319-55357-3

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-55357-3_15

Premium Partner

    Image Credits