Representation of elements in field extensions

[kstauffer]

I'm familiar with Magma, where field elements are represented as polynomials or in some basis. Like:

p := 2^61 - 1;
Fq<J> := ext<GF(p) | Polynomial([1,0,1])>;
J^2;
J^3;
J^4;

Prints

2305843009213693950
2305843009213693950*J
1

Which makes sense because J^2 = -1, J^3 = -J, and J^4 = 1. In addition to doing arithmetic with basis element J, you can create field elements by coercing a (little endian) list of integers: Fq![2,1]; prints J + 2. The reverse is Eltseq(J+2) -> [2, 1].

Given that guilty knowledge, the galois package confuses me. I guess that each field element is represented as a Python integer, and decomposed into coefficients by iterated divmod. So that J + 2 above is represented in this package as:

Fq = GF(p, [1,0,1])
Fq(p+2)

Indeed:

[GF(2305843009213693951, order=2305843009213693951^2),
 GF(2305843009213693950, order=2305843009213693951^2),
 GF(5316911983139663484697699213480296450, order=2305843009213693951^2),
 GF(1, order=2305843009213693951^2)]

So, given an element of GF(p^2), how do I extract its coefficients?

[mhostetter]

Good question. I'm not very familiar with Magma (only SageMath which uses Magma under the hood). Is J in your examples the polynomial indeterminate of the polynomial basis? Or is it a primitive element of the field? That clarity might help.

In galois, there are few ways to interact with other bases. It's true the default "display mode" for galois is the integer representation. So for an extension field GF(p^m), each element is a degree-m-1 polynomial in GF(p). The integer representation of a polynomial would be calculated like this.

In [1]: import galois                                                                          

In [2]: p = 2**61 - 1                                                                          

In [3]: GF = galois.GF(p**2, irreducible_poly=galois.Poly([1,0,1], field=galois.GF(p)))                                                             

In [4]: a = GF.Random(5); a                                                                    
Out[4]: 
GF([1440367246014816086838033797032250559,
    3668530470912041289134466205567456835,
    3576300674463896594486903799465496077,
    896627843836132695332653142013258235,
    3116134409782253745563875733924795894], order=2305843009213693951^2)

So when you create random elements, they are displayed in their integer representation. However this can be changed with GF.display().

In [5]: GF.display("poly");                                                                    

In [6]: a                                                                                      
Out[6]: 
GF([624659718922490652x + 688885438845804507,
    1590971482556842319x + 717069117336344466,
    1550973184286052583x + 2124823861810470644,
    388850342479251469x + 1953928539080094216,
    1351407878737101852x + 2188862880881498642], order=2305843009213693951^2)

The N-D array of field elements in GF(p^m) can be converted to a (N+1)-D array (with last dimension equal to m) of its polynomial coefficients in GF(p) using vector().

In [7]: a.vector()                                                                             
Out[7]: 
GF([[624659718922490652, 688885438845804507],
    [1590971482556842319, 717069117336344466],
    [1550973184286052583, 2124823861810470644],
    [388850342479251469, 1953928539080094216],
    [1351407878737101852, 2188862880881498642]], order=2305843009213693951)

Also, to create Galois field arrays in GF(p^m), there are a variety of methods using the polynomial basis. First, polynomial strings are accepted (and can be mix-and-matched with integer representations). This is more of a novelty and not useful for large data.

In [18]: GF(["x + 1", 1234, "76x + 54", p + 2])                                                
Out[18]: GF([x + 1, 1234, 76x + 54, x + 2], order=2305843009213693951^2)

For larger sets of data, if you have the appropriate polynomial coefficients in GF(p) a GF(p^m) Galois field array can be created by calling the Vector() constructor.

In [19]: GF.Vector([[1, 1], [0, 1234], [76, 54], [1, 2]])                                      
Out[19]: GF([x + 1, 1234, 76x + 54, x + 2], order=2305843009213693951^2)

And this works for any dimension of data.

In [20]: GFp = galois.GF(p)

