# American Institute of Mathematical Sciences

November  2018, 12(4): 805-816. doi: 10.3934/amc.2018047

## On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients

 1 Provincial Key Laboratory of Applied Mathematics, Putian University, Putian, Fujian 351100, China 2 Department of Applied Mathematics and Informatics, Novgorod State University, Veliky Novgorod, 173003, Russia 3 Fujian Provincial Key Laboratory of Network Security and Cryptology, College of Mathematics and Informatics, Fujian Normal University, Fuzhou, Fujian 350117, China

* Corresponding author: Zhixiong Chen (ptczx@126.com)

Received  March 2018 Published  September 2018

Fund Project: The work was partially supported by the National Natural Science Foundation of China under grant No. 61772292 and by the Fujian Provincial Natural Science Foundation of China under grant No. 2018J01425 and by the Program for Innovative Research Team in Science and Technology in Fujian Province University. V. Edemskiy was supported by Russian Foundation for Basic Research and Novgorod region under grant No. 18-41-530001. P. Ke was also supported by National Natural Science Foundation of China under grant No. 61772476.

We investigate the $k$-error linear complexity of pseudorandom binary sequences of period $p^{\mathfrak{r}}$ derived from the Euler quotients modulo $p^{\mathfrak{r}-1}$, a power of an odd prime $p$ for $\mathfrak{r}≥2$. When $\mathfrak{r} = 2$, this is just the case of polynomial quotients (including Fermat quotients) modulo $p$, which has been studied in an earlier work of Chen, Niu and Wu. In this work, we establish a recursive relation on the $k$-error linear complexity of the sequences for the case of $\mathfrak{r}≥3$. We also state the exact values of the $k$-error linear complexity for the case of $\mathfrak{r} = 3$. From the results, we can find that the $k$-error linear complexity of the sequences (of period $p^{\mathfrak{r}}$) does not decrease dramatically for $k<p^{\mathfrak{r}-2}(p-1)^2/2$.

