Research article

Correlation measures of binary sequences derived from Euler quotients

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

    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:

  • 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
  • Reader Comments
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1179) PDF downloads(54) Cited by(0)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog