Improvements on Cantor-Zassenhaus Factorization Algorithm

2010/12/23 by Michele Elia, Elia, Michele, Davide Schipani +1
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #graph theory and CDMA systems #math.NT

paper · pdf · doi:10.48550/arxiv.1012.5322

extended and revised version; case s>1 added

openalex publication_date 2010/12/23 · arxiv created 2011/05/27 · arxiv updated 2011/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

After revisiting Cantor-Zassenhaus polynomial factorization algorithm, we describe a new simplified version of it, which requires less computational cost. Moreover we show that it is able to find a factor of a fully splitting polynomial of degree t over \mathbb F_2^m with O(\frac2^m3^t) attempts and over \mathbb F_p^m for odd p with O(\fracp^m2^t) attempts.

Related

• Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields
• Enhancing the Power of Cardinal's Algorithm
• A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
• Factorization of Non-Commutative Polynomials
• Factoring Ore polynomials over \mathbbF_q(t) is difficult