numlib

Release 0.3.1

basic number theory tools

Homepage PyPI Python

License
Apache-2.0
Install
pip install numlib==0.3.1

Documentation

numlib

Contents

Installation

From your command line:

pip install numlib --user

or, for the latest development version:

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

This library depends heavily on another Python library, polylib, which can be installed with pip install polylib --user.

Note: for your Python installation, you may need to type pip instead of pip3 in the commands above. You can check whether pip points to its Python3 version by issuing the command pip -V at your commandline.

Quick start

Define and work in a Galois field

>>> import numlib as nl
>>> GF = nl.GaloisField(7, 3)
>>> print(GF)
Z/7[t]/<-3+3t^2+t^3>
>>> GF.order  # 7^3
(7, 3)

Element of GF are (equivalence classes of) polynomials. The easiest way to define a particular such element is to use an indeterminant.

>>> t = GF()
>>> 1 + 2*t**2
1+2t^2 + <-3+3t^2+t^3>
>>> t**100
2+t-3t^2 + <-3+3t^2+t^3>

The element t, created as above, is always a generator for GaloisField's multiplicative group of units:

>>> nl.mulorder(t)  # compute the multiplicative order
342

If you want something in GF's prime field when using an indeterminant:

>>> 2*t**0  
2 + <-3+3t^2+t^3>
>>> # the line above is equivalent to
>>> Zmod7 = Zmodp(7)
>>> GF([Zmod7(2)])
2 + <-3+3t^2+t^3>

You can run through all non-zero elements of GF by taking powers of t; but this is faster:

>>> for element in GF:
...     print(element)
...
-3t^2-3t-3
-3t^2-3t-2
-3t^2-2t-3
-3t^2-2t-2
-2t^2-3t-3
   ...

Define an elliptic curve using its short Weierstrass form over the Galois field GF

>>> E = nl.EllCurve(2*t**2+t+5, 3*t**0)
>>> E
y^2 = x^3 + (2t^2+t-2)x + 3 over Z/7[t]/<t^3+3t^2-3>

For small order curves, one can generate all finite $\operatorname{GF}(7^3)$-rational points:

>>> for point in nl.finite(E):
...    print(point)
...
(t^2+2t+3, -3t^2-3t-2)
(t^2+2t+3, 3t^2+3t+2)
(2t^2-2, -3t^2-2t-2)
(2t^2-2, 3t^2+2t+2)
(3t^2+t-1, -2t^2-3t-3)
        ...

Counting the point at infinity, the total number of $\operatorname{GF}(7^3)$-rational points on this curve is 378:

>>> len(list(nl.affine(E)))
377

Warning: the last command can take essentially forever for large curves even if the coefficients lie in field of somewhat manageable size — which is to say that, when implementing crypto-systems, one gets more encryption bang for one's buck by replacing a finite field with an elliptic curve over a finite field.

Basic examples

First, numlib provides various number theoretic utilities that may prove useful.

>>> from numlib import gcd, xgcd
>>> gcd(143, 2662)  # 11 since 143 = 11*13 and 2662 = 2*11^3
>>> xgcd(143, 2662)  # (11, -93, 5) since 11 = -93 * 143 + 5 * 2662
>>> -93 * 143 + 5 * 2662  #  = 11

Peruse all available utilities and see more examples by issuing the command pydoc3 numlib.utils at your commandline or by typing, in the interpreter,

>>> import numlib
>>> help(numlib.utils)

To work, in the interpreter, with the integers, $\mathbb{Z}$, modulo a positive integer $n:$

>>> from numlib import Zmod
>>>
>>> R = Zmod(15)  # R is a class that returns instances of integers modulo 15
>>> R(37)  # 7 mod 15
>>> print(R(37))  # 7
>>> x = R(9); y = R(30)
>>> z = 301*x + y**2 + x*y + 1000  # We can do arithmetic and integers such as 301
>>> z  # 4 mod 15                    and 1000 are coerced to integers mod 15
>>> z.isunit()  # True

R in the previous code block is now a class but think of it as a type: the ring, $\mathbb{Z}/15$, of integers modulo 15.

>>> print(R)  # Z/15

Some simple class-level methods are available:

