Correlation measures of binary sequences derived from Euler quotients

Huaning Liu; Zhixiong Chen; Chenhuang Wu; Huaning Liu; Zhixiong Chen; Chenhuang Wu

doi:10.3934/math.2022619

AIMS Mathematics

2022, Volume 7, Issue 6: 11087-11101. doi: 10.3934/math.2022619

Previous Article Next Article

Research article

Correlation measures of binary sequences derived from Euler quotients

1.
Research Center for Number Theory and Its Applications, School of Mathematics, Northwest University, Xi'an 710127, Shaanxi, China
2.
Fujian Key Laboratory of Financial Information Processing, Putian University, Putian 351100, Fujian, China
3.
Key Laboratory of Applied Mathematics of Fujian Province University, Putian University, Putian 351100, Fujian, China

Received: 25 November 2021 Revised: 22 March 2022 Accepted: 22 March 2022 Published: 07 April 2022
MSC : 11B50, 11K45, 94A55, 94A60

Fermat-Euler quotients arose from the study of the first case of Fermat's Last Theorem, and have numerous applications in number theory. Recently they were studied from the cryptographic aspects by constructing many pseudorandom binary sequences, whose linear complexities and trace representations were calculated. In this work, we further study their correlation measures by introducing a new approach based on Dirichlet characters, Ramanujan sums and Gauss sums. Our results show that the $ 4 $-order correlation measures of these sequences are very large. Therefore they may not be suggested for cryptography.
- Euler quotient,
- binary sequence,
- correlation measure,
- character sum
Citation: Huaning Liu, Zhixiong Chen, Chenhuang Wu. Correlation measures of binary sequences derived from Euler quotients[J]. AIMS Mathematics, 2022, 7(6): 11087-11101. doi: 10.3934/math.2022619

Related Papers:

Abstract

Fermat-Euler quotients arose from the study of the first case of Fermat's Last Theorem, and have numerous applications in number theory. Recently they were studied from the cryptographic aspects by constructing many pseudorandom binary sequences, whose linear complexities and trace representations were calculated. In this work, we further study their correlation measures by introducing a new approach based on Dirichlet characters, Ramanujan sums and Gauss sums. Our results show that the $ 4 $-order correlation measures of these sequences are very large. Therefore they may not be suggested for cryptography.

References

[1]	T. Agoh, K. Dilcher, L. Skula, Fermat quotients for composite moduli, J. Number Theory, 66 (1997), 29–50. https://doi.org/10.1006/jnth.1997.2162 doi: 10.1006/jnth.1997.2162
[2]	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
[3]	T. Apostol, Introduction to analytic number theory, New York: Springer, 1976. https://doi.org/10.1007/978-1-4757-5579-4
[4]	J. Cassaigne, C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences vii: the measures of pseudorandomness, Acta Arith., 103 (2002), 97–118. https://doi.org/10.4064/aa103-2-1 doi: 10.4064/aa103-2-1
[5]	M. 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
[6]	Z. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57 (2014), 1–10. https://doi.org/10.1007/s11432-014-5092-x doi: 10.1007/s11432-014-5092-x
[7]	Z. Chen, X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients, Des. Codes Cryptogr., 67 (2013), 317–323. https://doi.org/10.1007/s10623-012-9608-3 doi: 10.1007/s10623-012-9608-3
[8]	Z. Chen, X. Du, R. Marzouk, Trace representation of pseudorandom binary sequences derived from Euler quotients, Appl. Algebra Eng. Commun. Comput., 26 (2015), 555–570. https://doi.org/10.1007/s00200-015-0265-4 doi: 10.1007/s00200-015-0265-4
[9]	Z. Chen, A. Gómez, D. Gómez-Pérez, A. Tirkel, Correlation measure, linear complexity and maximum order complexity for families of binary sequences, Finite Fields Th. Appl., 78 (2022), 101977. https://doi.org/10.1016/j.ffa.2021.101977 doi: 10.1016/j.ffa.2021.101977
[10]	Z. Chen, L. Hu, X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105–108. https://doi.org/10.1007/s11277-010-0104-7 doi: 10.1007/s11277-010-0104-7
[11]	Z. Chen, A. Ostafe, A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, In: Lecture notes in computer science, Berlin: Springer, 2010, 73–85. https://doi.org/10.1007/978-3-642-13797-6_6
[12]	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
[13]	X. Du, Z. Chen, L. Hu, Linear complexity of binary sequences derived from Euler quotients with prime-power modulus, Inform. Process. Lett., 112 (2012), 604–609. https://doi.org/10.1016/j.ipl.2012.04.011 doi: 10.1016/j.ipl.2012.04.011
[14]	D. Gómez-Pérez, A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hung., 64 (2012), 161–168. https://doi.org/10.1007/s10998-012-3747-1 doi: 10.1007/s10998-012-3747-1
[15]	H. Liu, X. Liu, On the correlation measures of orders $ 3 $ and $ 4 $ of binary sequence of period $ p^2 $ derived from Fermat quotients, Adv. Math. Commun., in press. https://doi.org/10.3934/amc.2021008
[16]	C. Mauduit, A. Sárközy, On finite pseudorandom binary sequencs I: measure of pseudorandomness, the Legendre symbol, Acta Arith., 82 (1997), 365–377. https://doi.org/10.4064/aa-82-4-365-377 doi: 10.4064/aa-82-4-365-377
[17]	A. Ostafe, I. 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
[18]	C. D. Pan, C. B. Pan, Goldbach conjecture (Chinese), Beijing: Science Press, 2011.
[19]	I. 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
[20]	I. 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
[21]	I. 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
[22]	J. Zhang, S. Gao, C. Zhao, Linear complexity of a family of binary $ pq^2 $-periodic sequences from Euler quotients, IEEE Trans. Inf. Theory, 66 (2020), 5774–5780. https://doi.org/10.1109/TIT.2020.2979838 doi: 10.1109/TIT.2020.2979838
[23]	J. Zhang, C. Hu, X. Fan, C. Zhao, Trace representation of the binary $ pq^2 $-periodic sequences derived from Euler quotients, Cryptogr. Commun., 13 (2021), 343–359. https://doi.org/10.1007/s12095-021-00475-1 doi: 10.1007/s12095-021-00475-1

Reader Comments

Your name:*

Email:*
© 2022 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)