Inscrição na biblioteca: Guest
SJR: 0.275 SNIP: 0.59 CiteScore™: 0.8

ISSN Imprimir: 1064-2315
ISSN On-line: 2163-9337

# Journal of Automation and Information Sciences

DOI: 10.1615/JAutomatInfScien.v51.i10.10
pages 1-22

## Algorithms for Solving Systems of Linear Equations in the Field Fpk

Sergey L. Kryvyi
Kiev National Taras Shevchenko University, Kiev
H. I. Hoherchak
Scientific and Methodological Center for Natural Mathematical Education and Technologies of Institute of Postgraduate Pedagogical Education of Borys Grinchenko Kiev University, Kiev

### RESUMO

Consideration is given to basic theoretical concepts of finite fields areas including concepts and extensions of residue fields. The algorithms necessary for constructing extensions of residue fields are given: Rabin test for checking irreducibility of polynomials, its application to irreducible polynomial search, the algorithm for construction of tables of addition and multiplication modulo irreducible polynomial, the ways of opposite and inverse elements calculations based on these tables. The ways of improving the efficiency of searching for irreducible polynomials using the probabilistic approach are introduced. The features of the numbering the elements of extensions of finite fields Fpk and the numbering choice influence on the efficiency of performing basic operations with field elements including search for the opposite and inverse elements are described. The algorithm for constructing the basis for a set of solutions of systems of linear homogeneous equations and the algorithm for constructing a common solution of the systems of linear inhomogeneous equations over the extension of finite field Fpk as a sum of combinations of the basis vectors of the set of solutions of the corresponding homogeneous system and the partial solution of the inhomogeneous system are proposed. These algorithms have the polynomial estimators of time complexity demonstrated by tables for concrete examples of systems of linear equations and different parameters of the algorithms. Consideration is given to application of the algorithms for solving systems of linear equations to the mathematical safe problem, its classical formulation and adaptation to the field Fpk . Various cases of mathematical safe representation using matrices and graphs are described. The conditions for solution existence, the algorithms for solving the problem in these cases and their efficiency in the field Fpk are considered. Possible applications of the system of equations over the field Fpk in coding and cryptography are indicated.

### Referências

1. Donets G.A., Solving the safe problem on (0, 1)-matrices, Kibernetika i sistemnyi analiz, 2002, No. 1, 98-105 .

2. Kryvyi S.L., Algorithm for solving the systems of linear Diophantine equations in residue field, Kibernetika i sistemnyi analiz, 2007, No. 2, 15-23 .

3. Kryvyi S.L., Linear Diophantine constraints and their application [in Ukrainian], Bukrek, Chernivtsi-Kyiv, 2015 .

4. Sergienko I.V., Kryvyi S.L., Provotar O.I., Algebraic aspects of information technologies (ch. 1) [in Ukrainian], Interservis, Kyiv, 2018 .

5. Lidl R., Niederreiter H., Finite fields. 2nd edition, Cambridge University Press, 1996, DOI: https://doi.org/10.1017/CB09780511525926 .

6. Rabin M.O., Probabilistic algorithms in finite fields, SIAM Journal on Computing, 1980, 2, No. 9, 273-280, DOI: https://doi.org/10.1137/0209024 .

7. Gavrilkevich M.V., Solodovnikov V.I., Efficient algorithms for solving problems of linear algebra over the field of two elements, Obozreniepriklad. promyshl. matem., 1995, 2, No. 3, 400-437 .

8. Alekseychuk A.N., Ignatenko S.M., Optimization method of algorithms for solving systems of linear equations with distorted right-hand side over the ring of residue modulo 2n, Reyestratsiya, zberigannya i obrobka danyh, 2005, 7, No. 1, 21-29 .

### Articles with similar content:

Models and Methods of Semi-Infinite Optimization Inverse Heat-Conduction Problems
Heat Transfer Research, Vol.37, 2006, issue 3
E. Ya. Rapoport, Yu. E. Pleshivtseva
Principles of Designing PDC Algorithms for Intractable Combinatorial Problems
Journal of Automation and Information Sciences, Vol.29, 1997, issue 2-3
L. A. Pavlova , Alexander A. Pavlov
Algorithm for Solving a Continuous Problem of Optimal Partitioning with Neurolinguistic Identification of Functions in Target Functional
Journal of Automation and Information Sciences, Vol.50, 2018, issue 3
Elena M. Kiseleva, Olga M. Prytomanova , Sergey V. Zhuravel
Algorithm for Constructing Voronoi Diagrams with Optimal Placement of Generator Points Based on Theory of Optimal Set Partitioning
Journal of Automation and Information Sciences, Vol.52, 2020, issue 3
Elena M. Kiseleva, Olga M. Prytomanova , Lyudmila L. Hart
Generalized Algorithm of Recognition of a Prefractal Graph
Journal of Automation and Information Sciences, Vol.37, 2005, issue 4
Elena V. Bobyleva, Elena M. Kiseleva