Linear Complexity and Polynomial Degree of a Function Over a Finite Field

Wilfried Meidl () and Arne Winterhof ()
Additional contact information
Wilfried Meidl: Austrian Academy of Sciences, Institute of Discrete Mathematics
Arne Winterhof: Austrian Academy of Sciences, Institute of Discrete Mathematics

A chapter in Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, 2002, pp 229-238 from Springer

Abstract: Abstract We compare the complexities of the polynomial representation and the periodic sequence representation of a function over a finite field in the complexity measures degree and linear complexity. We prove a sharp inequality describing the relation between degree and linear complexity. These investigations are motivated by results on some cryptographic functions. In particular, as an application of the above mentioned inequality we prove new lower bounds on the linear complexity of sequences related to the Diffie-Hellman mapping.

Date: 2002
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-59435-9_18

Ordering information: This item can be ordered from
http://www.springer.com/9783642594359

DOI: 10.1007/978-3-642-59435-9_18

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().