In [23]: V = GFp.Random((3,3,2)); V                                                            
Out[23]: 
GF([[[1375578243991712354, 2253073386248978518],
     [2046580625395772872, 1915442889918544694],
     [1973163818725461044, 1467080881905109794]],

    [[767578612938699007, 993306079815297737],
     [627500482415891433, 1419746516063160641],
     [2174983968132597379, 1737381374548413549]],

    [[1251615168131846540, 21041992497815045],
     [360779194190359428, 1964261772441506698],
     [1504344701484279108, 332620284881070422]]], order=2305843009213693951)

In [24]: GF.Vector(V)                                                                          
Out[24]: 
GF([[1375578243991712354x + 2253073386248978518,
     2046580625395772872x + 1915442889918544694,
     1973163818725461044x + 1467080881905109794],
    [767578612938699007x + 993306079815297737,
     627500482415891433x + 1419746516063160641,
     2174983968132597379x + 1737381374548413549],
    [1251615168131846540x + 21041992497815045,
     360779194190359428x + 1964261772441506698,
     1504344701484279108x + 332620284881070422]], order=2305843009213693951^2)

I hope this somewhat addresses your desired use case.

[mhostetter]

Thinking about this more. I believe J in your case is the polynomial indeterminate for the polynomial basis. In that case, mimicking your Magma code, I get this in galois:

In [1]: import numpy as np                                                                     

In [2]: import galois                                                                          

In [3]: p = 2**61 - 1                                                                          

In [4]: GF = galois.GF(p**2, irreducible_poly=galois.Poly([1,0,1], field=galois.GF(p)))                                                             

In [5]: J = GF(p); J                                                                           
Out[5]: GF(2305843009213693951, order=2305843009213693951^2)

In [6]: J**np.arange(1, 5)                                                                     
Out[6]: 
GF([2305843009213693951, 2305843009213693950,
    5316911983139663484697699213480296450, 1], order=2305843009213693951^2)

In [7]: GF.display("poly");                                                                    

In [8]: J**np.arange(1, 5)                                                                     
Out[8]: GF([x, 2305843009213693950, 2305843009213693950x, 1], order=2305843009213693951^2)

In [10]: (J**np.arange(1, 5)).vector()                                                         
Out[10]: 
GF([[1, 0],
    [0, 2305843009213693950],
    [2305843009213693950, 0],
    [0, 1]], order=2305843009213693951)

[kstauffer]

The display method and the Vector factory function are exactly what I needed. Thanks! (In the Magma code, J is not an indeterminate, rather it is an element of GF(p^2) that is not an element of GF(p). J is a square root of -1.)

[mhostetter]

For posterity...

As of v0.0.19 it is easier to work with and display elements in extension fields. While the default display mode for field elements is their integer representation (since the elements are stored in NumPy arrays as integers), the display mode can be modified directly at class construction time to display elements from GF(p^m) as polynomials over GF(p) with degree less than m.

In [1]: import galois                                                                                                                                                                        

In [2]: galois.__version__                                                                                                                                                                   
Out[2]: '0.0.19'

In [3]: GF = galois.GF(2**4, display="poly")                                                                                                                                                 

In [4]: print(GF.properties)                                                                                                                                                                 
GF(2^4):
  characteristic: 2
  degree: 4
  order: 16
  irreducible_poly: x^4 + x + 1
  is_primitive_poly: True
  primitive_element: x

In [5]: GF.Random(3)                                                                                                                                                                         
Out[5]: GF([1, α^3 + α, α + 1], order=2^4)

Elements can be created using their polynomial representation as a string or from an array of coefficients (in degree-descending order).

# Create elements from their integer or polynomial representation
In [6]: GF(["1", "x^3 + x", 3])                                                                                                                                                          
Out[6]: GF([1, α^3 + α, α + 1], order=2^4)

# Create elements from their polynomial coefficients (vector representation)
In [7]: a = GF.Vector([[0,0,0,1], [1,0,1,0], [0,0,1,1]]); a                                                                                                                                  
Out[7]: GF([1, α^3 + α, α + 1], order=2^4)

Galois field elements can be converted back into their polynomial coefficients (vector representation) over their prime subfield using the vector() method.

In [8]: a.vector()                                                                                                                                                                           
Out[8]: 
GF([[0, 0, 0, 1],
    [1, 0, 1, 0],
    [0, 0, 1, 1]], order=2)

Hopefully as more people use this library and more feedback is provided, the user experience can improve! 😄