Article Contents
Article Contents

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

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

Mathematics Subject Classification: Primary: 94A55, 94A60; Secondary: 65C10.

 Citation:

•  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. 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. 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. M. C. Chang , Short character sums with Fermat quotients, Acta Arith., 152 (2012) , 23-38.  doi: 10.4064/aa152-1-3. 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. 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. 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. 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. 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. Z. Chen  and  A. Winterhof , Interpolation of Fermat quotients, SIAM J. Discr. Math., 28 (2014) , 1-7.  doi: 10.1137/130907951. 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. T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, North-Holland Mathematical Library, 55. North-Holland Publishing Co., Amsterdam, 1998. 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. 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. 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. 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. 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. A. Ostafe  and  I. E. Shparlinski , Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discr. Math., 25 (2011) , 50-71.  doi: 10.1137/100798466. M. Sha , The arithmetic of Carmichael quotients, Period. Math. Hungar., 71 (2015) , 11-23.  doi: 10.1007/s10998-014-0079-3. I. E. Shparlinski , Character sums with Fermat quotients, Quart. J. Math., 62 (2011) , 1031-1043.  doi: 10.1093/qmath/haq028. 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. 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. 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. 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. 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. 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) 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. 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)

• on this site

/