ライブラリ登録: Guest
Journal of Automation and Information Sciences

年間 12 号発行

ISSN 印刷: 1064-2315

ISSN オンライン: 2163-9337

SJR: 0.173 SNIP: 0.588 CiteScore™:: 2

Indexed in

Algorithms for Solving Systems of Linear Equations in the Field Fpk

巻 51, 発行 10, 2019, pp. 1-22
DOI: 10.1615/JAutomatInfScien.v51.i10.10
Get accessGet access

要約

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

によって引用された
  1. Kryvyi S., Hoherchak H., The Mathematical Safe Problem and Its Solution (Part 1), Cybernetics and Computer Technologies, 4, 2020. Crossref

Begell Digital Portal Begellデジタルライブラリー 電子書籍 ジャーナル 参考文献と会報 リサーチ集 価格及び購読のポリシー Begell House 連絡先 Language English 中文 Русский Português German French Spain