Citation: Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047
##### References:
 [1] T. Agoh, K. Dilcher and L. Skula, Fermat quotients for composite moduli, J. Number Theory, 66 (1997), 29-50.  doi: 10.1006/jnth.1997.2162.  Google Scholar [2] H. Aly and A. Winterhof, On the $k$-error linear complexity over $\mathbb{F}_p$ of Legendre and Sidelnikov sequences, Des. Codes Cryptogr., 40 (2006), 369-374.  doi: 10.1007/s10623-006-0023-5.  Google Scholar [3] J. Bourgain, K. Ford, S. Konyagin and I. E. Shparlinski, On the divisibility of Fermat quotients, Michigan Math. J., 59 (2010), 313-328.  doi: 10.1307/mmj/1281531459.  Google Scholar [4] M. C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38.  doi: 10.4064/aa152-1-3.  Google Scholar [5] Z. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57(2014), 112109, 10 pp. doi: 10.1007/s11432-014-5092-x.  Google Scholar [6] Z. Chen and X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients, Des. Codes Cryptogr., 67 (2013), 317-323.  doi: 10.1007/s10623-012-9608-3.  Google Scholar [7] Z. Chen, X. Du and R. Marzouk, Trace representation of pseudorandom binary sequences derived from Euler quotients, Appl. Algebra Eng. Commun. Comput., 26 (2015), 555-570.  doi: 10.1007/s00200-015-0265-4.  Google Scholar [8] Z. Chen, Z. Niu and C. Wu, On the $k$-error linear complexity of binary sequences derived from polynomial quotients, Sci. China Inf. Sci., 58 (2015), 092107, 15 pp. doi: 10.1007/s11432-014-5220-7.  Google Scholar [9] Z. Chen and A. Winterhof, Additive character sums of polynomial quotients, Proceedings of Theory and Applications of Finite Fields-Fq10, Contemp. Math., 579 (2012), 67-73.  doi: 10.1090/conm/579/11519.  Google Scholar [10] Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7.  doi: 10.1137/130907951.  Google Scholar [11] Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, in Proceedings of the 3rd International Conference on Arithmetic of Finite Fields-WAIFI2010, Lecture Notes in Comput. Sci., 6087 (2010), 73-5. doi: 10.1007/978-3-642-13797-6_6.  Google Scholar [12] T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, North-Holland Mathematical Library, 55. North-Holland Publishing Co., Amsterdam, 1998.  Google Scholar [13] C. Ding, G. Xiao and W. Shan, The Stability Theory of Stream Ciphers, Lecture Notes in Comput. Sci., 561, Springer-Verlag, Berlin, 1991. doi: 10.1007/3-540-54973-0.  Google Scholar [14] X. Du, Z. Chen and L. Hu, Linear complexity of binary sequences derived from Euler quotients with prime-power modulus, Inform. Process. Lett., 112 (2012), 604-609.  doi: 10.1016/j.ipl.2012.04.011.  Google Scholar [15] V. Edemskiy, C. Li, X. Zeng and T. Helleseth, The linear complexity of generalized cyclotomic binary sequences of period pn, Des. Codes Cryptogr., (2018) to appear. https://doi.org/10.1007/s10623-018-0513-2. Google Scholar [16] D. Gómez-Pérez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hungar., 64 (2012), 161-168.  doi: 10.1007/s10998-012-3747-1.  Google Scholar [17] Z. Niu, Z. Chen and X. Du, Linear complexity problems of level sequences of Euler quotients and their related binary sequences, Sci. China Inf. Sci., 59 (2016), 32106. doi: 10.1007/s11432-015-5305-y.  Google Scholar [18] A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discr. Math., 25 (2011), 50-71.  doi: 10.1137/100798466.  Google Scholar [19] M. Sha, The arithmetic of Carmichael quotients, Period. Math. Hungar., 71 (2015), 11-23.  doi: 10.1007/s10998-014-0079-3.  Google Scholar [20] I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043.  doi: 10.1093/qmath/haq028.  Google Scholar [21] I. E. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes, Bull. Aust. Math. Soc., 83 (2011), 456-462.  doi: 10.1017/S000497271000198X.  Google Scholar [22] I. E. Shparlinski, On the value set of Fermat quotients, Proc. Amer. Math. Soc., 140 (2012), 1199-1206.  doi: 10.1090/S0002-9939-2011-11203-6.  Google Scholar [23] I. E. Shparlinski, Fermat quotients: Exponential sums, value set and primitive roots, Bull. Lond. Math. Soc., 43 (2011), 1228-1238.  doi: 10.1112/blms/bdr058.  Google Scholar [24] I. E. Shparlinski and A. Winterhof, Distribution of values of polynomial Fermat quotients, Finite Fields Appl., 19 (2013), 93-104.  doi: 10.1016/j.ffa.2012.10.004.  Google Scholar [25] M. Stamp and C. F. Martin, An algorithm for the $k$-error linear complexity of binary sequences with period $2^n$, IEEE Trans. Inf. Theory, 39 (1993), 1398-1401.  doi: 10.1109/18.243455.  Google Scholar [26] C. Wu, C. Xu, Z. Chen and P. Ke, On error linear complexity of new generalized cyclotomic binary sequences of period $p^2$, CoRR abs/1711.06063v3 (2017) Google Scholar [27] Z. Xiao, X. Zeng, C. Li and T. Helleseth, New generalized cyclotomic binary sequences of period $p^2$, Des. Codes Cryptogr., 86 (2018), 1483-1497.  doi: 10.1007/s10623-017-0408-7.  Google Scholar [28] Z. Ye, P. Ke and C. Wu, A further study on the linear complexity of new binary cyclotomic sequence of length $p^r$, CoRR abs/1712.08886 (2017) Google Scholar

show all references

