Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






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


Diskretn. Anal. Issled. Oper., 2020, Volume 27, Issue 1, Pages 88–109 (Mi da945)  

On the annihilators of Boolean polynomials

V. K. Leontievab, E. N. Gordeevb

a Dorodnitsyn Computing Center, 42 Vavilov Street, 119991 Moscow, Russia
b Bauman Moscow State Technical University, 5 Vtoraya Baumanskaya Street, 105005 Moscow, Russia

Abstract: Boolean functions in general and Boolean polynomials (Zhegalkin polynomials or algebraic normal forms (ANF)) in particular are the subject of theoretical and applied studies in various fields of computer science. This article addresses the linear operators of the space of Boolean polynomials in $n$ variables, which leads to the results on the problem of finding the minimum annihilator degree for a given Boolean polynomial. This problem is topical in various analytical and algorithmic aspects of cryptography. Boolean polynomials and their combinatorial properties are under study in discrete analysis. The theoretical foundations of information security include the study of the properties of Boolean polynomials in connection with cryptography. In this article, we prove a theorem on the minimum annihilator degree. The class of Boolean polynomials is described for which the degree of an annihilator is at most $1$. We give a few combinatorial characteristics related to the properties of the space of Boolean polynomials. Some estimates of the minimum degree of an annihilator are given. We also consider the case of symmetric polynomials. Bibliogr. 26.

Keywords: Boolean polynomial, symmetric polynomial, annihilator, linear operator, cryptosystem.

Funding Agency Grant Number
Ministry of Science and Higher Education of the Russian Federation 0063-2016-0003
Russian Foundation for Basic Research 17-01-00300_а
This research is supported by Ministry of Science and Higher Education of Russian Federation (State Assignment 0063–2016–0003) and Russian Foundation for Basic Research (Project 19–07–00895).


DOI: https://doi.org/10.33048/daio.2020.27.646

Full text: PDF file (372 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2020, 14:1, 162–175

UDC: 519.16
Received: 24.01.2019
Revised: 10.09.2019
Accepted:25.09.2019

Citation: V. K. Leontiev, E. N. Gordeev, “On the annihilators of Boolean polynomials”, Diskretn. Anal. Issled. Oper., 27:1 (2020), 88–109; J. Appl. Industr. Math., 14:1 (2020), 162–175

Citation in format AMSBIB
\Bibitem{LeoGor20}
\by V.~K.~Leontiev, E.~N.~Gordeev
\paper On the annihilators of Boolean polynomials
\jour Diskretn. Anal. Issled. Oper.
\yr 2020
\vol 27
\issue 1
\pages 88--109
\mathnet{http://mi.mathnet.ru/da945}
\crossref{https://doi.org/10.33048/daio.2020.27.646}
\transl
\jour J. Appl. Industr. Math.
\yr 2020
\vol 14
\issue 1
\pages 162--175
\crossref{https://doi.org/10.1134/S1990478920010159}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85082389615}


Linking options:
  • http://mi.mathnet.ru/eng/da945
  • http://mi.mathnet.ru/eng/da/v27/i1/p88

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Number of views:
    This page:146
    Full text:8
    References:9
    First page:12

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021