Arithmetic autocorrelation and pattern distribution of binary sequences

Xi Liu; Huaning Liu; Xi Liu; Huaning Liu

doi:10.3934/era.2025038

Electronic Research Archive

2025, Volume 33, Issue 2: 849-866. doi: 10.3934/era.2025038

Previous Article Next Article

Research article Special Issues

Arithmetic autocorrelation and pattern distribution of binary sequences

Xi Liu ,
Huaning Liu ^,

Research Center for Number Theory and its Applications, School of Mathematics, Northwest University, Xi'an 710127, China

Received: 03 December 2024 Revised: 24 January 2025 Accepted: 06 February 2025 Published: 14 February 2025

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.
- arithmetic autocorrelation,
- Fermat quotient,
- generalized cyclotomic,
- binary sequence,
- character sum
Citation: Xi Liu, Huaning Liu. Arithmetic autocorrelation and pattern distribution of binary sequences[J]. Electronic Research Archive, 2025, 33(2): 849-866. doi: 10.3934/era.2025038

Related Papers:

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.

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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 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 doi: 10.1109/TIT.2018.2811507
[31]	E. Bai, X. Fu, G. Xiao, On the linear complexity of generalized cyclotomic sequences of order four over $\mathbb{Z}_pq$, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E88-A (2005), 392–395. https://doi.org/10.1093/ietfec/E88-A.1.392 doi: 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 doi: 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 doi: 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+1}q^{n+1}$, IEEE Trans. Inf. Theory, 58 (2012), 5534–5543. https://doi.org/10.1109/TIT.2012.2196254 doi: 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 doi: 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 doi: 10.1080/01611194.2022.2071116
[37]	Z. Chen, V. Edemskiy, Z. Niu, Y. Sang, Arithmetic correlation of binary half-$\ell$-sequences, IET Inf. Secur., 17 (2023), 289–293. https://doi.org/10.1049/ise2.12093 doi: 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 doi: 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 doi: 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 doi: 10.1109/tit.2023.3282229

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)