##### References:
 [1] T. Agoh, K. Dilcher and L. Skula, Fermat quotients for composite moduli, J. Number Theory, 66 (1997), 29-50.  doi: 10.1006/jnth.1997.2162.  Google Scholar [2] H. Aly and A. Winterhof, On the $k$-error linear complexity over $\mathbb{F}_p$ of Legendre and Sidelnikov sequences, Des. Codes Cryptogr., 40 (2006), 369-374.  doi: 10.1007/s10623-006-0023-5.  Google Scholar [3] J. Bourgain, K. Ford, S. Konyagin and I. E. Shparlinski, On the divisibility of Fermat quotients, Michigan Math. J., 59 (2010), 313-328.  doi: 10.1307/mmj/1281531459.  Google Scholar [4] M. C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38.  doi: 10.4064/aa152-1-3.  Google Scholar [5] Z. Chen, Trace representation and linear complexity of binary sequences derived from Fermat quotients, Sci. China Inf. Sci., 57(2014), 112109, 10 pp. doi: 10.1007/s11432-014-5092-x.  Google Scholar [6] Z. Chen and X. Du, On the linear complexity of binary threshold sequences derived from Fermat quotients, Des. Codes Cryptogr., 67 (2013), 317-323.  doi: 10.1007/s10623-012-9608-3.  Google Scholar [7] Z. Chen, X. Du and R. Marzouk, Trace representation of pseudorandom binary sequences derived from Euler quotients, Appl. Algebra Eng. Commun. Comput., 26 (2015), 555-570.  doi: 10.1007/s00200-015-0265-4.  Google Scholar [8] Z. Chen, Z. Niu and C. Wu, On the $k$-error linear complexity of binary sequences derived from polynomial quotients, Sci. China Inf. Sci., 58 (2015), 092107, 15 pp. doi: 10.1007/s11432-014-5220-7.  Google Scholar [9] Z. Chen and A. Winterhof, Additive character sums of polynomial quotients, Proceedings of Theory and Applications of Finite Fields-Fq10, Contemp. Math., 579 (2012), 67-73.  doi: 10.1090/conm/579/11519.  Google Scholar [10] Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7.  doi: 10.1137/130907951.  Google Scholar [11] Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, in Proceedings of the 3rd International Conference on Arithmetic of Finite Fields-WAIFI2010, Lecture Notes in Comput. Sci., 6087 (2010), 73-5. doi: 10.1007/978-3-642-13797-6_6.  Google Scholar [12] T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, North-Holland Mathematical Library, 55. North-Holland Publishing Co., Amsterdam, 1998.  Google Scholar [13] C. Ding, G. Xiao and W. Shan, The Stability Theory of Stream Ciphers, Lecture Notes in Comput. Sci., 561, Springer-Verlag, Berlin, 1991. doi: 10.1007/3-540-54973-0.  Google Scholar [14] X. Du, Z. Chen and L. Hu, Linear complexity of binary sequences derived from Euler quotients with prime-power modulus, Inform. Process. Lett., 112 (2012), 604-609.  doi: 10.1016/j.ipl.2012.04.011.  Google Scholar [15] V. Edemskiy, C. Li, X. Zeng and T. Helleseth, The linear complexity of generalized cyclotomic binary sequences of period pn, Des. Codes Cryptogr., (2018) to appear. https://doi.org/10.1007/s10623-018-0513-2. Google Scholar [16] D. Gómez-Pérez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences, Period. Math. Hungar., 64 (2012), 161-168.  doi: 10.1007/s10998-012-3747-1.  Google Scholar [17] Z. Niu, Z. Chen and X. Du, Linear complexity problems of level sequences of Euler quotients and their related binary sequences, Sci. China Inf. Sci., 59 (2016), 32106. doi: 10.1007/s11432-015-5305-y.  Google Scholar [18] A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discr. Math., 25 (2011), 50-71.  doi: 10.1137/100798466.  Google Scholar [19] M. Sha, The arithmetic of Carmichael quotients, Period. Math. Hungar., 71 (2015), 11-23.  doi: 10.1007/s10998-014-0079-3.  Google Scholar [20] I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043.  doi: 10.1093/qmath/haq028.  Google Scholar [21] I. E. Shparlinski, Bounds of multiplicative character sums with Fermat quotients of primes, Bull. Aust. Math. Soc., 83 (2011), 456-462.  doi: 10.1017/S000497271000198X.  Google Scholar [22] I. E. Shparlinski, On the value set of Fermat quotients, Proc. Amer. Math. Soc., 140 (2012), 1199-1206.  doi: 10.1090/S0002-9939-2011-11203-6.  Google Scholar [23] I. E. Shparlinski, Fermat quotients: Exponential sums, value set and primitive roots, Bull. Lond. Math. Soc., 43 (2011), 1228-1238.  doi: 10.1112/blms/bdr058.  Google Scholar [24] I. E. Shparlinski and A. Winterhof, Distribution of values of polynomial Fermat quotients, Finite Fields Appl., 19 (2013), 93-104.  doi: 10.1016/j.ffa.2012.10.004.  Google Scholar [25] M. Stamp and C. F. Martin, An algorithm for the $k$-error linear complexity of binary sequences with period $2^n$, IEEE Trans. Inf. Theory, 39 (1993), 1398-1401.  doi: 10.1109/18.243455.  Google Scholar [26] C. Wu, C. Xu, Z. Chen and P. Ke, On error linear complexity of new generalized cyclotomic binary sequences of period $p^2$, CoRR abs/1711.06063v3 (2017) Google Scholar [27] Z. Xiao, X. Zeng, C. Li and T. Helleseth, New generalized cyclotomic binary sequences of period $p^2$, Des. Codes Cryptogr., 86 (2018), 1483-1497.  doi: 10.1007/s10623-017-0408-7.  Google Scholar [28] Z. Ye, P. Ke and C. Wu, A further study on the linear complexity of new binary cyclotomic sequence of length $p^r$, CoRR abs/1712.08886 (2017) Google Scholar
 [1] Ahmad El Hajj, Hassan Ibrahim, Vivian Rizik. $BV$ solution for a non-linear Hamilton-Jacobi system. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020405 [2] Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $p$-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039 [3] Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167 [4] Federico Rodriguez Hertz, Zhiren Wang. On $\epsilon$-escaping trajectories in homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 329-357. doi: 10.3934/dcds.2020365 [5] Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $\Lambda$-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328 [6] Jiahao Qiu, Jianjie Zhao. Maximal factors of order $d$ of dynamical cubespaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 601-620. doi: 10.3934/dcds.2020278 [7] Chaoqian Li, Yajun Liu, Yaotang Li. Note on $Z$-eigenvalue inclusion theorems for tensors. Journal of Industrial & Management Optimization, 2021, 17 (2) : 687-693. doi: 10.3934/jimo.2019129 [8] Mathew Gluck. Classification of solutions to a system of $n^{\rm th}$ order equations on $\mathbb R^n$. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246 [9] Luca Battaglia, Francesca Gladiali, Massimo Grossi. Asymptotic behavior of minimal solutions of $-\Delta u = \lambda f(u)$ as $\lambda\to-\infty$. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 681-700. doi: 10.3934/dcds.2020293 [10] Guoyuan Chen, Yong Liu, Juncheng Wei. Nondegeneracy of harmonic maps from ${{\mathbb{R}}^{2}}$ to ${{\mathbb{S}}^{2}}$. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3215-3233. doi: 10.3934/dcds.2019228 [11] Magdalena Foryś-Krawiec, Jiří Kupka, Piotr Oprocha, Xueting Tian. On entropy of $\Phi$-irregular and $\Phi$-level sets in maps with the shadowing property. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1271-1296. doi: 10.3934/dcds.2020317 [12] Lei Liu, Li Wu. Multiplicity of closed characteristics on $P$-symmetric compact convex hypersurfaces in $\mathbb{R}^{2n}$. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378 [13] Wenqiang Zhao, Yijin Zhang. High-order Wong-Zakai approximations for non-autonomous stochastic $p$-Laplacian equations on $\mathbb{R}^N$. Communications on Pure & Applied Analysis, 2021, 20 (1) : 243-280. doi: 10.3934/cpaa.2020265 [14] Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $2^kn$ over $\mathbb{Z}_4+u\mathbb{Z}_4$. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067 [15] Hai Q. Dinh, Bac T. Nguyen, Paravee Maneejuk. Constacyclic codes of length $8p^s$ over $\mathbb F_{p^m} + u\mathbb F_{p^m}$. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020123 [16] Yichen Zhang, Meiqiang Feng. A coupled $p$-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075 [17] Aihua Fan, Jörg Schmeling, Weixiao Shen. $L^\infty$-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363 [18] Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $\mathbb{R}^2$. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020447 [19] Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $p$-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020445 [20] Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $p$ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020442

2019 Impact Factor: 0.734