Inscrição na biblioteca: Guest
Portal Digital Begell Biblioteca digital da Begell eBooks Diários Referências e Anais Coleções de pesquisa
Journal of Automation and Information Sciences
SJR: 0.275 SNIP: 0.59 CiteScore™: 0.8

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

Volume 52, 2020 Volume 51, 2019 Volume 50, 2018 Volume 49, 2017 Volume 48, 2016 Volume 47, 2015 Volume 46, 2014 Volume 45, 2013 Volume 44, 2012 Volume 43, 2011 Volume 42, 2010 Volume 41, 2009 Volume 40, 2008 Volume 39, 2007 Volume 38, 2006 Volume 37, 2005 Volume 36, 2004 Volume 35, 2003 Volume 34, 2002 Volume 33, 2001 Volume 32, 2000 Volume 31, 1999 Volume 30, 1998 Volume 29, 1997 Volume 28, 1996

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


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.


  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: .

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

  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