Bulletin of Irkutsk State University. Series Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Bulletin of Irkutsk State University. Series Mathematics:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Bulletin of Irkutsk State University. Series Mathematics, 2014, Volume 10, Pages 3–12 (Mi iigum205)  

This article is cited in 2 scientific papers (total in 2 papers)

On upper bound of the complexity of quasi polynomial representations of functions over finite fields

A. S. Baliuk

Irkutsk State University, 1, K. Marx st., Irkutsk, 664003
Full-text PDF (257 kB) Citations (2)
References:
Abstract: Representations of functions over finite fields, including polynomial representations, are being actively investigated. The complexity of such representations is one of main directions of research.
This paper is about quasi polynomial complexity of functions over finite fields. Quasi polynomial can be considered as a regular polynomial with the following transformation: every occurence $x_i^0, \dots, x_i^{k-1}$ of selected variable $x_i$ is replaced by a function from a set $\{g_0(x_i), \dots, g_{k-1}(x_i)\}$ of linearly independent unary functions.
The number of terms, the number of occurences of variables, or the degree of a polynomial are usually used as a measure of complexity. In the case of quasi polynomials one can use the number of terms as a natural measure of complexity, while further generalization are required for the number of occurences of variables and the degree of a polynomial. In this paper the number of terms is used as a measure of complexity. Previously, the upper bound of such a complexity was known for polynomials over finite fields of prime order. Namely, the quasi polynomial complexity of $n$-ary function over finite field of prime order $k$ is at most $\frac{k}{k+1}k^n$.
In this paper an upper bound for the quasi polynomial complexity of functions over finite fields of arbitrary order $q$ has been obtained, which significantly improves previously known upper bound for modulo prime quasi polynomials, if $q \geqslant 3$. Namely, the quasi polynomial complexity of any $n$-ary function over finite field of order $q$ is at most $ \frac{q-1}{q-q^{1-q}}q^n$.
Keywords: finite field, polynomial, quasi polynomial, complexity.
Document Type: Article
UDC: 519.715
Language: Russian
Citation: A. S. Baliuk, “On upper bound of the complexity of quasi polynomial representations of functions over finite fields”, Bulletin of Irkutsk State University. Series Mathematics, 10 (2014), 3–12
Citation in format AMSBIB
\Bibitem{Bal14}
\by A.~S.~Baliuk
\paper On upper bound of the complexity of quasi polynomial representations of functions over finite fields
\jour Bulletin of Irkutsk State University. Series Mathematics
\yr 2014
\vol 10
\pages 3--12
\mathnet{http://mi.mathnet.ru/iigum205}
Linking options:
  • https://www.mathnet.ru/eng/iigum205
  • https://www.mathnet.ru/eng/iigum/v10/p3
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Statistics & downloads:
    Abstract page:149
    Full-text PDF :45
    References:34
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025