On the arithmetic autocorrelation of the Legendre sequence

Richard Hofer; Arne Winterhof

doi:10.3934/amc.2017015

Article Contents

2017, Volume 11, Issue 1: 237-244. Doi: 10.3934/amc.2017015

This issue Previous Article On defining generalized rank weights Next Article Some results on the structure of constacyclic codes and new linear codes over GF(7) from quasi-twisted codes

On the arithmetic autocorrelation of the Legendre sequence

Richard Hofer^, and
Arne Winterhof

Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Str. 69,4040 Linz, Austria

^* Corresponding author
^* Corresponding author

Received: October 2015

Revised: February 2016

Published: May 2017

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

The Legendre sequence possesses several desirable features of pseudorandomness in view of different applications such as a high linear complexity (profile) for cryptography and a small (aperiodic) autocorrelation for radar, gps, or sonar. Here we prove the first nontrivial bound on its arithmetic autocorrelation, another figure of merit introduced by Mandelbaum for errorcorrecting codes.

Keywords:

Mathematics Subject Classification: Primary: 94A55; Secondary: 11T71, 94A05, 94A60.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier, Amsterdam, 2004.
[2]	C. Ding, Pattern distributions of Legendre sequences, IEEE Trans. Inform. Theory, 44 (1998), 1693-1698. doi: 10.1109/18.681353.
[3]	C. Ding, T. Helleseth and W. Shan, On the linear complexity of Legendre sequences, IEEE Trans. Inform. Theory, 44 (1998), 1276-1278. doi: 10.1109/18.669398.
[4]	M. Goresky and A. Klapper, Arithmetic crosscorrelations of feedback with carry shift register sequences, IEEE Trans. Inform. Theory, 43 (1997), 1342-1345. doi: 10.1109/18.605605.
[5]	M. Goresky and A. Klapper, Some results on the arithmetic correlation of sequences, Sequences and Their Applications-SETA 2008, Springer, Berlin, 2008, 71-80.
[6]	M. Goresky and A. Klapper, Statistical properties of the arithmetic correlation of sequences, Int. J. Found. Comput. Sci., 22 (2011), 1297-1315. doi: 10.1007/978-3-540-85912-3_7.
[7]	M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge Univ. Press, Cambridge, 2012. doi: 10.1142/S0129054111008726.
[8]	D. Mandelbaum, Arithmetic codes with large distance, IEEE Trans. Inform. Theory, 13 (1967), 237-242.
[9]	C. Mauduit and A. Sárközy, On finite pseudorandom binary sequences. Ⅰ. Measure of pseudorandomness, the Legendre symbol, Acta Arith., 82 (1997), 365-377.
[10]	R. E. A. C. Paley, On orthogonal matrices, J. Math. Physics, 12 (1933), 311-320. doi: 10.1002/sapm1933121311.
[11]	O. Perron, Bemerkungen über die Verteilung der quadratischen Reste, Math. Z., 56 (1952), 122-130. doi: 10.1007/BF01175029.
[12]	I. Shparlinski, Cryptographic Applications of Analytic Number Theory. Complexity Lower Bounds and Pseudorandomness, in Progress in Computer Science and Applied Logic 22, Birkhäuser Verlag, Basel, 2003. doi: 10.1007/978-3-0348-8037-4.
[13]	R. J. Turyn, The linear generation of Legendre sequence, J. Soc. Indust. Appl. Math., 12 (1964), 115-116. doi: 10.1137/0112010.