>>> print(', '.join(str(x) for x in R.units())) # R.units() is a Python generator
1, 2, 4, 7, 8, 11, 13, 14  # the multiplicative group of units in Z/15
>>>
>>> phi = len(list(R.units()))  # the order of the group of units
>>> phi  # phi(15) = 8 where phi is Euler's totient function
>>>
>>> R(7)**phi == 1  # True
>>>
>>> # Number theoretically, the last equality holds by Euler's Theorem;
>>> # group theoretically, it follows from Lagrange's Theorem that the
>>> # order of an element of a group must divide the order of the group.
>>>
>>> # Let us find the actual order of R(7):
>>> for i in range(phi):
...     if R(7)**(i+1) == 1:
...         print(i+1)
...         break
4

If we prefer, we can balance the representatives of Z/n about 0:

>>> list(Zmod(10, negatives=True))  # [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
>>> list(Zmod(10, negatives=True).units())  # [-3, -1, 1, 3]

Exercises

  1. Find the multiplicative inverse of 2022 modulo 2027 or show that no such inverse exists.
  2. Write a program that lists all non-zero elements of $\mathbb{Z}/60$ along with their multiplicative orders.
    (a) Is the multiplicative group of units in $\mathbb{Z}/60$ cyclic?
    (b) If so, is the group of units in $\mathbb{Z}/n$ always cyclic?
  3. In the ring $\mathbb{Z}/27720$, solve each of the following equations for $x,$ or argue that no solution exists.
    (a) $26x = 1$
    (b) $833x = 1$
    (c) $143x -7 = 2655$
  4. What are the conditions under which $ax = b$ always has a solution in $\mathbb{Z}/n$? Are those solutions unique?

Finite fields

The quotient ring $\mathbb{Z}/p$ is a field if $p$ is prime since then every non-zero element has a multiplicative inverse. For example:

>>> GF = Zmod(23)  # the field Z/23
>>> GF(8)**-1  #  8 has inverse 3 mod 23; equivalently, we could have typed 1/GF(8)
>>> len(list(PF.units())) == 22  # every non-zero element is a unit (i.e., invertible)
>>> GF.isField()   # True

Finite fields are often called Galois Fields, hence our notation GF in the last code block.

Both GF.units() above and, in fact, GF itself are Python generators. This can be useful, for instance, if we want to brute-force verify that the cubic $1 + x^2 + 3x^3$ is irreducible over $\mathbb{Z}/17$. For this, we use polylib (install with pip install polylib --user).

from numlib import Zmod
from polylib import FPolynomial

f = FPolynomial([1, 0, 1, 3])  # 1 + x^2 +3x^3
GF = Zmod(17)
result = "irreducible"
for x in GF:
    if f.of(x) == 0:
        result = "reducible"
        break

print(f"{f} is {result} in Z/17[x]")

The only way that a cubic $f(x)$ with coefficients in a field $\mathbb{K}$ can be reducible if it has a factor of the form $x-\alpha$ for some $\alpha\in\mathbb{K}$; in the program above, we have used that observation along with the fact that $x-\alpha$ divides $f(x)$ if and only if $f(\alpha)=0$ (which follows from unique factorization in the polynomial ring $\mathbb{K}[x]$ — concretely, since the division algorithm holds in $\mathbb{K}[x]$, we have $f(x) = q(x)(x-\alpha) + f(\alpha)$).

Practical matters involving large integers

When we issue the command Zmod(n) where n is some integer, numlib tries to figure out (using the function numlib.isprime) whether n is prime (so whether Zmod(n) is in fact a field). The function numlib.isprime(n) is fast but it returns True when n is only likely prime. Unexpected behavior may result in the rare case that numlib.isprime is wrong.

If we already know that $p$ is a prime, then we can avoid problems by indicating that:

>>> import numlib
>>> n = 258001471497710271176990892852404413747
>>> GF = numlib.Zmod(n, prime = True)  # no need for Zmod to check if n is prime
>>>
>>> numlib.isprime(n)   # True, so isprime() gets it right this time
>>> GF = numlib.Zmod(n) # so this is equivalent to above for this n

Moreover, if R = Zmod(n), then the generator R.units() simply yields in turn those elements of the generator R which are relatively prime with n. If n is large, this leads to many applications of the Euclidean algorithm.

If the large n is known to be prime, then we already know that everything but zero in R is a unit; consider indicating that (which also saves time when computing inverses) as above:

