# 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. [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. [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. [4] M. C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38. doi: 10.4064/aa152-1-3. [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. [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. [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. [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. [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. [10] Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7. doi: 10.1137/130907951. [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. [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. [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. [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. [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. [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. [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. [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. [19] M. Sha, The arithmetic of Carmichael quotients, Period. Math. Hungar., 71 (2015), 11-23. doi: 10.1007/s10998-014-0079-3. [20] I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043. doi: 10.1093/qmath/haq028. [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. [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. [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. [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. [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. [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) [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. [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)

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. [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. [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. [4] M. C. Chang, Short character sums with Fermat quotients, Acta Arith., 152 (2012), 23-38. doi: 10.4064/aa152-1-3. [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. [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. [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. [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. [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. [10] Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014), 1-7. doi: 10.1137/130907951. [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. [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. [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. [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. [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. [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. [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. [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. [19] M. Sha, The arithmetic of Carmichael quotients, Period. Math. Hungar., 71 (2015), 11-23. doi: 10.1007/s10998-014-0079-3. [20] I. E. Shparlinski, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043. doi: 10.1093/qmath/haq028. [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. [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. [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. [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. [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. [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) [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. [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)
 [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] 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 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] 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 [10] 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 [11] Teresa Alberico, Costantino Capozzoli, Luigi D'Onofrio, Roberta Schiattarella. $G$-convergence for non-divergence elliptic operators with VMO coefficients in $\mathbb R^3$. Discrete & Continuous Dynamical Systems - S, 2019, 12 (2) : 129-137. doi: 10.3934/dcdss.2019009 [12] Mohan Mallick, R. Shivaji, Byungjae Son, S. Sundar. Bifurcation and multiplicity results for a class of $n\times n$ $p$-Laplacian system. Communications on Pure & Applied Analysis, 2018, 17 (3) : 1295-1304. doi: 10.3934/cpaa.2018062 [13] 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 [14] Chengxiang Wang, Li Zeng, Wei Yu, Liwei Xu. Existence and convergence analysis of $\ell_{0}$ and $\ell_{2}$ regularizations for limited-angle CT reconstruction. Inverse Problems & Imaging, 2018, 12 (3) : 545-572. doi: 10.3934/ipi.2018024 [15] Yonglin Cao, Yuan Cao, Hai Q. Dinh, Fang-Wei Fu, Jian Gao, Songsak Sriboonchitta. Constacyclic codes of length $np^s$ over $\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}$. Advances in Mathematics of Communications, 2018, 12 (2) : 231-262. doi: 10.3934/amc.2018016 [16] Tadahisa Funaki, Yueyuan Gao, Danielle Hilhorst. Convergence of a finite volume scheme for a stochastic conservation law involving a $Q$-brownian motion. Discrete & Continuous Dynamical Systems - B, 2018, 23 (4) : 1459-1502. doi: 10.3934/dcdsb.2018159 [17] Qianying Xiao, Zuohuan Zheng. $C^1$ weak Palis conjecture for nonsingular flows. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 1809-1832. doi: 10.3934/dcds.2018074 [18] María Anguiano, Alain Haraux. The $\varepsilon$-entropy of some infinite dimensional compact ellipsoids and fractal dimension of attractors. Evolution Equations & Control Theory, 2017, 6 (3) : 345-356. doi: 10.3934/eect.2017018 [19] Sanjiban Santra. On the positive solutions for a perturbed negative exponent problem on $\mathbb{R}^3$. Discrete & Continuous Dynamical Systems - A, 2018, 38 (3) : 1441-1460. doi: 10.3934/dcds.2018059 [20] Lin Du, Yun Zhang. $\mathcal{H}_∞$ filtering for switched nonlinear systems: A state projection method. Journal of Industrial & Management Optimization, 2018, 14 (1) : 19-33. doi: 10.3934/jimo.2017035

2017 Impact Factor: 0.564

Article outline