DOI
10.34229/KCA2522-9664.26.2.4
УДК 61.681.3
С.Л. КРИВИЙ
Київський національний університет імені Тараса Шевченка, Київ, Україна,
sl.krivoi@gmail.com
О.В. ЧУГАЄНКО
ТОВ «Самсунг РнД Інститут Україна», Київ, Україна, firestreami13@yahoo.com
ПРО АЛГОРИТМИ РОЗВ’ЯЗАННЯ ЛІНІЙНИХ
РІВНЯНЬ У КІЛЬЦЯХ ЛИШКІВ
Анотація. Проаналізовано два алгоритми розв’язання систем лінійних конгруенцій у кільцях лишків. Перший алгоритм ґрунтується на факторизації модуля з подальшим розв’язанням підсистем, на які розпадається початкова система, у примарних кільцях і полях. В основу другого алгоритму покладено введення певної надлишковості під час обчислень. Обидва алгоритми знаходять твірні вектори множини всіх розв’язків початкової системи лінійних конгруенцій. Наведено отримані у результаті експериментів залежності обох алгоритмів від величини модуля, кількості конгруенцій та кількості змінних у системах.
Ключові слова: лінійні рівняння, кільце лишків, алгоритми, складність.
повний текст
СПИСОК ЛІТЕРАТУРИ
- 1. Menezes A., van Oorschot P., Vanstons S. Handbook of applied cryptography. Boca Raton: CRC Press, 1996. 661 p.
- 2. Lenstra A.K., Lenstra M.S., Menasse M.S., Pollard J.M. The number field sieve. Proc. of the 22nd ACM Symposium on the Theory of Computing (13–17 May 1990, Baltimore, USA). Baltimore, 1990. P. 564–572.
- 3. Калужнин Л.А. Введение в общую алгебру. Москва: Наука, 1973. 447 с.
- 4. Shoup V. A computational introduction to number theory and algebra. Cambridge: Cambridge University Press, 2008. 580 p.
- 5. Kryvyi S.L. Algorithms for solution of systems of linear Diophantine equations in residue fields. Cybernetics and Systems Analysis. 2007. Vol. 43, N 2. P. 171–178. https://doi.org/10.1007/s10559-007-0036-8.
- 6. Kryvyi S.L. Algorithms for solution of linear constraints over residue ring. Cybernetics and Systems Analysis. 2024. Vol. 60, N 6. P. 862–871. https://doi.org/10.1007/s10559-024-00723-1.
- 7. Крывый С.Л., Антонюк В.Т. Реализация алгоритма решения систем линейных диофантовых уравнений в кольце вычетов. Управляющие системы и машины. 2017. № 6. С. 55–64.
