Article Contents

2016, Volume 10, Issue 4: 743-752. Doi: 10.3934/amc.2016038

This issue Previous Article Further results on semi-bent functions in polynomial form Next Article A note on diagonal and Hermitian hypersurfaces

An extension of binary threshold sequences from Fermat quotients

1.
College of Mathematics and Statistics, Northwest Normal University, Lanzhou, Gansu 730070
2.
School of Mathematics, Putian University, Putian, Fujian 351100

Received: September 2014

Published: November 2016

Abstract / Introduction Related Papers Cited by

Abstract

We extend the construction of $p^2$-periodic binary threshold sequences derived from Fermat quotients to the $d$-ary case where $d$ is an odd prime divisor of $p-1$, and then by defining cyclotomic classes modulo $p^{2}$, we present exact values of the linear complexity under the condition of $d^{p-1}\not \equiv 1 \pmod {p^2}$. Also, we extend the results to the Euler quotients modulo $p^{r}$ with odd prime $p$ and $r \geq 2$. The linear complexity is very close to the period and is of desired value for cryptographic purpose. The results extend the linear complexity of the corresponding $d$-ary sequences when $d$ is a primitive root modulo $p^2$ in earlier work. Finally, partial results for the linear complexity of the sequences when $d^{p-1} \equiv 1 \pmod {p^2}$ is given.

Keywords:

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

Citation:

Related Papers

Cited by

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]	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.
[3]	Z. Chen, L. Hu and X. Du, Linear complexity of some binary sequences derived from Fermat quotients, China Commun., 9 (2012), 105-108.doi: 10.1007/s10623-012-9608-3.
[4]	Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients, in Proc. WAIFI 2010, Springer-Verlag, Heidelberg, 2010, 73-85.doi: 10.1007/978-3-642-13797-6_6.
[5]	Z. Chen and A. Winterhof, On the distribution of pseudorandom numbers and vectors derived from Euler-Fermat quotients, Int. J. Number Theory, 8 (2012), 631-641.doi: 10.1142/S1793042112500352.
[6]	R. Crandall, K. Dilcher and C. Pomerance, A search for Wieferich and Wilson primes, Math. Comp., 66 (1997), 433-449.doi: 10.1090/S0025-5718-97-00791-6.
[7]	A. Cunningham, Period-lengths of circulates, Messenger Math., 29 (1900), 145-179.
[8]	X. Du, Z. Chen and L. Hu, Linear complexity of binary sequences derived from Euler quotients with prime-power modulus, Inform. Proc. Letters, 112 (2012), 604-609.doi: 10.1016/j.ipl.2012.04.011.
[9]	X. Du, A. Klapper and Z. Chen, Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations, Inform. Proc. Letters, 112 (2012), 233-237.doi: 10.1016/j.ipl.2011.11.017.
[10]	R. Ernvall and T. Metsänkylä, On the p-divisibility of Fermat quotients, Math. Comp., 66 (1997), 1353-1365.doi: 10.1090/S0025-5718-97-00843-0.
[11]	D. Gomez 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.
[12]	A. Granville, Some conjectures related to Fermat's Last Theorem, in Number Theory, Walter de Gruyter, Berlin, 1990, 177-192.
[13]	W. Keller and J. Richstein, Prime solutions $p$ of $a^{p-1}\equiv 1$ (mod $p^2$) for prime bases $a$, Math. Comput., 74 (2005), 927-936.doi: 10.1090/S0025-5718-04-01666-7.
[14]	R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, MA, 1983.
[15]	J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127.
[16]	A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discrete Math., 25 (2011), 50-71.doi: 10.1137/100798466.
[17]	A. Winterhof, Linear complexity and related complexity measures, in Selected Topics in Information and Coding Theory, World Scientic, 2010, 3-40.doi: 10.1142/9789812837172_0001.
[18]	M. Sha, The arithmetic of Carmichael quotients, preprint, arXiv:1108.2579 doi: 10.1007/s10998-014-0079-3.
[19]	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.
[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, Fermat quotients: Exponential sums, value set and primitive roots, Bull. London Math. Soc., 43 (2011), 1228-1238.doi: 10.1112/blms/bdr058.
[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.