Lower Bounds of Complexity for Polarized Polynomials over Finite Fields
- Authors: Baliuk A.S.1, Zinchenko A.S.2
-
Affiliations:
- LLC Informatics of Medicine
- Irkutsk State University
- Issue: Vol 60, No 1 (2019)
- Pages: 1-9
- Section: Article
- URL: https://journals.rcsi.science/0037-4466/article/view/172158
- DOI: https://doi.org/10.1134/S0037446619010014
- ID: 172158
Cite item
Abstract
We obtain an efficient lower bound of complexity for n-ary functions over a finite field of arbitrary order in the class of polarized polynomials. The complexity of a function is defined as the minimal possible number of nonzero terms in a polarized polynomial realizing the function.
About the authors
A. S. Baliuk
LLC Informatics of Medicine
Author for correspondence.
Email: alexanderbalyuk@gmail.com
Russian Federation, Irkutsk
A. S. Zinchenko
Irkutsk State University
Author for correspondence.
Email: azinchenko@gmail.com
Russian Federation, Irkutsk