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.
Zircon - This is a contributing Drupal Theme Design by WeebPal.
