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. AgohK. 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. BourgainK. FordS. 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. ChenX. 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. DuZ. 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. XiaoX. ZengC. 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. AgohK. 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. BourgainK. FordS. 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. ChenX. 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. DuZ. 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. XiaoX. ZengC. 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]

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]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Zalman Balanov, Yakov Krasnov. On good deformations of $ A_m $-singularities. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1851-1866. doi: 10.3934/dcdss.2019122

[19]

Pak Tung Ho. Prescribing the $ Q' $-curvature in three dimension. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2285-2294. doi: 10.3934/dcds.2019096

[20]

Eun-Kyung Cho, Cunsheng Ding, Jong Yoon Hyun. A spectral characterisation of $ t $-designs and its applications. Advances in Mathematics of Communications, 2019, 13 (3) : 477-503. doi: 10.3934/amc.2019030

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (49)
  • HTML views (281)
  • Cited by (0)

[Back to Top]