February  2017, 11(1): 237-244. doi: 10.3934/amc.2017015

On the arithmetic autocorrelation of the Legendre sequence

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

* Corresponding author

Received  October 2015 Revised  February 2016 Published  February 2017

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.

Citation: Richard Hofer, Arne Winterhof. On the arithmetic autocorrelation of the Legendre sequence. Advances in Mathematics of Communications, 2017, 11 (1) : 237-244. doi: 10.3934/amc.2017015
References:
[1]

T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier, Amsterdam, 2004.  Google Scholar

[2]

C. Ding, Pattern distributions of Legendre sequences, IEEE Trans. Inform. Theory, 44 (1998), 1693-1698.  doi: 10.1109/18.681353.  Google Scholar

[3]

C. DingT. Helleseth and W. Shan, On the linear complexity of Legendre sequences, IEEE Trans. Inform. Theory, 44 (1998), 1276-1278.  doi: 10.1109/18.669398.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[7] M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge Univ. Press, Cambridge, 2012.  doi: 10.1142/S0129054111008726.  Google Scholar
[8]

D. Mandelbaum, Arithmetic codes with large distance, IEEE Trans. Inform. Theory, 13 (1967), 237-242.   Google Scholar

[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.   Google Scholar

[10]

R. E. A. C. Paley, On orthogonal matrices, J. Math. Physics, 12 (1933), 311-320.  doi: 10.1002/sapm1933121311.  Google Scholar

[11]

O. Perron, Bemerkungen über die Verteilung der quadratischen Reste, Math. Z., 56 (1952), 122-130.  doi: 10.1007/BF01175029.  Google Scholar

[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.  Google Scholar

[13]

R. J. Turyn, The linear generation of Legendre sequence, J. Soc. Indust. Appl. Math., 12 (1964), 115-116.  doi: 10.1137/0112010.  Google Scholar

show all references

References:
[1]

T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier, Amsterdam, 2004.  Google Scholar

[2]

C. Ding, Pattern distributions of Legendre sequences, IEEE Trans. Inform. Theory, 44 (1998), 1693-1698.  doi: 10.1109/18.681353.  Google Scholar

[3]

C. DingT. Helleseth and W. Shan, On the linear complexity of Legendre sequences, IEEE Trans. Inform. Theory, 44 (1998), 1276-1278.  doi: 10.1109/18.669398.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[7] M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge Univ. Press, Cambridge, 2012.  doi: 10.1142/S0129054111008726.  Google Scholar
[8]

D. Mandelbaum, Arithmetic codes with large distance, IEEE Trans. Inform. Theory, 13 (1967), 237-242.   Google Scholar

[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.   Google Scholar

[10]

R. E. A. C. Paley, On orthogonal matrices, J. Math. Physics, 12 (1933), 311-320.  doi: 10.1002/sapm1933121311.  Google Scholar

[11]

O. Perron, Bemerkungen über die Verteilung der quadratischen Reste, Math. Z., 56 (1952), 122-130.  doi: 10.1007/BF01175029.  Google Scholar

[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.  Google Scholar

[13]

R. J. Turyn, The linear generation of Legendre sequence, J. Soc. Indust. Appl. Math., 12 (1964), 115-116.  doi: 10.1137/0112010.  Google Scholar

[1]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, 2021, 20 (1) : 369-388. doi: 10.3934/cpaa.2020271

[2]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[3]

Andreu Ferré Moragues. Properties of multicorrelation sequences and large returns under some ergodicity assumptions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020386

[4]

Kalikinkar Mandal, Guang Gong. On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020125

[5]

Ludovick Gagnon, José M. Urquiza. Uniform boundary observability with Legendre-Galerkin formulations of the 1-D wave equation. Evolution Equations & Control Theory, 2021, 10 (1) : 129-153. doi: 10.3934/eect.2020054

[6]

Alexandra Köthe, Anna Marciniak-Czochra, Izumi Takagi. Hysteresis-driven pattern formation in reaction-diffusion-ODE systems. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3595-3627. doi: 10.3934/dcds.2020170

[7]

Hua Zhong, Xiaolin Fan, Shuyu Sun. The effect of surface pattern property on the advancing motion of three-dimensional droplets. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020366

[8]

Evelyn Sander, Thomas Wanner. Equilibrium validation in models for pattern formation based on Sobolev embeddings. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 603-632. doi: 10.3934/dcdsb.2020260

[9]

Yuanfen Xiao. Mean Li-Yorke chaotic set along polynomial sequence with full Hausdorff dimension for $ \beta $-transformation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 525-536. doi: 10.3934/dcds.2020267

[10]

Jinfeng Wang, Sainan Wu, Junping Shi. Pattern formation in diffusive predator-prey systems with predator-taxis and prey-taxis. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1273-1289. doi: 10.3934/dcdsb.2020162

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (48)
  • HTML views (59)
  • Cited by (5)

Other articles
by authors

[Back to Top]