polylib

Release 0.3.1

a library for working with polynomials

Homepage PyPI Python

License
Apache-2.0
Install
pip install polylib==0.3.1

Documentation

polylib

The package provides a class for concretely computing in the ring of polynomials with coefficients in a given ring or field. See below for example usage. After installation, additional documentation is made available by typing in your Python interpreter:

>>> import polylib
>>> help(polylib.Polynomial)
>>> help(polylib.FPolynomial)

Alternatively, type at your commandline: pydoc3 polylib.Polynomial. For recent versions of Python, pydoc3 is simply pydoc.

Installing this package also installs an executable program, bernoulli, that computes Bernoulli polynomials; type bernoulli at your commandline or, if ~/.local/bin/ is not in your PATH, type ~/.local/bin/bernoulli.

Contents

Installation

From your command line:

pip install polylib --user

or, for the latest dev version:

pip install git+https://github.com/sj-simmons/polylib.git --user

For older Python installations, pip might refer to its Python2 version (check this with pip -V), so use instead pip3.

Basic usage

In the interpreter, one can

>>> import polylib
>>> p = polylib.Polynomial([1, 0, -1])  # define a poly by specifying its coefficients
>>> p  # Polynomial([1, 0, -1])
>>> print(p)  # 1 - x^2
>>> print(p**5)  # 1 - 5x^2 + 10x^4 - 10x^6 + 5x^8 - x^10

Equivalently, one can define polynomials in a more Sage-like manner:

>>> x = polylib.Polynomial([0, 1])  # an indeterminant from which to build polynomials
>>> p = 1 - x**2
>>> print(p**5)  # 1 - 5x^2 + 10x^4 - 10x^6 + 5x^8 - x^10

If you are working over a field, you may wish to use FPolynomial — the difference is that, in the divmod, floordiv, and mod methods, one can divide an FPolynomial by any FPolynomial, whereas the divisor must be monic when dividing Polynomials.

