# 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] Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016 [2] Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036 [3] Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369 [4] Haisheng Tan, Liuyan Liu, Hongyu Liang. Total $\{k\}$-domination in special graphs. Mathematical Foundations of Computing, 2018, 1 (3) : 255-263. doi: 10.3934/mfc.2018011 [5] Ekta Mittal, Sunil Joshi. Note on a $k$-generalised fractional derivative. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 797-804. doi: 10.3934/dcdss.2020045 [6] Edcarlos D. Silva, José Carlos de Albuquerque, Uberlandio Severo. On a class of linearly coupled systems on $\mathbb{R}^N$ involving asymptotically linear terms. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3089-3101. doi: 10.3934/cpaa.2019138 [7] 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, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020039 [8] Tuan Anh Dao, Michael Reissig. $L^1$ estimates for oscillating integrals and their applications to semi-linear models with $\sigma$-evolution like structural damping. Discrete & Continuous Dynamical Systems - A, 2019, 39 (9) : 5431-5463. doi: 10.3934/dcds.2019222 [9] Daniel Heinlein, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. A subspace code of size $\bf{333}$ in the setting of a binary $\bf{q}$-analog of the Fano plane. Advances in Mathematics of Communications, 2019, 13 (3) : 457-475. doi: 10.3934/amc.2019029 [10] Thomas French. Follower, predecessor, and extender set sequences of $\beta$-shifts. Discrete & Continuous Dynamical Systems - A, 2019, 39 (8) : 4331-4344. doi: 10.3934/dcds.2019175 [11] Adam Kanigowski, Federico Rodriguez Hertz, Kurt Vinhage. On the non-equivalence of the Bernoulli and $K$ properties in dimension four. Journal of Modern Dynamics, 2018, 13: 221-250. doi: 10.3934/jmd.2018019 [12] Silvia Frassu. Nonlinear Dirichlet problem for the nonlocal anisotropic operator $L_K$. Communications on Pure & Applied Analysis, 2019, 18 (4) : 1847-1867. doi: 10.3934/cpaa.2019086 [13] Vladimir Chepyzhov, Alexei Ilyin, Sergey Zelik. Strong trajectory and global $\mathbf{W^{1,p}}$-attractors for the damped-driven Euler system in $\mathbb R^2$. Discrete & Continuous Dynamical Systems - B, 2017, 22 (5) : 1835-1855. doi: 10.3934/dcdsb.2017109 [14] Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297 [15] Pak Tung Ho. Prescribing $Q$-curvature on $S^n$ in the presence of symmetry. Communications on Pure & Applied Analysis, 2020, 19 (2) : 715-722. doi: 10.3934/cpaa.2020033 [16] Wenqiang Zhao. Random dynamics of non-autonomous semi-linear degenerate parabolic equations on $\mathbb{R}^N$ driven by an unbounded additive noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2499-2526. doi: 10.3934/dcdsb.2018065 [17] Jaume Llibre, Y. Paulina Martínez, Claudio Vidal. Phase portraits of linear type centers of polynomial Hamiltonian systems with Hamiltonian function of degree 5 of the form $H = H_1(x)+H_2(y)$. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 75-113. doi: 10.3934/dcds.2019004 [18] Yeping Li, Jie Liao. Stability and $L^{p}$ convergence rates of planar diffusion waves for three-dimensional bipolar Euler-Poisson systems. Communications on Pure & Applied Analysis, 2019, 18 (3) : 1281-1302. doi: 10.3934/cpaa.2019062 [19] Sugata Gangopadhyay, Goutam Paul, Nishant Sinha, Pantelimon Stǎnicǎ. Generalized nonlinearity of $S$-boxes. Advances in Mathematics of Communications, 2018, 12 (1) : 115-122. doi: 10.3934/amc.2018007 [20] Gyula Csató. On the isoperimetric problem with perimeter density $r^p$. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2729-2749. doi: 10.3934/cpaa.2018129

2018 Impact Factor: 0.879