Improvements on Cantor-Zassenhaus Factorization Algorithm

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(\frac{2^m}{3^t})$ attempts and over ${\mathbb{F}}_{p^m}$ for odd $p$ with $O(\frac{p^m}{2^t})$ attempts.

extended and revised version; case s>1 added