Arithmetic autocorrelation and pattern distribution of binary sequences

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

Abstract

We clarify a relation between the arithmetic autocorrelation and pattern distribution of binary sequences, then we apply the relation to study the upper bound of arithmetic autocorrelation for two binary sequences constructed by Fermat quotient and the generalized cyclotomic class of order 2, respectively. Our results indicate that the sequences with large “long term” correlations may have small “short term” pattern distribution; and thus have rather small arithmetic autocorrelations.

Keywords

arithmetic autocorrelation / Fermat quotient / generalized cyclotomic / binary sequence / character sum

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

References

[1] D. Mandelbaum, Arithmetic codes with large distance, IEEE Trans. Inf. Theory, 13 (1967), 237-242. https://doi.org/10.1109/TIT.1967.1054015

[2] R. Hofer, A. Winterhof, On the arithmetic autocorrelation of the legendre sequence, Adv. Math. Commun., 11 (2017), 237-244. https://doi.org/10.3934/amc.2017015

[3] M. Goresky, A. Klapper, Arithmetic crosscorrelation of feedback with carray shift register sequences, IEEE Trans. Inf. Theory, 43 (1997), 1342-1345. https://doi.org/10.1109/18.605605

[4] M. Goresky, A. Klapper, Some results on the arithmetic correlation of sequences, in Sequences and Their Applications-SETA 2008: 5th International Conference Lexington, 5203 (2008), 71-80. https://doi.org/10.1007/978-3-540-85912-3_7

[5] M. Goresky, A. Klapper, Statistical properties of the arithmetic correlation of sequences, Int. J. Found. Comput. Sci., 22 (2011), 1297-1315. https://doi.org/10.1142/S0129054111008726

[6] M. Goresky, A. Klapper, Algebratic Shift Register Sequences, Cambridge University Press, U.K., 2012. https://doi.org/10.1017/CBO9781139057448

[7] R. Hofer, L. Mérai, A. Winterhof, “ Measure of pseudorandomness: Arithmetic autocorrelation and correlation measure”, in Number Theory-Diophantine Problems, Uniform Distribution and Applications, (eds. C. Elsholtz and P. Grabner), Spring, Cham (2017), 303-312. https://doi.org/10.1007/978-3-319-55357-3_15

[8] C. Ding, Pattern distributions of Legendre sequences, IEEE Trans. Inf. Theory, 44 (1998), 1693-1698. https://doi.org/10.1109/18.681353

[9] S. W. Golomb, G. Gong, Signal Design for Good Correlation: For Wireless Communication, Cryptography and Radar, Cambridge University Press, Cambridge, 2005. https://doi.org/10.1017/CBO9780511546907

[10] H. Liu, Y. Ren, Balance, pattern distribution and linear complexity of M-ary sequences from Sidel’nikov sequences, Appl. Algebra Engrg. Comm. Comput., 35 (2024), 667-682. https://doi.org/10.1007/s00200-022-00580-5

[11] C. Mauduit, A. Sárközy, On finite pseudorandom sequences of k symbols, Indag. Math., 13 (2002), 89-101. https://doi.org/10.1016/S0019-3577(02)90008-X

[12] H. Aly, A. Winterhof, Boolean functions derived from Fermat quotients, Cryptogr. Commun., 3 (2011), 165-174. https://doi.org/10.1007/s12095-011-0043-5

[13] M. C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38. https://doi.org/10.4064/aa152-1-3

[14] Z. Chen, A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discrete Math., 28 (2014), 1-7. https://doi.org/10.1137/130907951

[15] D. Gómez, A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hungar., 64 (2012), 161-168. https://doi.org/10.1007/s10998-012-3747-1

[16] A. Ostafe, I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discrete Math., 25 (2011), 50-71. https://doi.org/10.1137/100798466

[17] I. E. Shparlinski, Fermat quotients: exponential sums, value set and primitive roots, Bull. Lond. Math. Soc., 43 (2011), 1228-1238. https://doi.org/10.1112/blms/bdr058

[18] I. E. Shparlinski, Character sums with Fermat quotients, Q. J. Math., 62 (2011), 1031-1043. https://doi.org/10.1093/qmath/haq028

[19] I. E. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes, Bull. Aust. Math. Soc., 83 (2011), 456-462. https://doi.org/10.1017/S000497271000198X

[20] Z. Chen, L. Hu, X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105-108.

