Linear complexity of Legendre-polynomial quotients

Linear complexity of Legendre-polynomial quotients

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Let p be an odd prime and be a positive integer. The authors continue to investigate the binary sequence over defined from polynomial quotients by modulo p. The is generated in terms of which equals to the Legendre symbol of for u ≥ 0. In an earlier work, the linear complexity of was determined for (i.e. the case of Fermat quotients) under the assumption of . In this work, they develop a naive trick to calculate all possible values on the linear complexity of for all under the same assumption. They also state that the case of larger can be reduced to that of . So far, the linear complexity is almost determined for all kinds of Legendre-polynomial quotients.


    1. 1)
      • 1. Ostafe, A., Shparlinski, I.E.: ‘Pseudorandomness and dynamics of Fermat quotients’, SIAM J. Discrete Math., 2011, 25, pp. 5071.
    2. 2)
      • 2. Chen, Z.: ‘Trace representation and linear complexity of binary sequences derived from Fermat quotients’, Sci. China Inf. Sci., 2014, 57, (11), pp. 110.
    3. 3)
      • 3. Chen, Z., Du, X.: ‘On the linear complexity of binary threshold sequences derived from Fermat quotients’, Des. Codes Cryptogr., 2013, 67, pp. 317323.
    4. 4)
      • 4. Chen, Z., Gómez-Pérez, D.: ‘Linear complexity of binary sequences derived from polynomial quotients’. Sequences and their Applications-SETA 2012, Springer, Berlin, 2012 (LNCS, 7280), pp. 181189.
    5. 5)
      • 5. Chen, Z., Niu, Z., Wu, C.: ‘On the k-error linear complexity of binary sequences derived from polynomial quotients’, Sci. China Inf. Sci., 2015, 58, (9), pp. 115.
    6. 6)
      • 6. Du, X., Klapper, A., Chen, Z.: ‘Linear complexity of pseudorandom sequences generated by Fermat quotients and their generalizations’, Inf. Process. Lett., 2012, 112, pp. 233237.
    7. 7)
      • 7. Chen, Z., Winterhof, A.: ‘Additive character sums of polynomial quotients’. Theory and Applications of Finite Fields-Fq10, Contemporary Mathematics, 579, American Mathematical Society, Providence, RI, 2012, pp. 6773.
    8. 8)
      • 8. Aly, H., Winterhof, A.: ‘Boolean functions derived from Fermat quotients’, Cryptogr. Commun., 2011, 3, pp. 165174.
    9. 9)
      • 9. Chen, Z., Winterhof, A.: ‘Polynomial quotients: distribution of values and Waring's problem’, Acta Arithmetica, 2015, 170, (2), pp. 121134.
    10. 10)
      • 10. Gómez-Pérez, D., Winterhof, A.: ‘Multiplicative character sums of Fermat quotients and pseudorandom sequences’, Period. Math. Hung., 2012, 64, pp. 161168.
    11. 11)
      • 11. Sha, M.: ‘The arithmetic of Carmichael quotients’, Period. Math. Hung., 2015, 71, (1), pp. 1123.
    12. 12)
      • 12. Akbary, A., Siavashi, S.: ‘The largest known Wieferich numbers’, Integers, 2018, 18, (#A3), pp. 16.
    13. 13)
      • 13. Crandall, R., Dilcher, K., Pomerance, C.: ‘A search for Wieferich and Wilson primes’, Math. Comput., 1997, 66, (217), pp. 433449.
    14. 14)
      • 14. Cusick, T.W., Ding, C., Renvall, A.: ‘Stream ciphers and number theory’ (North-Holland Mathematical Library 55, Elsevier/North-Holland, 1998), revised edition, vol. 66 (The North-Holland Mathematical Library, 2004).

Related content

This is a required field
Please enter a valid email address