>>> from fractions import Fraction as F
>>> from polylib import FPolynomial
>>>
>>> x = FPolynomial([0, F(1)])  # an indeterminant for polys over the rational numbers
>>> p = F(3) - F(7,2)*x - F(3,2)*x**2 - F(11,12)*x**3 - F(5,4)*x**4
>>> print(p)  # 3 - 7/2x - 3/2x^2 - 11/12x^3 - 5/4x^4
>>>
>>> # looking at the constant and leading coefficient of
>>> 12*p  # 36 - 42x - 18x^2 - 11x^3 - 15x^4,
>>> # a possible root of p is 3/5. Let us check:
>>> p.of(F(3,5)) == 0  # True
>>>
>>> # Let us divide p by  x - 3/5  using long division:
>>> p1 = x - F(3,5)
>>> q, r = p.divmod(p1)
>>> print("quotient:", q)   # quotient:  5 + 5/2x + 5/3x^2 + 5/4x^3
>>> print("remainder:", r)  # remainder: 0
>>>
>>> #If you just want the quotient:
>>> print(p // p1)  # 5 + 5/2x + 5/3x^2 + 5/4x^3
>>>
>>> #or, just the remainder:
>>> print(p % p1)  # 0

Suppose we want a different name for the indeterminant:

>>> from polylib import Polynomial
>>> print(Polynomial([3, 4, 0, 2], 't'))  # 3 + 2t + 4t^3
>>> # equivalently:
>>> t = Polynomial([0,1], 't')
>>> p = 3 + 2*t + 4*t**3  # 3 + 2t + 4t^3

Polynomials with polynomial coefficients

This library does not robustly handle polynomials in more than one variable; however, when working, say, over finite fields, we often want polynomials with polynomial coefficients.

We could do something like this:

>>> t = Polynomial([0, 1], 't')
>>> p = Polynomial([5-t, t**2+t-1, -2])
>>> print(p)  # 5 - t + -1 + t + t^2x + -2x^2

Problem: the string output is ambiguous; instead, do this:

>>> t = Polynomial([0, 1], '(t)')  # note the parentheses
>>> p = Polynomial([5-t, t**2+t-1, -2])
>>> print(p)  # (5 - t) + (-1 + t + t^2)x + -2x^2

but that is incorrect since

>>> p  # Polynomial((Polynomial((5, -1)), Polynomial((-1, 1, 1)), -2))

This is what we want:

>>> p = Polynomial([5-t, t**2+t-1, -2*t**0])  # note the use of t**0
>>> print(p)  # (5 - t) + (-1 + t + t^2)x + (-2)x^2
>>> p  # Polynomial((Polynomial((5, -1)), Polynomial((-1, 1, 1)), Polynomial((-2,))))

Alternatively, of course, one can type

>>> p=Polynomial((Polynomial((5,-1),'(t)'),Polynomial((-1,1,1),'(t)'),Polynomial((-2,),'(t)')))

but this might be better:

>>> x = Polynomial([0, 1])
>>> t = Polynomial([0, 1], '(t)')  # note the parentheses
>>> p = (5-t) * x**0 + (t**2+t-1) * x - 2*t**0 * x**2  # note, now, both t**0 and x**0
>>> print(p)
(5 - t) + (-1 + t + t^2)x + (-2)x^2

These sorts of polynomials occur when working with elliptic curves over a finite field. Their string representations are more readable if the coefficient polynomials don't appear with spaces:

>>> x = Polynomial([0, 1])
>>> t = Polynomial([0, 1], '(t)', spaces=False)
>>> p = (5-t) * x**0 + (t**2+t-1) * x - 2*t**0 * x**2  # note, now, both t**0 and x**0
>>> print(p)
(5-t) + (-1+t+t^2)x + (-2)x^2

In some cases, wrapping in square brackets is more readable:

>>> t = Polynomial([0, 1],'[t]')
>>> p = Polynomial([complex(0,1), complex(2,3)-complex(0,1)*t])
>>> print(p)  # 1j + [(2+3j) + (-0-1j)t]x
>>> print(p*2)  # (-1+0j) + [(-6+4j) + (2+0j)t]x + [(-5+12j) + (6-4j)t + (-1+0j)t^2]x^2

You may prefer a capital x or some other symbol for the indeterminate:

>>> p = Polynomial([complex(0,1), complex(2,3)-complex(0,1)*t], '[X]')
>>> print(p*2)  # (-1+0j) + [(-6+4j) + (2+0j)t]X + [(-5+12j) + (6-4j)t + (-1+0j)t^2]X^2

Cyclotomic polynomials

Next, suppose that we try to compute cyclotomic polynomials by means of their definition in terms of complex roots of unity:

from cmath import exp, pi
from math import gcd
from functools import reduce
from operator import mul
from polylib import Polynomial

def cyclotomic_poly(n):
    omega = exp(complex(0,2*pi/n))  # e^(2pi/n i), a primitive n_th root of unity
    x = Polynomial([0, 1])
    return reduce(mul, [x - omega**j for j in range(n) if gcd(j, n) == 1], 1)

print(cyclotomic_poly(8))

The function cyclotomic_poly(n) computes, in standard math notation, $\Phi_n(x)$, which is defined by

$$\Phi_n(x) = \prod_{\substack{0<j<n \\ \gcd(j,n)=1}} \left(x - e^{\frac{2\pi j}{n} i}\right),$$

the terms in the product on the right involving only primitive roots of unity.

The output of the above program is

(1-1.5543122344752192e-15j) + (7.771561172376096e-16+1.1102230246251565e-16j)x + (3.3306690738754696e-16-2.220446049250313e-16j)x^2 + (6.661338147750939e-16+0j)x^3 + x^4

The cmath Python library, as well as the builtin type complex, represents complex numbers in rectangular form, as pairs of floats; hence the rounding error in the coefficients of the 8th cyclotomic polynomial. In fact, as we will see below, the coefficients of $\Phi_n(x)$ are integral for all $n.$

Since the complex primitive roots of unity occur in complex conjugate pairs. we can improve things by multiplying first the conjugate pairs:

def cyclotomic_poly(n):
    omega = exp(complex(0,2*pi/n))
    x = Polynomial([0, 1])
    if n < 3:
        poly = reduce(mul, [x - omega**j for j in range(n) if gcd(j, n) == 1], 1)
    else:
        poly = reduce(
            mul,
            [(x-omega**j)*(x-(omega**j).conjugate()) for j in range(n//2+1) if gcd(j, n) == 1],
            1
        )
    return poly

Then cyclotomic_poly(8) becomes:

1 + (-4.440892098500626e-16+0j)x + (4.440892098500626e-16+0j)x^2 + (-4.440892098500626e-16+0j)x^3 + x^4

Assuming that the coefficients are integral, we can now simply round:

from cmath import exp, pi
from math import gcd
from functools import reduce
from operator import mul
from polylib import Polynomial

def cyclotomic_poly(n):
    omega = exp(complex(0, 2 * pi / n))
    x = Polynomial([0, 1])
    if n < 3:
        poly = reduce(mul, [x - omega ** j for j in range(n) if gcd(j, n) == 1], 1)
    else:
        poly = reduce(
            mul,
            [
                (x - omega ** j) * (x - (omega ** j).conjugate())
                for j in range(n // 2 + 1)
                if gcd(j, n) == 1
            ],
            1,
        )
    return Polynomial([round(coeff.real) for coeff in poly])

print(" n   cyclotomic_poly(n)")
for n in range(1, 17):
    print(f"{n:2}   {cyclotomic_poly(n)}")

output:

 n   cyclotomic_poly(n)
 1   -1 + x
 2   1 + x
 3   1 + x + x^2
 4   1 + x^2
 5   1 + x + x^2 + x^3 + x^4
 6   1 - x + x^2
 7   1 + x + x^2 + x^3 + x^4 + x^5 + x^6
 8   1 + x^4
 9   1 + x^3 + x^6
10   1 - x + x^2 - x^3 + x^4
11   1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10
12   1 - x^2 + x^4
13   1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12
14   1 - x + x^2 - x^3 + x^4 - x^5 + x^6
15   1 - x + x^3 - x^4 + x^5 - x^7 + x^8
16   1 + x^8

(For those interested in computing exactly in the real of complex numbers see, for example, Calcium and slides from a talk by its author.)

In the case of cyclotomic polynomials, it is better to reformulate their definition completely in terms of $\mathbb{Z}[x]$, polynomials over the integers. Before we do that, let us observe the floating point issues inherent in the above formulation of cyclotomic_poly(n) building up to the point of throwing off our computations.

It is fairly easy to establish (see below), for $p$ a prime and $r$ a positive integer, the following identity:

$$\Phi_{p^r}(x) = \Phi_p\left(x^{p^{r-1}}\right).$$

We can use polylib to compose polynomials. Let us verify the identity above for $p=3$ and $r=4$:

x = Polynomial([0, 1])
cyclotomic_poly(3**4) == cyclotomic_poly(3).of(x**(3**3))  # True

But what if $r=5$?

cyclotomic_poly(3**5) == cyclotomic_poly(3).of(x**(3**4))  # False, but should be True

Cyclotomic polynomials as polynomials over the integers

Over any field $\mathbb{F}$ with unit, one can construct cyclotomic polynomials $\Phi_n(x)\in \mathbb{Z}[x]$ (partially) characterized by the following:

\begin{align} \Phi_n(b) = 0 \text{~if and only if~} b \text{~has exponent~} n. \tag{1} \end{align}

(Here, $b\ne 0$ and the exponent of $b\in\mathbb{F}$ is the smallest positive integer $n$, if it exists, satisfying $b^n = 1.$)

More correctly, the coefficients are in an isomorphic image of $\mathbb{Z}$ embedded in the prime field $\mathbb{Q}$ of $\mathbb{F}$ in the case that $\mathbb{F}$ has characteristic zero; if $\mathbb{F}$ has positive characteristic $p$, then the coefficients live in its prime field — isomorphic to $\mathbb{Z}/p\mathbb{Z}$ — which is naturally the homomorphic image of $\mathbb{Z}$ in $\mathbb{F}.$

If $\mathbb{F}=\mathbb{C}$, notice that, by the Fundamental Theorem of Algebra, the cyclotomic polynomials defined above satisfy condition (1) since the primitive $n$th roots of unity, $e^{\frac{2\pi j}{n}i}$ for $0< j < n$ and $\gcd(j,n)=1,$ are the complete list of complex numbers of exponent $n.$ Also note that each primitive $n$th root of unity is a zero of mutliplicity 1, so the $\Phi_n(x)$ in the definition above are the unique smallest-degree, monic polynomials that do the job.

How can we construct the cyclotomic polynomials $\Phi_n(x)$ using only polynomials of the integers?

First note that, over $\mathbb{C}$, we have the factorization

$$x^n-1=\prod_{0\le j < n} \left(x - e^{\frac{2\pi j}{n} i}\right),$$

the product now involving all $n$th roots of unity — the factorization holds since the $n$ $n$th roots of unity are exactly the $n$ roots of $x^n-1.$

The $n$th roots of unity together comprise a multiplicative group of order $n.$ By Lagrange's Theorem, the order, $d$, of any single $n$th root of unity must divide $n.$ Collecting the $d$th primitive roots of unity for each $d$ that divides $n,$ we can write

$$x^n-1=(x-1)\prod_{\substack{1 < d \le n \\ d|n}} \Phi_d(x),$$

where $\Phi_d(x)$ are, for now, still defined, as above, in terms of the primitive $d$th roots of unity; hence, we can write

$$\Phi_n(x)=\frac{x^n-1}{\displaystyle\prod_{\substack{1 \le d < n \\ d|n}} \Phi_d(x)}$$

where we have set $\Phi_1(x)=x -1.$ In fact, we can view this last equality as a (recursive) definition of $\Phi_n(x).$

We now see why $\Phi_n(x)$ has integer coefficients: inductively (with respect to $n$), if we assume that each — monic, we already know — $\Phi_d(x)$ with $d|n$ and $d<n$ has integral coefficients, the product in the denominator above is also monic with integer coefficients. The numerator, $x^n-1$, has integer coefficients so that long division (we already know that the remainder is 0) can be executed using only integers.

Rather than writing out the induction proof in detail, let us rewrite the function cyclotomic_poly in a such a way that it uses only polynomials over the integers:

from functools import reduce
from operator import mul
from polylib import Polynomial

def cyclotomic_poly(n):
    assert n > 0
    x = Polynomial([0, 1])
    return (x ** n - 1) // reduce(
        mul, [cyclotomic_poly(d) for d in range(1, n) if n % d == 0], x ** 0
    )

print(" n   cyclotomic_poly(n)")
for n in range(1, 18):
    print(f"{n:2}   {cyclotomic_poly(n)}")

The output is, of course, the same as above,

 n   cyclotomic_poly(n)
 1   -1 + x
 2   1 + x
 3   1 + x + x^2
 4   1 + x^2
 5   1 + x + x^2 + x^3 + x^4
     ...

And the two identities, the second of which we had trouble with above?

x = Polynomial([0, 1])
cyclotomic_poly(3**4) == cyclotomic_poly(3).of(x**(3**3))  # True
cyclotomic_poly(3**5) == cyclotomic_poly(3).of(x**(3**4))  # True

Before moving on, let us establish the identity in question, which is

$$\Phi_{p^r}(x) = \Phi_p\left(x^{p^{r-1}}\right).$$

First notice that, if n is prime, the recursive definition specializes to

$$\Phi_p(x)=\frac{x^p-1}{x-1}.$$

More generally,

\begin{align} \Phi_{p^r}(x) &= \frac{x^{p^r}-1}{\Phi_{1}(x)\Phi_{p}(x)\Phi_{p^2}(x)\cdots\Phi_{p^{r-1}}(x)} \notag \\ &= \frac{x^{p^r}-1}{\Phi_{1}(x)\Phi_{p}(x)\Phi_{p^2}(x)\cdots\Phi_{p^{r-2}}(x)\frac{x^{p^{r-1}}-1}{\Phi_{1}(x)\Phi_{p}(x)\Phi_{p^2}(x)\cdots\Phi_{p^{r-2}(x)}}} \notag \\ &= \frac{x^{p^r}-1}{x^{p^{r-1}}-1} \notag \\ &= \Phi_p\left(x^{p^{r-1}}\right). \notag \end{align}

Cyclotomic polynomials over fields

Over $\mathbb{C}$, the polynomial $x^n-1$ has $n$ distinct roots and so each root has multiplicity 1; i.e., in its factored form, none of the linear factors $x-\alpha$ of $x^n-1$ are repeated. It turns out the same is true over any field whose characteristic does not divide $n$ (this follows from the fact that $x^n-1$ and its formal derivative $nx^{n-1}$ satisfy $1 = n^{-1}x \cdot nx^{n-1}-(x^n-1)$ if the characteristic of $F$ does not divide $n$ and hence are co-prime over $\mathbb{F}$)1.

A natural question to consider is: can we use the recursive definition from the last section over any field? For completeness, here is the recursive definition:

$$\Phi_n(x)=\frac{x^n-1}{\displaystyle\prod_{\substack{1 \le d < n \\ d|n}} \Phi_d(x)}$$

At issue is whether we retain the property

$$\Phi_n(b) = 0 \text{~if and only if~} b \text{~has exponent~} n$$

over fields other than the complex numbers.

But the only way that $\alpha\in\mathbb{F}$ can satisfy $\Phi_n(\alpha) = 0$ is if $\alpha^n=1$; and if the reason $\alpha^n=1$ is that $\alpha^d=1$ for $0<d<n$ (assume without loss of generality that $d$ is the least such positive integer) then $d$ must divide $n$ (by the division algorithm). But then $\alpha$ is a root of the denominator so that $x-\alpha$ occurs as a factor in the denominator. This is a problem since such a factor in the denominator would cancel with an identical and non-repeated (if the characteristic of $\mathbb{F}$ does not divide $n$) factor in the numerator. Hence no such $d$ exists, and the property above holds over any field.

A subtlety here is that we are now officially working over the prime field of $\mathbb{F}.$ Let $\overline{\Phi}_n(x)$ denote the cyclotomic polynomial $\Phi_n(x)$ with coefficients now in the image of the natural ring homomorphism $\mathbb{Z}\rightarrow\mathbb{F}$ (which is reduction modulo a prime if the characteristic of $\mathbb{F}$ is positive and essentially the identity in characteristic zero). Clearly, $\overline{\Phi}_n(x)=0$ for $\alpha \in \mathbb{F}$ if and only if $\Phi_n(\alpha)=0.$ Using the Euclidean algorithm, we can write, for $\Phi_d(x)$ or any $f(x)\in\mathbb{F}[x],$ $f(x)=g(x)(x-\alpha) + r$ where $r\in \mathbb{F};$ in fact, $r=f(\alpha)$ so that $\alpha\in\mathbb{F}$ is a root if and only if $(x-\alpha)$ divides $f(x)$ (which, note, also implies that $f(x)$ has at most $n$ roots in $\mathbb{F}$).2

A useful summary of the preceding argument is that if, in the case that char($\mathbb{F}$) does not divide $n,$ we write

$$x^n-1 = \displaystyle\prod_{\substack{1 \le d \le n \\ d|n}} \Phi_d(x),$$

then the cyclotomic polynomials on the right are pairwise coprime as polynomials in $\mathbb{F}[x].$

If defined using complex $n$th roots of unity, then $\Phi_n(x)$ clearly has degree $\phi(n)$ where $\phi$ denotes Euler's phi-function (i.e., $\phi(n)$ is defined to be the number of positive integers less than and coprime to $n$).

But over any field, the degree is the same, as follows inductively from the recursive definition and the identity

$$\sum_{\substack{1 \le d \le n \\ d|n}} \phi(d) = n.$$

Let us reformulate the property above:

If char($\mathbb{F}$) does not divide $n$, then

\begin{align} \Phi_n(b) = 0 \text{~if and only if~} b \text{~has order~} n \text{~in~}\mathbb{F}^* \tag{1'} \end{align}

where $\mathbb{F}^*$ denotes the non-zero elements (so, units) of the field $\mathbb{F}$.

We are now in a good position to observe the following:

$$\text{Every finite subgroup of ~} \mathbb{F}^* text{~is cyclic}.$$

This is true in any field $\mathbb{F}.$ Why? Suppose given a subgroup of order $n$ and consider the identity (in $\mathbb{F}[x]$):

$$x^n-1 = \displaystyle\prod_{\substack{1 \le d \le n \\ d|n}} \Phi_d(x);$$

The elements of the given group are exactly the solutions of the polynomials on the left and hence on the right. From (1'), we know that the roots of $\Phi_n(x)$ are the generators of the given group (of which there are $\phi(n),$ we also know). More generally, each (also cyclic, of course) subgroup of the given group must have order $d$ dividing $n$ and so has the $\phi(d)$ generators consisting exactly of the roots of $\Phi_n(x).$3

The picture is now complete. Over any field one has the analogue of the $n$th complex roots of unity with exactly the same group structure. The roots of the cycolotomic polynomials are precisely the generators of of the subgroups of order $d$ dividing $n$.

In a field of characteristic zero, one has finite groups of all orders and they are all cyclic. The same is true in finite field, at least for orders not divisible by the characteristic.

In any case, to find a generator, or primitive element, of a subgroup of order $n$, one only need to find a root of $\Phi_n(x)$.

The program below uses numlib to instantiate the prime field $\mathbb{Z}/2\mathbb{Z}$ and then computes the first few cyclotomic polynomials with coefficients reduced modulo 2.

from functools import reduce
from operator import mul
from polylib import Polynomial
from numlib import Zmod

def cyclotomic_poly(n: int, x: Polynomial = Polynomial([0, 1])) -> Polynomial:
    return (x ** n - 1) // reduce(
        mul, [cyclotomic_poly(d) for d in range(1, n) if n % d == 0], x ** 0
    )

Zp = Zmod(2)
x = Polynomial([0, Zp(1)])

print(" n   n_th cyclotomic poly over", Zp)
for n in range(1, 8):
    print(f"{n:2}   {cyclotomic_poly(n, x)}")

output:

 n   n_th cyclotomic poly over Z/2Z
 1   1 + x
 2   1 + x
 3   1 + x + x^2
 4   1 + x^2
 5   1 + x + x^2 + x^3 + x^4
 6   1 + x + x^2
 7   1 + x + x^2 + x^3 + x^4 + x^5 + x^6

Cyclotomic polynomials over fields

Cyclotomic polynomials are often in the mix when constructing finite (Galois) fields. Suppose $f(x)$ is an irreducible polynomial over $\mathbb{Z}/p\mathbb{Z}$ of degree $m.$ Then, $\mathbb{Z}/p\mathbb{Z} [x]$ modulo the ideal $\langle f(x)\rangle$ generated by $f(x)$ is a finite field of order $p^m$. See, for example, numlib for the mathematical details and implementations.

Let us consider the case in which $p=2$ and $m=4$. Using numlib we can construct the Galois field of order 16 using numlib.FPmod but we need a quartic that is irreducible over the prime field $\mathbb{Z}/2\mathbb{Z}$ (more on finding such a polynomial below).

>>> from numlib import Zmod, FPmod
>>> from polylib import FPolynomial
>>>
>>> PF = Zmod(2)  # the prime field
>>> t = FPolynomial([0, PF(1)], 't')  # an indeterminant for Z/2Z[x]
>>> irred = 1 + t**3 + t**4  # this is irreducible over Z/2Z[x]
>>> GF = FPmod(irred)  # representation of the Galois field of order 16
>>> print(GF)  # Z/2Z [t] / <1 + t^3 + t^4>

We already know that the multiplicative group of units in GF is cyclic, and that its generators are exactly the roots of the cyclotomic polynomial $\Phi_{15}$. As a sanity check, let us brute force verify this. Continuing the previous interactive session:

>>> def order(elt):   # return the multiplicative orde
...     for j in range(1,16):
...         if elt**j == 1:
...             return j
>>>
>>> from itertools import product
>>>
>>> generators = []
>>> for coeffs in product(PF, repeat=4):
...     elt = GF(coeffs)
...     if order(elt) == 15:
...         generators.append(elt)
>>> print(', '.join([str(gen).replace(" ","") for gen in generators]))
t^2, t^2+t^3, t, t+t^2, t+t^2+t^3, 1+t^3, 1+t^2+t^3, 1+t+t^2

Now for the verification:

>>> from polylib import cyclotomic
>>> cyclo15 = cyclotomic(15, t)  # 1 + t + t^3 + t^4 + t^5 + t^7 + t^8
>>> all(map(lambda elt: cyclo15.of(elt) == 0, generators))
True

Serendipitously, the choice of $1+t^3+t^4$ for the irreducible when implementing $\operatorname{GF}(2^4)$ led to the equivalence class $t + \langle 1+t^3+t^4\rangle$ being a generator. That happening is particularly convenient and we say that $1+t^3+t^4$ is a primitive polynomial for $\operatorname{GF}(2^4)$; i.e., an irreducible $f(x)$ is a primitive polynomial for $\operatorname{GF}(2^4)$ if $t$'s equivalence class is a generator for $\mathbb{Z}/2\mathbb{Z}[x]/\langle 1+t^3+t^4 \rangle$.

We know that we need an quartic irreducible over $\mathbb{Z}/2\mathbb{Z}[x]$ to even instantiate $\operatorname{GF}(2^4)$; but how can we choose one so that $t$ turns out to be a generator? A hint is that the irreducible we chose above divides $\Phi_{15}$:

>>> print(cyclo15 % irred)
0
>>> print(cyclo15 // irred)
1 + t + t^4

Moreover, $1 + t + t^4$ is also irreducible in $\mathbb{Z}/2\mathbb{Z}[x]$.

But how do we find a candidate for a primitive polynomial in the first place? One clue is that, in the previous example, $\Phi_{15}$ factors like

begin(align) 1+t+t^3+t^4+t^5+t^7+t^8 &= 1 + t^3 + t^4 + t + t^4(t + t^3 + t^4) \notag\ &= 1 + (1 + t^4)(t + t^3 + t^4) \notag\

Exercises

  1. Write a program that find an primitive polynomial for $\operatorname{GF}(2^12).$

Footnotes

1 The formal (or algebraic) derivative $D: \mathbb{F}[x] \rightarrow \mathbb{F}[x],$ which one first defines on monomials as $D(x^n)=nx^{n-1}$ and then extends linearly, satisfies the familiar product rule from Calculus. Hence, if $f(x) = (x-\alpha)^2\cdot g(x),$ then $D[f(x)]=(x-\alpha)^2\cdot D[g(x)] + 2(x-\alpha)\cdot g(x)$; so that $(x-\alpha)$ is a common divisor of $f(x)$ of $D[f(x)].$

Also, that the expression $1 = n^{-1}x \cdot nx^{n-1}-(x^n-1)$ implies that $nx^{n-1}$ and $x^n-1$ have no common factors tacitly uses the fact that $\mathbb{F}[x]$ is a unique factorization domain — more computationally, $\mathbb{F}[x]$ is a Euclidean domain and, in fact, one in which polynomial division can be used to implement the Euclidean algorithm.

2 The ring $\mathbb{Z}[x]$, where the cyclotomic polynomials $\Phi_n(x)$ live, is not a Euclidean domain, nor even an principal ideal domain; it is, however, a unique factorization domain in which the division algorithm can be used to write any $f(x)$ in $\mathbb{Z}[x]$ as $f(x)=g(x)(x-a) + r$ where $r\in \mathbb{Z},$ so that $a\in \mathbb{Z}$ is a root of $f$ if and only if it is divisible by $x-a$.

3 If $\mathbb{F}$ is perfect and char($\mathbb{F}$) divides $n$, then one can show that $x^n-1$ necessarily has repeated roots in $\mathbb{F}$. In other words, there are not enough element of $\mathbb{F}$ with the right order to form a group of order $n$ — so over, for example, over a finite field, there is no subgroup with order divisible by the characteristic.

Resources

Todo

  • Implement faster division algorithm (see Cao and Cao's paper linked to above).
  • Implement multivariate polynomials (use hash?)
  • Add option to Polynomial's constructor to print in decreasing degree order.

Stats

Dependencies
0
Dependent packages
0
Dependent repositories
0
Total releases
3
Latest release
First release
Stars
2
Forks
0
Watchers
2
Contributors
1
Repository size
936 KB
SourceRank
7

Development practices

Source repo 2FA enabled
TEXT!
Package manager 2FA enabled
TEXT!
Is security responsive
TEXT!
Dependencies are managed
TEXT!
Issue-free release available
TEXT!
Succession plan available
TEXT!
Package manager 2FA enabled
TEXT!

The Tidelift Subscription provides access to a continuously curated stream of human-researched and maintainer-verified data on open source packages and their licenses, releases, vulnerabilities, and development practices.

Learn more →

Releases

0.3.1
0.3
0.1

Contributors

Scott Simmons


See all contributors

Something wrong with this page? Make a suggestion

Export .ABOUT file for this package

Last synced: 2024-01-27 19:23:00 UTC

Login to resync this project