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

Zhixiong Chen; Vladimir Edemskiy; Pinhui Ke; Chenhuang Wu

doi:10.3934/amc.2018047

Article Contents

2018, Volume 12, Issue 4: 805-816. Doi: 10.3934/amc.2018047

This issue Previous Article Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases Next Article Binary subspace codes in small ambient spaces

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)
* Corresponding author: Zhixiong Chen (ptczx@126.com)

Received: February 28, 2018

Published: October 2018

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

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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

Keywords:

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

Citation:

Full Text(HTML)

Related Papers

Cited by

References

	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 pⁿ, 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)