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]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281

[2]

Pinhui Ke, Yueqin Jiang, Zhixiong Chen. On the linear complexities of two classes of quaternary sequences of even length with optimal autocorrelation. Advances in Mathematics of Communications, 2018, 12 (3) : 525-539. doi: 10.3934/amc.2018031

[3]

Oǧuz Yayla. Nearly perfect sequences with arbitrary out-of-phase autocorrelation. Advances in Mathematics of Communications, 2016, 10 (2) : 401-411. doi: 10.3934/amc.2016014

[4]

Yu Zheng, Li Peng, Teturo Kamae. Characterization of noncorrelated pattern sequences and correlation dimensions. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 5085-5103. doi: 10.3934/dcds.2018223

[5]

Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047

[6]

Marcela Mejía, J. Urías. An asymptotically perfect pseudorandom generator. Discrete & Continuous Dynamical Systems - A, 2001, 7 (1) : 115-126. doi: 10.3934/dcds.2001.7.115

[7]

Yuhua Sun, Zilong Wang, Hui Li, Tongjiang Yan. The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$. Advances in Mathematics of Communications, 2013, 7 (4) : 409-424. doi: 10.3934/amc.2013.7.409

[8]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036

[9]

Hua Liang, Jinquan Luo, Yuansheng Tang. On cross-correlation of a binary $m$-sequence of period $2^{2k}-1$ and its decimated sequences by $(2^{lk}+1)/(2^l+1)$. Advances in Mathematics of Communications, 2017, 11 (4) : 693-703. doi: 10.3934/amc.2017050

[10]

Sabyasachi Karati, Palash Sarkar. Connecting Legendre with Kummer and Edwards. Advances in Mathematics of Communications, 2019, 13 (1) : 41-66. doi: 10.3934/amc.2019003

[11]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281

[12]

Oğul Esen, Partha Guha. On the geometry of the Schmidt-Legendre transformation. Journal of Geometric Mechanics, 2018, 10 (3) : 251-291. doi: 10.3934/jgm.2018010

[13]

Tanja Eisner, Rainer Nagel. Arithmetic progressions -- an operator theoretic view. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 657-667. doi: 10.3934/dcdss.2013.6.657

[14]

Mehdi Pourbarat. On the arithmetic difference of middle Cantor sets. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4259-4278. doi: 10.3934/dcds.2018186

[15]

Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169

[16]

Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249-259. doi: 10.3934/amc.2008.2.249

[17]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489

[18]

Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012

[19]

Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369

[20]

Kevin Ford. The distribution of totients. Electronic Research Announcements, 1998, 4: 27-34.

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (8)
  • HTML views (10)
  • Cited by (2)

Other articles
by authors

[Back to Top]