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.
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
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.
[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 |