Вдосконалення алгоритму Кантора-Зассенгауза для факторизацiї полiномiв
Loading...
Date
2025
Authors
Тiхонов, Андрiй
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
У роботi запропоновано метод прискорення алгоритму Кантора-Зассенгауза для факторизацiї полiномiв над скiнченними полями. Розроблено паралельну модель алгоритму, що використовує стратегiю динамiчного балансування навантаження «work stealing» для ефективної роботи на багатоядерних системах. Програмна реалiзацiя та експериментальне порiвняння з послiдовною версiєю пiдтвердили прискорення обчислень, що є актуальним для криптографiї та комп’ютерної алгебри.
Description
The paper proposes a method for speeding up the Cantor-Sassenhaus algorithm for factorizing polynomials over finite fields. A parallel model of the algorithm has been developed that uses a dynamic load balancing strategy called "work stealing" for efficient operation on multi-core systems. The software implementation and experimental comparison with the sequential version confirmed the computational speedup, which is relevant for cryptography and computer algebra
Keywords
факторизацiя полiномiв, скiнченне поле, поле Галуа, алгоритм Кантора-Зассенгауза, алгоритм Берлекампа, паралельнi обчислення, багатоядернi системи, work stealing, обчислювальна складнiсть, factorization of polynomials, finite field, Galois field, Berlekamp algorithm, parallel computing, multicore systems, work stealing, computational complexity, Cantor-Zassenhaus algorithm, магістерська робота