Алгоритм решения систем линейных уравнений в поле Fpk

Loading...
Thumbnail Image
Date
2019
Authors
Крывый, Сергей
Гогерчак, Григорий
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Рассматривается задача построения базиса множества решений систем линейных уравнений (СЛУ) над конечным полем Fpk Поле Fpk строится как Fp расширение поля вычетов Fp с помощью неприводимого в поле Fp полинома степени к, где р — простое число.
Basic theoretical concepts of finite fields area are considered, including concepts of residue field and extension of residue field. The algorithms necessary for constructing extensions ef residue fields are given: a Rabin test for checking ir- reducibility of polynomials, its application to irreducible polynomials search, algorithm for construction of addition and multiplication tables by modulo of irreducible polynomial, ways of opposite and inverse elements calculation based on these tables. Ways of efficiency improvement for irreducible polynomials search with probabilistic approach are introduced. The features of the numbering of elements extensions of finite fields Fpk and numbering choice influence on the efficiency of performing basic operations on field elements, including search for opposite and inverse elements, are described. An algorithm for constructing a basis for a set of solutions of homogeneous systems of linear equations and an algorithm for building of common solution ef inhomogeneous systems of linear eqations over a finite field Fpk as a sum of linear combination of corresponding homogeneous system set of solutions basis and partial solution of inhomogeneous system are presented. Proposed algorithms have polinomial estimations of time complexity as demonstrated by tables for different systems of equations and different parameters of these algorithms. Applications for systems of linear equations in the mathematical safe problem is considered. Classic formulation of this problem and its adaptation for the field F k is proposed. Various cases of p the representation of a mathematical safe: using matrixes and graphs are described. Conditions for solution existence, algorithms for solving a problem in these cases, and their effectiveness in the field F k are considered. Possible appplications of systems of equations over the field Fpk coding and cryptopgraphy are indicated.
Description
Keywords
системы диофантовых уравнений, расширение поля, задача о математическом сейфе, статья, systems of diophantine equations, field extension, math safe problem
Citation
Крывый С. Л. Алгоритм решения систем линейных уравнений в поле Fpk / С. Л. Крывый, Г. И. Гогерчак // Проблемы управления и информатики. - 2019. - № 5. - C. 5-24.