>>> PF = Zmod(2**3021377-1, prime=True)  # a Mersenne prime with about 900K digits
>>> PF(2)**-1  # this still takes several seconds

Constructing finite fields

Above, we used numlib to quickly construct a finite field of prime order:

>>> from numlib import Zmod
>>> GF = Zmod(17)  # a primefield of order 17
>>> GF.isField()  # True
>>> len(list(GF.units()))  # 16
>>> GF(5)/GF(10)  # since GF is a field, you can divide, this is 9 mod 17
>>> 5/GF(10)  # integers are coerced to the primefield so this is equivalent
>>> GF(5)/10  # so is this
>>> GF(3)+50  # 2, coercion is implemented w/r to all field operations

Of course, we can replace 17 with any prime, $p,$ thereby obtaining the field $\mathbb{Z}/p$ of order $p.$

Not all finite fields have prime order. Any field, $\mathbb{K}$, finite or not, admits a ring homomorphism $\mathbb{Z} \rightarrow \mathbb{K}$ defined by $n \mapsto n\cdot 1_\mathbb{K},$ where $1_\mathbb{K}$ denotes the multiplicative identity of $\mathbb{K}.$ The kernel of this homomorphism is either $\{0\}$ or the ideal $\langle p\rangle = p\cdot\mathbb{Z}=\{np~|~n\in\mathbb{Z}\}$ for some prime $p$ called the characteristic of $\mathbb{K};$ hence, the image of the natural ring homomorphism $\mathbb{Z} \rightarrow \mathbb{K}$ is a copy of either $\mathbb{Z}$ or $\mathbb{Z}/p$ living inside $\mathbb{K}$ (in the latter case, $p$ must be prime since otherwise $\mathbb{K}$ would have non-trivial, non-invertible zero-divisors).

In the case that the natural map $\mathbb{Z} \rightarrow \mathbb{K}$ is injective, so that its image is $\mathbb{Z},$ then the characteristic of $\mathbb{K}$ is defined to be zero and the field of fractions of the image, which is isomorphic to $\mathbb{Q}$, is called the prime field of the infinite field $\mathbb{K}.$ If $\mathbb{Z} \rightarrow \mathbb{K}$ is not injective then the characteristic, $\operatorname{char}(K),$ is positive — some prime $p$ — and the prime field of $\mathbb{K}$ is the image of $\mathbb{Z}$ in $\mathbb{K}$ (which is isomorphic to $\mathbb{Z}/p$).

Whether or not $\mathbb{K}$ is finite, it is a vector space over its prime field. Suppose that a finite field, $\mathbb{K}$, has dimension $n$ as a finite-dimensional vector space over its prime field of order $p$, then $K$ necessarily has order $q = p^n$. How can we construct a finite field of prime power order?

To construct such a field, we need a polynomial $f(x)$ of degree $n$ that is irreducible over $\mathbb{Z}/p.$ Then we simply quotient the polynomial ring $\mathbb{Z}/p[x]$ (consisting of all polynomials with coefficients in $\mathbb{Z}/p$) by the ideal $\langle f(x)\rangle$ generated by the irreducible $f(x)\in \mathbb{Z}/p[x].$

Above, we checked that $1 + x^2 + 3x^3$ is irreducible over $\mathbb{Z}/17.$ We can construct elements of the finite field of order $17^3$ as follows.

>>> from numlib import Zmod, FPmod
>>> from polylib import FPolynomial
>>>
>>> PF = Zmod(17)  # the prime field
>>> x = FPolynomial([0, PF(1)])  # indeterminant for polys over PF
>>> f = 1+x**2+3*x**3  # FPolynomial((1 mod 17, 0 mod 17, 1 mod 17, 3 mod 17))
>>> GF = FPmod(f)
>>> print(GF)  # Z/17[x]/<1 + x^2 + 3x^3>
>>>
>>> # now we can use the class GF to define elements of the Galois field:
>>> p1 = GF([1,2,3,4])  # 11 + 2x + 13x^2 mod 1 + x^2 + 3x^3
>>> p1**-1  # 4 + 12x + 14x^2 mod 1 + x^2 + 3x^3

Suppose, though, that we want to work conveniently in $\mathbb{Z}/p[x] / \langle 1 + x^2 + 3x^3\rangle$ with an indeterminant. Continuing with the interactive session above

