Decomposing Univariate Polynomials over Finite Fields
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


Decomposing Univariate Polynomials over Finite Fields

This Python-module provides functions to study the functional decomposition of univariate polynomials over a finite field. We have the following fundamental distinctions.

Tame case
where the polynomial's degree is coprime to the characteristic of the base field.
Wild case
where the polynomial's degree is a multiple of the characteristic of the base field.
Additive case
where all exponents of the polynomial are powers of the characteristic of the base field; this is a special case of the previous one.

We measure the degree of our understanding by our ability to count the number of decomposable polynomials at a given degree. The crucial ingredient for the obvious inclusion-exclusion formula is an understanding of collisions, that is of distinct decompositions of a given polynomial.


for all additive polynomials this gives the exact number of $k$-collisions and by inclusion-exclusion the number of decomposables; see [GGZ10], compare to [CHH04].
for a single additive polynomial, this determines the structure of (the lattice of) right components via the rational Jordan form of the Frobenius on its root space; see [GGZ10] and [F11].
create look-up tables of complete decompositions (if feasible) or count at least the number of decomposables; output to ./data/
for the (basic) wild case, create dictionaries to classify decompositions; see [BGZ13].
for the (basic) wild case, create polynomials with a given number of decompositions TODO
for the tame case, determine the structure (and number) of all tame collisions according to [Z14].


Load the module in your local Sage installation:

$ sage -q
sage: load('add_count.sage')

See each module's documentation for further instructions.


  • add the formulas of [BGZ13] to p2_construct_collision_by_parameter.sage
  • compare with the ore-package and sigma(a) = a^r


This code requires the free mathematical software [Sage] which is available for download at and as cloud service at It has been tested under GNU/Linux with Sage 6.4.


[BGZ13](1, 2) Raoul Blankertz, Joachim von zur Gathen & Konstantin Ziegler (2013). Compositions and collisions at degree p2. Journal of Symbolic Computation 59, 113–145. ISSN 0747-7171. URL Also available at Extended abstract in Proceedings of the 2012 International Symposium on Symbolic and Algebraic Computation ISSAC ’12, Grenoble, France (2012), 91–98.
[CHH04]Robert S. Coulter, George Havas & Marie Henderson (2004). On decomposition of sub-linearised polynomials. Journal of the Australian Mathematical Society 76(3), 317–328. URL
[F11]Harald Fripertinger (2011). The number of invariant subspaces under a linear operator on finite vector spaces. Advances in Mathematics of Communications 5(2), 407–416. ISSN 1930-5346. URL
[GGZ10](1, 2) Joachim von zur Gathen, Mark Giesbrecht & Konstantin Ziegler (2010). Composition collisions and projective polynomials. Statement of results. In Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation ISSAC ’10, Munich, Germany, edited by Stephen Watt, 123–130. ACM Press. URL Preprint available at
[Sage]W. A. Stein et al. (2014). Sage Mathematics Software (Version 6.4). The Sage Development Team. URL
[Z14]Konstantin Ziegler (2014). Tame decompositions and collisions. In Proceedings of the 2014 International Symposium on Symbolic and Algebraic Computation ISSAC ’14, Kobe, Japan, edited by Katsusuke Nabeshima, 421–428. ACM Press, Kobe, Japan. URL Preprint available at


  • Konstantin Ziegler (2013-12-24): initial version


This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see