Issues in the implementation of multiplication and factoring algorithms in Galois fields
Loading...
Files
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of New Brunswick
Abstract
Cryptography in finite fields often requires factoring polynomials. As a result, there is value to understanding the different approaches to polynomial factoring algorithms and their performance. First, several of the approaches to univariate polynomial multiplication are explored. These polynomial factoring algorithms are then used to solve the problem of univariate polynomial factorization in a Galois field. An emphasis is placed on the theoretical running time and memory requirements of these algorithms, as well as the actual running time (in seconds) of some sample problems. This is done to give an idea of the real computing costs of running these algorithms. After covering univariate polynomial multiplication and factoring, the more complex problem of factoring with a field extension is explored. One approach to this problem is to modify the univariate polynomial factoring algorithms (such as Cantor-Zassenhaus) to account for the more complicated finite field structure. Finally, a novel application of the Cantor-Zassenhaus algorithm is developed.