-
Previous Article
Some results on the structure of constacyclic codes and new linear codes over GF(7) from quasi-twisted codes
- AMC Home
- This Issue
-
Next Article
On defining generalized rank weights
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 |
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.
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. 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. |
[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. |
show all references
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. 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. |
[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. |
[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
Tools
Metrics
Other articles
by authors
[Back to Top]