Advanced Search
Article Contents
Article Contents

On the arithmetic autocorrelation of the Legendre sequence

  • * Corresponding author

    * Corresponding author 
Abstract Full Text(HTML) Related Papers Cited by
  • 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.

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • [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. 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.
    [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. KlapperAlgebraic 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.
  • 加载中

Article Metrics

HTML views(395) PDF downloads(156) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint