Advanced Search
Article Contents
Article Contents

An extension of binary threshold sequences from Fermat quotients

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 94A55, 94A60; Secondary: 65C10.


    \begin{equation} \\ \end{equation}
  • [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.


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


    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.


    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.


    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.


    A. Cunningham, Period-lengths of circulates, Messenger Math., 29 (1900), 145-179.


    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.


    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.


    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.


    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.


    A. Granville, Some conjectures related to Fermat's Last Theorem, in Number Theory, Walter de Gruyter, Berlin, 1990, 177-192.


    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.


    R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, MA, 1983.


    J. L. Massey, Shift register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127.


    A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients, SIAM J. Discrete Math., 25 (2011), 50-71.doi: 10.1137/100798466.


    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.


    M. Sha, The arithmetic of Carmichael quotients, preprint, arXiv:1108.2579 doi: 10.1007/s10998-014-0079-3.


    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, Character sums with Fermat quotients, Quart. J. Math., 62 (2011), 1031-1043.doi: 10.1093/qmath/haq028.


    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.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(227) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint