Header

UZH-Logo

Maintenance Infos

Improvements on the Cantor-Zassenhaus factorization algorithm


Elia, Michele; Schipani, Davide (2015). Improvements on the Cantor-Zassenhaus factorization algorithm. Mathematica Bohemica, 140(3):271-290.

Abstract

The paper presents a careful analysis of the Cantor-Zassenhaus polynomial factorization algorithm, thus obtaining tight bounds on the performances, and proposing useful improvements. In particular, a new simplified version of this algorithm is described, which entails a lower computational cost. The key point is to use linear test polynomials, which not only reduce the computational burden, but can also provide good estimates and deterministic bounds of the number of operations needed for factoring. Specifically, the number of attempts needed to factor a given polynomial, and the least degree of a polynomial such that a factor is found with at most a fixed number of attempts, are computed. Interestingly, the results obtained demonstrate the existence of some sort of duality relationship between these two problems.

Abstract

The paper presents a careful analysis of the Cantor-Zassenhaus polynomial factorization algorithm, thus obtaining tight bounds on the performances, and proposing useful improvements. In particular, a new simplified version of this algorithm is described, which entails a lower computational cost. The key point is to use linear test polynomials, which not only reduce the computational burden, but can also provide good estimates and deterministic bounds of the number of operations needed for factoring. Specifically, the number of attempts needed to factor a given polynomial, and the least degree of a polynomial such that a factor is found with at most a fixed number of attempts, are computed. Interestingly, the results obtained demonstrate the existence of some sort of duality relationship between these two problems.

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:2015
Deposited On:07 Dec 2016 07:59
Last Modified:08 Dec 2017 21:09
Publisher:Akademie Ved Ceske Republiky
ISSN:0862-7959
Official URL:http://mb.math.cas.cz/MBtoc.html

Download

Full text not available from this repository.