>>> # currently x is an element of Z/17[x]
>>> x  # FPolynomial((0 mod 17, 1 mod 17))
>>> x**100 # this is x^100 in Z/17[x]
>>> GF(x**100) # 16 + 7x + x^2 mod 1 + x^2 + 3x^3  <- now it's in the Galois field
>>>
>>> # the notation is clearer if we change the indeterminant to 't'
>>> t = GF([0, 1], 't')
>>> t**100  # 16 + 7t + t^2 mod 1 + t^2 + 3t^3
>>> print(t**100)  # 16 + 7t + t^2
>>>
>>> # alternatively, we can just do this:
>>> t = GF(x, 't')  # t mod 1 + t^2 + 3t^3
>>> t**100  # 16 + 7t + t^2 mod 1 + t^2 + 3t^3

Quotienting $\mathbb{Z}/p[x]$ by the ideal $\langle f(x)\rangle$ generated by an irreducible is wholly analogous to quotienting $\mathbb{Z}$ by the ideal $\langle p\rangle=p\mathbb{Z}$ generated by a prime number. We get a field in both cases, roughly due to the fact that dividing by an irreducible, respectively, a prime, leaves no chance for a zero divisor. In both cases, we are quotienting in a principal ideal domain. In fact, both $\mathbb{K}[x],$ where $\mathbb{K}$ is a field, and $\mathbb{Z}$ are Euclidean domains with Euclidean function $f(x) \mapsto \operatorname{degree}(f(x)),$ respectively, $n \mapsto |n|.$ In a Euclidean domain, we can carry out the division algorithm.

Why is every ideal in $\mathbb{K}[x]$ a principal ideal? Let $f(x)$ be a fixed polynomial (not necessarily irreducible) of minimal degree in a given proper ideal of $\mathbb{K}[x].$ and let $g(x)$ be any other element of that ideal. Then the division algorithm (that is, long division of polynomials) yields $q(x)$ and $r(x)$ satisfying $g(x) = q(x)\cdot f(x)+ r(x)$ where either $r(x)=0$ or $r(x)$ has degree strictly less than that of $f(x).$ But $r(x) = g(x) - q(x)\cdot f(x)$ is an element of the given proper ideal; so that $r(x)$ must be the zero polynomial since, otherwise, the minimality of the degree of $f(x)$ would be violated.

We can always represent an equivalence class in the quotient ring $\mathbb{K}[x]/\langle f(x) \rangle$ with a polynomial of degree less than that of $f(x)$ — just pick any polynomial $g(x)$ in the equivalence class and use the division algorithm to write $g(x) = q(x) \cdot f(x) + r(x);$ then $r(x)$ is the specified representative the equivalence class defined by $g(x).$ The difference of such representatives of any two distinct classes, $r_1(x)$ and $r_2(x)$, cannot be an element of the ideal $\langle f(x)\rangle$; hence, as a vector space, $\mathbb{K}[x]/\langle f(x) \rangle$ is precisely the set of polynomials in $\mathbb{K}[x]$ of degree less than the degree of $f(x)$ with addition and scalar multiplication that of polynomials.

Returning to the case in which $f(x)$ is irreducible in $\mathbb{K}[x],$ let $r(x)$ represent a non-zero element of $\mathbb{K}[x]/\langle f(x) \rangle$ and consider the ideal generated by $r(x)$ and $f(x).$ This is a principal ideal, of course, generated by some polynomial that divides both $r(x)$ and $f(x).$ An irreducible $f(x)$ is only divisible by units in $\mathbb{K}$ so that the ideal in question is the whole ring $\mathbb{K}[x]$. In other words, there exist polynomials $a(x)$ and $b(x)$ in $\mathbb{K}[x]$ satisfying $a(x)\cdot r(x) + b(x)\cdot f(x) = 1_\mathbb{K},$ so that $a(x)$ inverts $r(x)$ modulo $f(x).$ In practice, one finds $a(x)$ using the Euclidean algorithm in $\mathbb{K}[x].$ For example:

>>> from numlib import Zmod, xgcd
>>> from polylib import FPolynomial
>>>
>>> x = FPolynomial([0, Zmod(17)(1)])
>>> # let us invert, in Z/17[x], 1 + 2x + 3x^2 + 4x^3 modulo 1 +x^2 + 3x^4
>>> tup = xgcd(1+2*x+3*x**2+4*x**3, 1+x**2+3*x**3)
>>> tup[0]  # FPolynomial((16 mod 17,)), the gcd is a constant polynomial
>>> print(tup[1]*tup[0][0]**-1)  # 4 + 12x + 14x^2, the inverse

Note that this last interactive session agrees with our previous session in which we worked in the Galois field $\mathbb{Z}/p[x] / \langle 1 + x^2 + 3x^3\rangle.$ In fact, the FPmod class simply calls xgcd when it needs to invert something.

Field extensions

From the previous discussion, we know that every finite field has prime power order and that we can construct such a finite field with order $q=p^n$ by quotienting the polynomial ring $\mathbb{Z}/p[x]$ with the ideal $\langle f(x)\rangle$ generated by an irreducible polynomial in $\mathbb{Z}/p[x].$ Of course, in general, there are different candidates for the irreducible $f.$ Do different choices of $f$ lead to different finite fields of order $q?$

Notice that any homomorphism $\lambda: \mathbb{K}_1 \rightarrow \mathbb{K}_2$ between two fields is a homomorphism of rings whose kernel is an ideal; but a field has no proper ideals, so either the kernel is all of $\mathbb{K}_1$ in which case $\lambda$ is the zero map, or the kernel is $\{0_{\mathbb{K}_1}\}$ so that $\lambda$ is an injection. Hence, there are no quotient fields; only subfields — or, said differently, there are only extension fields.

Furthermore, if $\lambda: \mathbb{K}_1 \rightarrow \mathbb{K}_2$ maps injectively between finite fields, then lambda must be an isomorphism — in fact essentially the identity since lambda must map $1_{\mathbb{K}_1} to $1_{\mathbb{K}_2} — on prime fields. If $\mathbb{K}_1$ and $\mathbb{K}_2$ have the same size, then such a $\lambda$ must be an isomorphism. In other words, up to isomorphism, there only one field of order $q=p^n.$

But what of the construction above? Different choices of the irreducible $f(x)$ lead obviously to element-wise differences but not, we have argued, overall structural dissimilarity in the finite field. It is instructive to think about this in terms of extension fields.

In field theory, the potentially confusion notation $L/K$ means that $L$ is a field that contains $K$ as a subfield; i.e., $L$ is an extension field of $K$ (important: $L/K$ is not a quotient of fields).

For instance, the field $\mathbb{Z}/p[x] / \langle 1 + x^2 + 3x^3\rangle$ is an extension of its prime field — note that said prime field is just image in the quotient group of the constant polynomials (since the multiplicative identity in $\mathbb{Z}/p[x] / \langle 1 + x^2 + 3x^3\rangle$ is just $1 + \langle 1 + x^2 + 3x^3\rangle$).

Now, obviously, since it is irreducible, $f(x) = 1 + x^2 + 3x^3$ does not have a root in $\mathbb{Z}/p;$ but it does have a root in the extension $\mathbb{Z}/p[x] / \langle 1 + x^2 + 3x^3\rangle;$ namely, $x + \langle 1 + x^2 + 3x^3\rangle:$

$$f(x + \langle 1 + x^2 + 3x^3\rangle) = f(x) + \langle 1 + x^2 + 3x^3\rangle = \langle 1 + x^2 + 3x^3\rangle.$$

That $x \in \mathbb{Z}/p[x] / \langle 1 + x^2 + 3x^3\rangle$ is a root of $f(x) = 1 + x^2 + 3x^3$ is a tautology; still, we can verify it concretely. Continuing the previous interactive session:

>>> f.of(t)  # 0 mod 1 + t^2 + 3t^3

Remember that we changed the letter for the indeterminant in GF to t.

Given a field $\mathbb{K}$ and a non-constant polynomial $f(x)\in \mathbb{K}[x]$, one can always build a field extension

Imagine taking two irreducible polynomials, $f_1(x)$ and f_

The chosen $f$ in the last paragraph is not, in general, unique, of course. But if one required that the minimal

Once we have a monic polynomial of degree $r$ the Galois field of order $p^r$ can be realized as the quotient of the polynomial ring $(\mathbb{Z}/p)[x]$ and the ideal generated by the irreducible monic polynomial.

