АЛГОРИТМ РОЗВʼЯЗКУ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ У ПОЛІ Fpk

АЛГОРИТМ РОЗВʼЯЗКУ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ У ПОЛІ 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...

Full description

Saved in:
Bibliographic Details
Date:2025
Main Authors: Kryvyi, S.L., Hoherchak, H.I.
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
id oai:ojs2.jais.net.ua:article-676
record_format ojs
institution Problems of Control and Informatics
baseUrl_str
datestamp_date 2025-10-08T22:38:45Z
collection OJS
language English
topic системи діофантових рівнянь
розширення поля
задача про математичний сейф
spellingShingle системи діофантових рівнянь
розширення поля
задача про математичний сейф
Kryvyi, S.L.
Hoherchak, H.I.
АЛГОРИТМ РОЗВʼЯЗКУ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ У ПОЛІ Fpk
topic_facet системи діофантових рівнянь
розширення поля
задача про математичний сейф
systems of diophantine equations
field extension
math safe problem
format Article
author Kryvyi, S.L.
Hoherchak, H.I.
author_facet Kryvyi, S.L.
Hoherchak, H.I.
author_sort Kryvyi, S.L.
title АЛГОРИТМ РОЗВʼЯЗКУ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ У ПОЛІ Fpk
title_short АЛГОРИТМ РОЗВʼЯЗКУ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ У ПОЛІ Fpk
title_full АЛГОРИТМ РОЗВʼЯЗКУ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ У ПОЛІ Fpk
title_fullStr АЛГОРИТМ РОЗВʼЯЗКУ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ У ПОЛІ Fpk
title_full_unstemmed АЛГОРИТМ РОЗВʼЯЗКУ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ У ПОЛІ Fpk
title_sort алгоритм розвʼязку систем лінійних рівнянь у полі fpk
title_alt ALGORITHM FOR SOLVING SYSTEMS OF LINEAR EQUATIONS IN FIELD Fpk
description 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.
publisher V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
publishDate 2025
url https://jais.net.ua/index.php/files/article/view/676
work_keys_str_mv AT kryvyisl algorithmforsolvingsystemsoflinearequationsinfieldfpk
AT hoherchakhi algorithmforsolvingsystemsoflinearequationsinfieldfpk
AT kryvyisl algoritmrozvʼâzkusistemlíníjnihrívnânʹupolífpk
AT hoherchakhi algoritmrozvʼâzkusistemlíníjnihrívnânʹupolífpk
first_indexed 2025-10-30T02:49:35Z
last_indexed 2025-10-30T02:49:35Z
_version_ 1847373411536338944
spelling oai:ojs2.jais.net.ua:article-6762025-10-08T22:38:45Z ALGORITHM FOR SOLVING SYSTEMS OF LINEAR EQUATIONS IN FIELD Fpk АЛГОРИТМ РОЗВʼЯЗКУ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ У ПОЛІ Fpk Kryvyi, S.L. Hoherchak, H.I. системи діофантових рівнянь розширення поля задача про математичний сейф systems of diophantine equations field extension math safe problem 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. Розглянуто базові теоретичні поняття в області скінченних полів, зокрема поняття поля залишків та розширення поля залишків. Наведено комплекс алгоритмів, необхідних для побудови розширень полів залишків: тест Рабіна для перевірки поліномів на незвідність, його використання для пошуку незвідних поліномів, алгоритм побудови таблиць додавання та множення за модулем незвідного полінома, шляхи обчислення протилежного та оберненого елементів на основі цих таблиць. Запропоновано шляхи покращення ефективності пошуку незвідних поліномів з використанням імовірнісногопідходу. Описано особливості нумерації елементів розширень скінченних полів Fpk і вплив вибору нумерації на ефективність виконання базових операцій над елементами поля, зокрема для пошуку протилежного і оберненого елементів. Запропоновано алгоритм побудови базису множини розвʼязків систем лінійних однорідних рівнянь та алгоритм побудови загального розвʼязку системи неоднорідних рівнянь над розширенням скінченного поля Fpk у вигляді суми комбінації векторів базису множини розв’язків відповідної однорідної системи та часткового розв’язк у неоднорідної системи. Алгоритми розв’язання систем рівнянь мають поліноміальні оцінки часової складності, які наведено в таблицях для конкретних прикладів систем лінійних рівнянь та різних параметрів алгоритмів. Розглянуто застосування запропонованих алгоритмів розвʼязання систем лінійних рівнянь до задачі про математичний сейф, її класичне формулювання та адаптаціюдо поля Fpk. Описано варіанти представлення математичного сейфа: за допомогою матриць та графів. Наведено умови існування розвʼязку, алгоритми розвʼязання задачі в цих випадках та їх ефективність в полі Fpk. Вказано можливі шляхи застосування систем рівнянь в полі Fpk в кодуванні та криптографії. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2025-10-09 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/676 10.1615/JAutomatInfScien.v51.i10.10 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 64 № 5 (2019): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 5-24 International Scientific Technical Journal "Problems of Control and Informatics; Том 64 № 5 (2019): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 5-24 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 64 No. 5 (2019): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 5-24 2786-6505 2786-6491 en https://jais.net.ua/index.php/files/article/view/676/743 https://creativecommons.org/licenses/by-nc-nd/4.0

Similar Items