[21] Z. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57 (2014), 112109:1-10. https://doi.org/10.1007/s11432-014-5092-x

[22] Z. Chen, Z. Niu, C. Wu, On the k-error linear complexity of binary sequences derived from polynomial quotients, preprint, arXiv:1307.6626.

[23] X. Du, A. Klapper, Z. Chen, Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations, Inf. Process. Lett., 112 (2012), 233-237. https://doi.org/10.1016/j.ipl.2011.11.017

[24] A. L. Whiteman, A family of difference sets, Illinois J. Math., 6 (1962), 107-121. https://doi.org/10.1215/ijm/1255631810

[25] C. Ding, Linear complexity of generalized cyclotomic binary sequences of order 2, Finite Fields Appl., 3 (1997), 159-174. https://doi.org/10.1006/ffta.1997.0181

[26] T. W. Cusick, C. Ding, A. Renvall, Stream Ciphers and Number Theory, North-holland mathematical library, Amsterdam, The Netherlands: North-Holland, 1998. https://doi.org/10.1016/s0924-6509(98)x8001-3

[27] C. Ding, Autocorrelation values of generalized cyclotomic sequences of order two, IEEE Trans. Inf. Theory, 44 (1998), 1699-1702. https://doi.org/10.1109/18.681354

[28] N. Brandstätter, A. Winterhof, Some notes on the two-prime generator of order 2, IEEE Trans. Inf. Theory, 51 (2005), 3654-3657. https://doi.org/10.1109/TIT.2005.855615

[29] Z. Dai, G. Gong, H. Y. Song, A trace representation of binary Jacobi sequences, Discrete Math., 309 (2009), 1517-1527. https://doi.org/10.1016/j.disc.2008.02.024

[30] R. Hofer, A. Winterhof, On the 2-adic complexity of the two-prime generator, IEEE Trans. Inf. Theory, 64 (2018), 5957-5960. https://doi.org/10.1109/TIT.2018.2811507

[31] E. Bai, X. Fu, G. Xiao, On the linear complexity of generalized cyclotomic sequences of order four over Z_pq , IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E88-A (2005), 392-395. https://doi.org/10.1093/ietfec/E88-A.1.392

[32] E. Bai, X. Liu, G. Xiao, Linear complexity of new generalized cyclotomic sequences of order two of length pq, IEEE Trans. Inf. Theory, 51 (2005), 1849-1853. https://doi.org/10.1109/TIT.2005.846450

[33] T. Yan, X. Du, G. Xiao, X, Huang, Linear complexity of binary Whiteman generalized cyclotomic sequences of order 2^k , Inf. Sci., 179 (2009), 1019-1023. https://doi.org/10.1016/j.ins.2008.11.006

[34] L. Hu, Q. Yue, M. Wang, The linear complexity of Whiteman’s generalized cyclotomic sequences of period p^m+1qⁿ⁺¹ , IEEE Trans. Inf. Theory, 58 (2012), 5534-5543. https://doi.org/10.1109/TIT.2012.2196254

[35] J. Rivat, A. Sárközy, Modular constructions of pseudorandom binary sequences with composite moduli, Period. Math. Hungar., 51 (2005), 75-107. https://doi.org/10.1007/s10998-005-0031-7

[36] Z. Chen, Z. Niu, Y. Sang, C. Wu, Arithmetic autocorrelation of binary m-sequences, Cryptologia, 47 (2023), 449-458. https://doi.org/10.1080/01611194.2022.2071116

[37] Z. Chen, V. Edemskiy, Z. Niu, Y. Sang, Arithmetic correlation of binary half-ℓ-sequences, IET Inf. Secur., 17 (2023), 289-293. https://doi.org/10.1049/ise2.12093

[38] Z. Chen, Z. Niu, A. Winterhof, Arithmetic crosscorrelation of pseudorandom binary sequences of coprime periods, IEEE Trans. Inf. Theory, 68 (2022), 7538-7544. https://doi.org/10.1109/tit.2022.3184176

[39] X. Jing, K. Feng, Arithmetic crosscorrelation of binary m-sequences with coprime periods, Finite Fields Appl., 96 (2024), 102424. https://doi.org/10.1016/j.ffa.2024.102424

[40] X. Jing, A. Zhang, K. Feng, Arithmetic Autocorrelation Distribution of Binary m-Sequences, IEEE Trans. Inf. Theory, 69 (2023), 6040-6047. https://doi.org/10.1109/tit.2023.3282229