Above we showed that $1 + x^2 + 3x^3$ is irreducible over $\mathbb{Z}/17.$ The same is true for the monic polynomial $6 + 6x^2 + x^3.$

  >>> from polylib import FPolynomial
>>> 1/PF(3) * FPolynomial([1, 0, 1, 3])  # FPolynomial((6 mod 17, 0 mod 17, 6 mod 17, 1 mod 17))
>>> print(1/PF(3) * FPolynomial([1, 0, 1, 3]))  # 6 + 6x^2 + x^3

The quotient field $(\mathbb{Z}/17)[x]/\langle 6 + 6x^2 + x^3\rangle$ is in fact a field of order $17^3$.

We can use numlib to get our hands on this Galois field as follows.

>>> from numlib import Zmod, FPmod
>>> from polylib import FPolynomial
>>> PF = Zmod(17)
>>> GF = FPmod(FPolynomial([PF(6), PF(0), PF(6), PF(1)]))   # A Galois field
>>> print(GF)  # Z/17[x]/<6 + 6x^2 + x^3>

In practice, the symbology of the second to last line is too repetitive. We see better ways to instantiate a Galois field later.

First, let us define an element in our new Galois field, and make some computations.

>>> f1 = GF([1, 2, 3, 2, 3, 4, 5])
>>> f1  # 11 + 16x^2 mod 6 + 6x^2 + x^3

Notice that we passed just a list of integers to GF. We didn't have to bother with wrapping them in PF (because the type of the coefficients is automatically inferred from the irreducible polynomial). Let us now computed in the Galois field.

>>> f1**1000  # 12 + 13x + 14x^2 mod 6 + 6x^2 + x^3
>>> f1**(17**3-1) # 1 mod 6 + 6x^2 + x^3
>>> f2 = GF([8, 12])
>>> f1/f2  # 16 + 10x + 8x^2 mod 6 + 6x^2 + x^3

In practice, we often simplify notation as shown in the following program, which prints out each non-zero and non-identity element of a Galois field of order $3^3$ along with its order.

from numlib import Zmod, FPmod
from polylib import FPolynomial
from itertools import product

PF = Zmod(3)  # the prime field Z/3
t = FPolynomial([0, PF(1)], 't')  # some prefer t for Galois fields
irred = 1 + 2 * t ** 2 + t ** 3  # an irreducible cubic over Z/3

GF = FPmod(irred)  # a Galois field of order 3^3

def find_order(elt):
    """return multiplicative order"""
    for i in range(1, len(list(PF))**irred.degree()):
        if elt ** i == 1:
            return i

orders_ = {}  # dict that maps a non-zero elements of GF to its order
for coeffs in product(PF, repeat=3):  # iterate over all triples
    elt = GF(coeffs)
    if elt != 0:
        orders_[str(elt)] = find_order(elt)

orders = {}  # the reverse dict of order_, with aggregated values
for k, v in orders_.items():
    orders.setdefault(v, []).append(k)

print(f"Orders of non-zero elements of {str(GF)}\n")
print(f"{'order':<8}")
for k, v in orders.items():
    print(f"{k:^5} {', '.join(map(lambda s: ''.join(s.split()), v))}")

Before we run the program, we know that the order of each element must divide $3^3-1=26$ since that's the order of the multiplicative group of units in this case. Here is the output of the program:

Orders of non-zero elements of Z/3[t]/<1 + 2t^2 + t^3>

order
 13   t^2, 2t, 2t+t^2, 2t+2t^2, 1+2t^2, 1+t, 1+t+t^2, 1+2t, 1+2t+t^2, 2+2t^2, 2+t+t^2, 2+2t+t^2
 26   2t^2, t, t+t^2, t+2t^2, 1+t^2, 1+t+2t^2, 1+2t+2t^2, 2+t^2, 2+t, 2+t+2t^2, 2+2t, 2+2t+2t^2
  1   1
  2   2

We see that the multiplicative group of units is in fact cyclic. It turns out that that the group of units is always cyclic (see ...).

Notice that the polynomial $t\in\mathbb{Z}/3[x]/\langle t + 2r^2 +t^3\rangle$ generates the entire group of units. When $t$ is such a generator This is particularly nice

Knowing this, there is no need to break out itertools.product in the code above because the powers of $t$ run through all non-zero elements of the Galois field.

