EN|RU
|
![]() |
Volume 29, No 1, 2022, P. 56-73 UDC 519.712.3+512.622+510.52
Keywords: $p$-valued function (function of $p$-valued logic), finite field, prime field, polynomial over a field, periodicity, algorithm, complexity. DOI: 10.33048/daio.2022.29.727 Svetlana N. Selezneva 1 Received November 14, 2021 References[1] O. A. Logachyov, A. A. Sal’nikov, S. V. Smyshlyaev, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptology (MTsNMO, Moscow, 2012) [Russian].[2] E. Dawson and C.-K. Wu, On the linear structure of symmetric Boolean functions, Australas. J. Comb. 16, 239–243 (1997). [3] V. K. Leont’ev, Certain problems associated with Boolean polynomials, Zh. Vychisl. Mat. Mat. Fiz. 39 (6), 1045–1054 (1999) [Russian] [Comput. Math. Math. Phys. 39 (6), 1006–1015 (1999)]. [4] S. N. Selezneva, On the complexity of completeness recognition of systems of Boolean functions realized in the form of Zhegalkin polynomials, Diskretn. Mat. 9 (4), 24–31 (1997) [Russian] [Discrete Math. Appl. 7 (6), 565–572 (1997)]. [5] S. N. Selezneva, A polynomial algorithm for the recognition of belonging a function of $k$-valued logic realized by a polynomial to precomplete classes of selfdual functions, Diskretn. Mat. 10 (3), 64–72 (1998) [Russian] [Discrete Math. Appl. 8 (5), 483–492 (1998)]. [6] D. Yu. Grigoriev, Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines, Theor. Comput. Sci. 180 (1–2), 217–228 (1997). [7] D. Yu. Grigoriev, Testing the shift-equivalence of polynomials using quantum machines, Itogi Nauki Tekh., Ser. Sovrem. Mat. Pril. 34, 98–116 (1996) [Russian] [J. Math. Sci 82 (1), 3184–3193 (1996)]. [8] S. N. Selezneva, On searching periods of Zhegalkin polynomials, Diskretn. Mat. 33 (3), 107–120 (2021) [Russian]. [9] R. Lidl and H. Niederreiter, Finite Fields (Camb. Univ. Press, Cambridge, 1985; Mir, Moscow, 1988 [Russian]). [10] S. V. Yablonskii, Introduction to Discrete Mathematics (Vysshaya Shkola, Moscow, 2001) [Russian]. [11] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]). |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|