CECCO: Finding Irreducible Polynomials

Constructing a finite extension field with Q=q^m (m>=2) elements requires a finite field Fq with q elements (the base field) and an irreducible (over Fq) polynomial of degree m, cf. here. CECCO requires these polynomials to be monic and the extension field constructor expects their coefficient vectors with least significant coefficient on the left. Over F2, we have the irreducible polynomial 1+x+x^2, so we can construct F4 as follows:

code.cpp Lines 7–7

    using F4 = Ext<Fp<2>, {1, 1, 1}>;

Similarly, F8 can be constructed from base field F2 and 1+x^2+x^3:

code.cpp Lines 8–8

    using F8 = Ext<Fp<2>, {1, 0, 1, 1}>;

F16 can be constructed in two ways, either from base field F2 and 1+x^3+x^4 or from base field F4 and 2+2x+x^2. The resulting fields are isomorphic, so they can be merged into a stack of isomorphic fields:

code.cpp Lines 9–9

    using F16 = Iso<Ext<Fp<2>, {1, 0, 0, 1, 1}>, Ext<Ext<Fp<2>, {1, 1, 1}>, {2, 2, 1}> >;

This is of course not restricted to fields of characteristic 2, we can also construct F27 from base field F3 and 1+2x+x^3:

code.cpp Lines 11–11

    using F27 = Ext<Fp<3>, {1, 2, 0, 1}>;

Until now, we did not specify how the irreducible polynomials can be obtained. They can be found by constructing random polynomials of degree m over the base field and testing their irreducibility. This is exactly what the function template find_irreducible<>() does (it outputs only monic polynomials). The coefficient vector (with least significant coefficient on the left) can be obtained using the get_coefficients() member.

code.cpp Lines 13–18

    constexpr size_t q = 2;
    constexpr size_t m = 6;
    using Fq = Fp<q>;
    auto P = find_irreducible<Fq>(m);
    std::cout << "Monic irreducible polynomial: " << P << std::endl;
    std::cout << "Coefficient vector (to be used as template parameter of Ext<>): " << P.get_coefficients() << std::endl;

Monic irreducible polynomial: 1 + x^5 + x^6
Coefficient vector (to be used as template parameter of Ext<>): ( 1, 0, 0, 0, 0, 1, 1 )

Alternatively, one can use an appropriate Conway polynomial. The Conway polynomials for p^m<10000 are hard-coded into the library:

code.cpp Lines 20–22

    auto Q = ConwayPolynomial<q, m>();
    std::cout << "Conway polynomial: " << Q << std::endl;
    std::cout << "Coefficient vector (to be used as template parameter of Ext<>): " << Q.get_coefficients() << std::endl;

Conway polynomial: 1 + x + x^3 + x^4 + x^6
Coefficient vector (to be used as template parameter of Ext<>): ( 1, 1, 0, 1, 1, 0, 1 )

The coefficient vectors that are obtained in this way are supposed to be hard-coded as template parameters of Ext<>, same as in the introductory examples F2, F4, F16, and F27!

A complete, compilable demo is shown below:

code.cpp

#include <iostream>

#include "cecco.hpp"
using namespace CECCO;

int main(void) {
    using F4 = Ext<Fp<2>, {1, 1, 1}>;
    using F8 = Ext<Fp<2>, {1, 0, 1, 1}>;
    using F16 = Iso<Ext<Fp<2>, {1, 0, 0, 1, 1}>, Ext<Ext<Fp<2>, {1, 1, 1}>, {2, 2, 1}> >;

    using F27 = Ext<Fp<3>, {1, 2, 0, 1}>;

    constexpr size_t q = 2;
    constexpr size_t m = 6;
    using Fq = Fp<q>;
    auto P = find_irreducible<Fq>(m);
    std::cout << "Monic irreducible polynomial: " << P << std::endl;
    std::cout << "Coefficient vector (to be used as template parameter of Ext<>): " << P.get_coefficients() << std::endl;

    auto Q = ConwayPolynomial<q, m>();
    std::cout << "Conway polynomial: " << Q << std::endl;
    std::cout << "Coefficient vector (to be used as template parameter of Ext<>): " << Q.get_coefficients() << std::endl;

    return 0;
}