Exercise

  1. Rewrite the program above without using itertools.product and observe that you get the same output.
  2. Write a program that finds all irreducible, monic cubics over $\mathbb{Z}/3[x].$ How many of those lead to $t$ be a generator?

A Galois field of order $p^r$ is often denoted $\operatorname{GF}(p^r)$ where $p$ is prime and $r$ is a positive integer.

Algebraic number fields

If $K$ is a field containing a subfield $k$, then we denote this by $K/k$ and say that the $K$ is an extension $k$. The standard notation $K/k$ is somewhat confusing in that the $/$ does not, here, mean quotient. In fact, all ideals of $K$ are proper so that the morphisms in the category of fields are either zero or injections.

Let $K$ denote a field extension of a ground field $k$; i.e., $K$ is contains

Quadratic field

We can extend the field, $\mathbb{Q}$, of rational numbers by adjoining the complex number $i,$ thereby obtaining the Gaussian rationals, $\mathbb{Q}[i].$

In numlib, we get our hands of the Gaussian rationals as follows.

>>> from fractions import Fraction
>>> from polylib import FPolynomial
>>> from numlib import FPmod
>>> x = FPolynomial([0, Fraction(1)], 'i')
>>> GQ = FPmod(1+x**2)  # The Gaussian rationals
>>> i = GQ([0, 1])
>>> print(', '.join([str(i**j) for j in range(4)]))
1, i, -1, i  # GQ contains the 4th roots of unity as its only finite-order units.

More generally, one can implement any degree 2 extension a — so called quadratic field — of the rationals by adjoining $\sqrt{d}$ where $d$ is a square-free integer; for instance:

>>> x = FPolynomial([0, Fraction(1)])
>>> QF = FPmod(5+x**2)  # The Gaussian rationals

Elliptic Curves

Let us define an elliptic curve, $E$, with Weierstrass normal form $y^2= x^3 + 17x + 20$ over, say, $\mathbb{Z}/43.$

>>> from numlib import Zmod, EllCurve
>>> PF = Zmod(43)  # a prime field
>>> E = EllCurve(PF(17), PF(20))
>>> E
y^2 = 20 + 17x + x^3 over Z/43
>>> E.discriminant() # let's check that the curve is non-singular
21 + <43>
>>> E.j-invariant()
21 + <43>

We can define points on the curve using integers — their correct type will be inferred from the coefficients (17 and 20) used to define the curve:

>>> E(25, 26)
(25, 26) on y^2 = 20 + 17x + x^3 over Z/43
>>> print(E(25, 26))
(25, 26)
>>> E(1,2)
ValueError: (1, 2) is not on y^2 = 20 + 17x + x^3 ...

Let us find all points on the curve:

>>> from itertools import product
>>> count = 0
>>> for coeffs in product(PF,PF):
...     try:
...         print(E(*coeffs))
...         count += 1
...     except:
...         pass
...
(1, 9)
(1, 34)
(4, 18)
(4, 25)
(5, 12)
  ...
(39, 19)
(39, 24)
(41, 8)
(41, 35)
>>> count
46

In total, the curve $E$ consists of 47 points including the point at infinity: any finite point on the curve is a generator:

>>> len(set(n * E(25, 26) for n in range(1, 48)))
47
>>> 47 * E(25, 26)
[0: 1: 0] on y^2 = 20 + 17x + x^3 over Z/43

The curve is an Abelian group; an element's additive inverse is itself with the negated y-coordinate:

>>> E(25, 26) + E(25, -26)
[0: 1: 0] on y^2 = 20 + 17x + x^3 over Z/43

