АЛГОРИТМ РОЗВʼЯЗКУ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ У ПОЛІ Fpk
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 irreducibility of polynomials, its application to irreducib...
Saved in:
| Date: | 2025 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2025
|
| Subjects: | |
| Online Access: | https://jais.net.ua/index.php/files/article/view/676 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Problems of Control and Informatics |
Institution
Problems of Control and Informatics| Summary: | 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 irreducibility 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 Fpk is proposed. Various cases of the representation of a mathematical safe: using matrixes and graphs are described. Сonditions for solution existence, algorithms for solving a problem in these cases, and their effectiveness in the field Fpk are considered. Possible applications of systems of equations over the field Fpk in coding and cryptography are indicated. |
|---|