Exercises:

  1. The method of iterating, as above, through the product $\operatorname{PF} \times \operatorname{PF}$ is inefficient in general since it is order $\mathcal{O}(n^2)$ in the size of $\operatorname{PF}.$ (Also, try/except is not cheap.) Meanwhile, the elliptic curve should have roughly the same order as $\operatorname{PF}.$ (Footne to Hasse's thm here). Implement an $\mathcal{O}(n)$ algorithm that finds all points on the curve $E.$ Hint: first compute the squares of all elements of $\operatorname{PF}.$

  2. How many points are on the curve $y^2= x^3 + 1113x + 1932$ over $\mathbb{Z}/2017?$ Is this curve cyclic?

A more correct notation for the curve above is $E(\mathbb{Z}/43);$ then, the name $E$ can be reserved for the set of points $(x,y)$ in the algebraic closure of $\mathbb{Z}/43$ which satisfy $y^2= x^3 + 1113x + 1932$.

In common mathematical parlance, we know that the number of $\mathbb{Z}/43$-rational points of $E$ is $47$; together, those comprise $E(\mathbb{Z}/43).$

It is also good to write $E/\mathbb{F}_{43}$ to indicating where live the coefficients $a$ and $b$ that determine the Weierstrass form of the curve. Note that the $/$ has nothing to do with quotienting, so we wrote $\mathbb{F}_43$ instead of the notation $\mathbb{Z}/{43}$ where the slash does indicate quotienting.

Now consider the set of points in an algebraically closed field that lie on some Weiestrass curve with coefficients $a$ and $b$ elements of a subfield $k$. Since the group addition laws are rational expressions of the coordinates of points lying on the curve, the $K$-rational points of $E$ form a group for any intermediate field $K$.

Of course, if we expand our point of view to an extension field then we generally expect to pick up more up more points. Here is a concrete demonstration:

import numlib as nl
import polylib as pl

PF = nl.Zmod(43)  # a prime field
irreducible = pl.FPolynomial([PF(5), PF(2), PF(1)], 't')  # 5+2t+t^2 in Z/43[t]
GF = nl.FPmod(irreducible)  # GF(43^2)

E =  nl.EllCurve(GF([17]), GF([20]))  # y^2 = 20+17x+x^3 over Z/43[t]/<5+2t+t^2>

squares = {}  # dict that maps squares to their roots
for y in GF:
    squares.setdefault(y**2, []).append(y)

points_of_E = {E(0,1,0)}
for x in GF:
   f_of_x = E.f.of(x)
   if f_of_x in squares:
       for y in squares[f_of_x]:
           points_of_E.add(E(x,y))

print(len(points_of_E))

Notes:

  • Notice that $\operatorname{GF}$ is a generator (that runs through all elements of $\operatorname{GF}(43^2)).$
  • E.f is just the function defining $E:$ 
    print(E.f)  # 20 + 17x + x^3
  • A subtlety is that one must define the curve by specifying coefficients in $\operatorname{GF}$, not $\operatorname{PF}.$ Unless one want to roll one's own Galois field by choosing some particular irreducible, consider using numlib's function GaloisField. So replace this 
    PF = nl.Zmod(43)  # a prime field
irreducible = pl.FPolynomial([PF(5), PF(2), PF(1)], 't')  # 5+2t+t^2 in Z/43[t]
GF = nl.FPmod(irreducible)  # GF(43^2)
    with simply 
    GF = nl.GaloisField(43, 2) # GF(43^2)
    in the program above (after which there is no need to import polylib).

The output of the program is: $1927.$

So over $\operatorname{GF}(43^2),$ $E$ has order $1927.$ The number of those points whose coordinates live in $\operatorname{GF}(43^2)$'s prime field, $\mathbb{F}_{43}$ — i.e., that are $\mathbb{F}_{43}$-rational — is $47.$ Said differently, $E$ has $1927$ $\mathbb{F}_{43^2}$-rational points, $47$ of which are $\mathbb{F}_{43}$-rational.

Of course, $E(\mathbb{F}_{43})$ is a subgroup of order $47$ of $E(\mathbb{F}_{43^2})$ which, in turn, has order $1927 = 41\cdot 47$ (and is cyclic, it turns out).

For convenience, the functionality above is built-in to numlib:

>>> import numlib as nl:
>>> GF = nl.GaloisField(43, 2) # GF(43^2)  # a finite field
>>> E =  nl.EllCurve(GF([17]), GF([20]))   # an elliptic curve over GF
>>> for pt in E:
...     print(pt)
...
(-21-21t, -13-21t)
(-21-21t, 13+21t)
(-21-20t, -21+7t)
(-21-20t, 21-7t)
(-21-19t, -16-12t)
(-21-19t, 16+12t)
         ...

Note: $E$ in the last code block is a generator that runs through all finite $\operatorname{GF}$-rational points on the curve.

>>> len(E)
1926

Hence, $\#E(\mathbb{F}_{43^2}) = 1927.$

References

Todo

Stats

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

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

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:40:00 UTC

Login to resync this project