Calculating trace of arbitrary element of a finite extension binary field GF(2^n)

[geostergiop]

Hi there, thanks for the great work.
I am trying to calculate the trace of x in a binary field GF(2^n) extension, which by expression is simply the sum of all Galois conjugates of α^(2^0), a^(2^1) .....a^(2^n-1) but I am finding it hard to use np.trace with the library.

For a given
GF = galois.GF(2**100)
y = GF(4)

the best way I found was to execute: conjugates = np.unique(y**(2**np.arange(0, 100))).sum()
but I get an error "ValueError: Maximum allowed size exceeded". This is due to np.arange since the table is extremely large. The think is that we dont need a table since the equation is rather simple as a linear sum. Can you suggest something for building the relevant sum maybe using np.power over GF elements? (which also throws a sum error).

Sorry if I am missing something obvious, I am trying to go over your python code and figure this out but haven't found anything as of today.

Thank you for your time!
George

[geostergiop]

Nevermind, my previous assumption is false, there is no underlying library that calculates such conjugates based on a polynomial as far as I see.

[mhostetter]

The issue is that 2**np.arange(0, 100) uses int64 which overflows above 2^63.

In [12]: 2**np.arange(0, 100)                                                                                                                
Out[12]: 
array([                   1,                    2,                    4,
                          8,                   16,                   32,
                         64,                  128,                  256,
                        512,                 1024,                 2048,
                       4096,                 8192,                16384,
                      32768,                65536,               131072,
                     262144,               524288,              1048576,
                    2097152,              4194304,              8388608,
                   16777216,             33554432,             67108864,
                  134217728,            268435456,            536870912,
                 1073741824,           2147483648,           4294967296,
                 8589934592,          17179869184,          34359738368,
                68719476736,         137438953472,         274877906944,
               549755813888,        1099511627776,        2199023255552,
              4398046511104,        8796093022208,       17592186044416,
             35184372088832,       70368744177664,      140737488355328,
            281474976710656,      562949953421312,     1125899906842624,
           2251799813685248,     4503599627370496,     9007199254740992,
          18014398509481984,    36028797018963968,    72057594037927936,
         144115188075855872,   288230376151711744,   576460752303423488,
        1152921504606846976,  2305843009213693952,  4611686018427387904,
       -9223372036854775808,                    0,                    0,
                          0,                    0,                    0,
                          0,                    0,                    0,
                          0,                    0,                    0,
                          0,                    0,                    0,
                          0,                    0,                    0,
                          0,                    0,                    0,
                          0,                    0,                    0,
                          0,                    0,                    0,
                          0,                    0,                    0,
                          0,                    0,                    0,
                          0,                    0,                    0,
                          0])

You can set dtype=object which will use Python ints (which don't overflow). That's what the library does under the hood for GF(2^100) arrays.

In [13]: 2**np.arange(0, 100, dtype=object)                                                                                                  
Out[13]: 
array([1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192,
       16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152,
       4194304, 8388608, 16777216, 33554432, 67108864, 134217728,
       268435456, 536870912, 1073741824, 2147483648, 4294967296,
       8589934592, 17179869184, 34359738368, 68719476736, 137438953472,
       274877906944, 549755813888, 1099511627776, 2199023255552,
       4398046511104, 8796093022208, 17592186044416, 35184372088832,
       70368744177664, 140737488355328, 281474976710656, 562949953421312,
       1125899906842624, 2251799813685248, 4503599627370496,
       9007199254740992, 18014398509481984, 36028797018963968,
       72057594037927936, 144115188075855872, 288230376151711744,
       576460752303423488, 1152921504606846976, 2305843009213693952,
       4611686018427387904, 9223372036854775808, 18446744073709551616,
       36893488147419103232, 73786976294838206464, 147573952589676412928,
       295147905179352825856, 590295810358705651712,
       1180591620717411303424, 2361183241434822606848,
       4722366482869645213696, 9444732965739290427392,
       18889465931478580854784, 37778931862957161709568,
       75557863725914323419136, 151115727451828646838272,
       302231454903657293676544, 604462909807314587353088,
       1208925819614629174706176, 2417851639229258349412352,
       4835703278458516698824704, 9671406556917033397649408,
       19342813113834066795298816, 38685626227668133590597632,
       77371252455336267181195264, 154742504910672534362390528,
       309485009821345068724781056, 618970019642690137449562112,
       1237940039285380274899124224, 2475880078570760549798248448,
       4951760157141521099596496896, 9903520314283042199192993792,
       19807040628566084398385987584, 39614081257132168796771975168,
       79228162514264337593543950336, 158456325028528675187087900672,
       316912650057057350374175801344, 633825300114114700748351602688],
      dtype=object)

Now, you should get a proper output.

In [1]: import numpy as np                                                                                                                   

In [2]: import galois                                                                                                                        

In [3]: GF = galois.GF(2**100)                                                                                                               

In [4]: y = GF(4); y                                                                                                                         
Out[4]: GF(4, order=2^100)

In [5]: y**(2**np.arange(0, 100, dtype=object))                                                                                              
Out[5]: 
GF([4, 16, 256, 65536, 4294967296, 18446744073709551616,
    69058186649150901006106624, 450631821225601268424741715514,
    1156206588031968198419318910436, 1150985234355543272700505874756,
    213660965430823397395969430007, 719396459737944410961108253266,
    210198455863442231265860170905, 1047812155139163570237401688250,
    222251007615744344396447396388, 1068846214586072209481394206039,
    40915739630396188502085518115, 283619708520225820830193823599,
    257283764976813505466728664760, 1098935288167429485858045219268,
    1061474956052807424015776645413, 914224064203654389729228089378,
    851053392276399244688875860475, 1133624594619451218386700261170,
    840495834812281424580733094135, 565610689944036942706726732751,
    49900470411977213026350531700, 98475085706676515235217925665,
    23291294528147893461837318191, 1104313578578610119192149372060,
    525455824979015827083482056407, 201824750422741607408279144304,
    832140615061339079580690496864, 4027381787174237022496547116,
    944475693794830732451548129965, 88041759876869236124054804506,
    938587049184388757753287394424, 34671407309254474879735379448,
    977396836435507789874726436980, 1253435520118533200735009656766,
    1188027258700897440955459304428, 872430869922847754324381014485,
    484347720086247583687739731381, 189974196161498254316684065208,
    803422808993897082209532355826, 957923402196886067028731784015,
    934524018352823895023075906066, 678676404101763832008889926953,
    619200853459819360233847134769, 224578514763007752640052891188,
    188837639203019728408968222935, 378083108619970366480674302081,
    864246463894022465067659885355, 20400021553193909276794980005,
    440818677086358464260585451027, 613313506654633303712435889432,
    62076614658452829904823096914, 760402676617495845124073788544,
    1189508187875205633284189989416, 621000532743654409835900023006,
    1202552390214728699873770142170, 154130370802199007786318554048,
    289712156303014349428148677807, 574526593194922145166613049830,
    20677219316142601459617851799, 909218871523209717312340724157,
    667543309717177531532599129858, 932608483586943905375182214763,
    367608969904948588381879852094, 900879833367711178397110166840,
    679332375192484661892880564253, 1022753661869638130616164463085,
    230851121619673519127339424227, 214700858266212690387782899508,
    95037647599061864611163576007, 1199577604335270893279308632821,
    273581365675725964654613660352, 649416959770818962955289881651,
    724715056602125771024044636662, 1208524735779650180016869889640,
    322529843664957151399023764458, 984000794741333689845347160827,
    501628738434378244316773109904, 1013075303630134048014091371545,
    110557782233671494397638253690, 370259676765293339577833124553,
    1102214004101896047848829694899, 347125207701709972907425833410,
    157108845878646888996671522174, 1173647821343829847964939954523,
    703925673902937133552794014464, 808954428201102640536078409494,
    1081891886911541185126869855971, 1202346232164206256122783514998,
    326005558665964396565755806118, 857749028226308656053006828788,
    723010781495246501567290369433, 502516239967081254476883790814,
    658093088232783877165080018824, 2], order=2^100)

In [8]: conjugates = np.unique(y**(2**np.arange(0, 100, dtype=object)))                                                                      

In [9]: conjugates.sum()                                                                                                                     
Out[9]: GF(0, order=2^100)

Does that help / answer your question? Let me know if you run into more issues.

[geostergiop]

Thank you Matt, indeed this partially solves my problems, although that is due to my erroneous expression of the original issue. Besides calculating the sum I mentioned, I need to calculate the same sum as a trace over a binary field, i.e. also get a single output of 0 or 1 at the end.

To explain a bit, from the theory of finite fields, we know that each element in F_{2^n} can be represented by a binary string of length n, and we also know that F_{2^n} consists of all the possible binary strings of length n. This means that, for each value of a, we have a corresponding binary string. By evaluating a Trace(a) for arbitrary elements 'a' over this binary field we should obtain 2^{n−1} binary values. Now, for each {2^t}, the Trace(a) = Sum a^{2^t} will be an element in the truth table at the position corresponding to the decimal representation of the binary string corresponding to the element a^{2^t}.

This is the reason why I closed the issue myself, because I read your code and afaik I didnt see any relevant functionality and so I will have to code it myself.

If you have any ideas on the matter feel free to help out of course, since I am a bit over my head with the implementation :)

[mhostetter]

Does this wiki article Field trace define what you are describing? I'm not a mathematician, so my field theory isn't complete.

In galois, the function np.trace() is supported, which computes the trace of a 2-D matrix, which is the sum of elements on the diagonal. It seems this trace is different.

From what I've read, and from what you've said, it seems that you want to take the sum of the conjugates of a in L, but the result is guaranteed to be in the base field K?

I did a little test to build my own intuition and see if this result matches up with what you'd expect. Here is GF(2^4) for simplicity, because it can be completely displayed.

In [1]: import numpy as np                                                                                                                   

In [2]: import galois                                                                                                                        

In [3]: GF = galois.GF(2**4)                                                                                                                 

In [4]: def trace(a): 
   ...:     field = type(a) 
   ...:     p, m = field.characteristic, field.degree 
   ...:     conjugates = a**(p**np.arange(0, m, dtype=a.dtype)) 
   ...:     return conjugates.sum() 
   ...:                                                                                                                                      

In [5]: for a in GF.Elements(): 
   ...:     print(a, trace(a)) 
   ...:                                                                                                                                      
GF(0, order=2^4) GF(0, order=2^4)
GF(1, order=2^4) GF(0, order=2^4)
GF(2, order=2^4) GF(0, order=2^4)
GF(3, order=2^4) GF(0, order=2^4)
GF(4, order=2^4) GF(0, order=2^4)
GF(5, order=2^4) GF(0, order=2^4)
GF(6, order=2^4) GF(0, order=2^4)
GF(7, order=2^4) GF(0, order=2^4)
GF(8, order=2^4) GF(1, order=2^4)
GF(9, order=2^4) GF(1, order=2^4)
GF(10, order=2^4) GF(1, order=2^4)
GF(11, order=2^4) GF(1, order=2^4)
GF(12, order=2^4) GF(1, order=2^4)
GF(13, order=2^4) GF(1, order=2^4)
GF(14, order=2^4) GF(1, order=2^4)
GF(15, order=2^4) GF(1, order=2^4)

From the wiki article, it says

and it seems that GF(2^4) has 8 0s and 8 1s.

Here is GF(3^2):

In [6]: GF = galois.GF(3**2)                                                                                                                 

In [7]: for a in GF.Elements(): 
   ...:     print(a, trace(a)) 
   ...:                                                                                                                                      
GF(0, order=3^2) GF(0, order=3^2)
GF(1, order=3^2) GF(2, order=3^2)
GF(2, order=3^2) GF(1, order=3^2)
GF(3, order=3^2) GF(1, order=3^2)
GF(4, order=3^2) GF(0, order=3^2)
GF(5, order=3^2) GF(2, order=3^2)
GF(6, order=3^2) GF(2, order=3^2)
GF(7, order=3^2) GF(1, order=3^2)
GF(8, order=3^2) GF(0, order=3^2)

And here is GF(5^2).

In [8]: GF = galois.GF(5**2)                                                                                                                 

In [9]: for a in GF.Elements(): 
   ...:     print(a, trace(a)) 
   ...:                                                                                                                                      
GF(0, order=5^2) GF(0, order=5^2)
GF(1, order=5^2) GF(2, order=5^2)
GF(2, order=5^2) GF(4, order=5^2)
GF(3, order=5^2) GF(1, order=5^2)
GF(4, order=5^2) GF(3, order=5^2)
GF(5, order=5^2) GF(1, order=5^2)
GF(6, order=5^2) GF(3, order=5^2)
GF(7, order=5^2) GF(0, order=5^2)
GF(8, order=5^2) GF(2, order=5^2)
GF(9, order=5^2) GF(4, order=5^2)
GF(10, order=5^2) GF(2, order=5^2)
GF(11, order=5^2) GF(4, order=5^2)
GF(12, order=5^2) GF(1, order=5^2)
GF(13, order=5^2) GF(3, order=5^2)
GF(14, order=5^2) GF(0, order=5^2)
GF(15, order=5^2) GF(3, order=5^2)
GF(16, order=5^2) GF(0, order=5^2)
GF(17, order=5^2) GF(2, order=5^2)
GF(18, order=5^2) GF(4, order=5^2)
GF(19, order=5^2) GF(1, order=5^2)
GF(20, order=5^2) GF(4, order=5^2)
GF(21, order=5^2) GF(1, order=5^2)
GF(22, order=5^2) GF(3, order=5^2)
GF(23, order=5^2) GF(0, order=5^2)
GF(24, order=5^2) GF(2, order=5^2)

I don't know if those results are correct, but they appear to satisfy the above property.

Since all these sums result in values that are in the extension field L and the base field K (i.e., the field element polynomial is degree-0), you can cast / convert / reduce (don't know the mathematical term) the field element in L to just the base field K by keeping only the 0-th degree term of the polynomial.

In galois, the .vector() function converts a field element to it's polynomial coefficients / vector representation. Here's a little example with an element from GF(5^2).

In [12]: with GF.display("poly"): 
    ...:     a = GF(16) 
    ...:     print(a) 
    ...:     print(a.vector()) 
    ...:                                                                                                                                     
GF(3α + 1, order=5^2)
GF([3, 1], order=5)

So, back to the trace() function... You can simply modify the return statement to get the resulting sum as an element of K and not L. Notice the second print value is an element in GF(5) not GF(5^2).

In [13]: def trace(a): 
    ...:     field = type(a) 
    ...:     p, m = field.characteristic, field.degree 
    ...:     conjugates = a**(p**np.arange(0, m, dtype=a.dtype)) 
    ...:     return conjugates.sum().vector()[-1] 
    ...:                                                                                                                                     

In [14]: for a in GF.Elements(): 
    ...:     print(a, trace(a)) 
    ...:                                                                                                                                     
GF(0, order=5^2) GF(0, order=5)
GF(1, order=5^2) GF(2, order=5)
GF(2, order=5^2) GF(4, order=5)
GF(3, order=5^2) GF(1, order=5)
GF(4, order=5^2) GF(3, order=5)
GF(5, order=5^2) GF(1, order=5)
GF(6, order=5^2) GF(3, order=5)
GF(7, order=5^2) GF(0, order=5)
GF(8, order=5^2) GF(2, order=5)
GF(9, order=5^2) GF(4, order=5)
GF(10, order=5^2) GF(2, order=5)
GF(11, order=5^2) GF(4, order=5)
GF(12, order=5^2) GF(1, order=5)
GF(13, order=5^2) GF(3, order=5)
GF(14, order=5^2) GF(0, order=5)
GF(15, order=5^2) GF(3, order=5)
GF(16, order=5^2) GF(0, order=5)
GF(17, order=5^2) GF(2, order=5)
GF(18, order=5^2) GF(4, order=5)
GF(19, order=5^2) GF(1, order=5)
GF(20, order=5^2) GF(4, order=5)
GF(21, order=5^2) GF(1, order=5)
GF(22, order=5^2) GF(3, order=5)
GF(23, order=5^2) GF(0, order=5)
GF(24, order=5^2) GF(2, order=5)

Are these outputs correct / is this what you were looking to do? Again, I apologize but this particular mathematical concept is new to me, so I may have missed something / misunderstood something.

[geostergiop]

The article does describe what I am refering to but I think the computations are not correct (Galois fields are not my area of expertise either, so I need to cross-check some stuff before being sure).
Quick fact check: I loaded GF(2³) in your test code which is easy to check and got the following:

GF(2^3):
  characteristic: 2
  degree: 3
  order: 8
  irreducible_poly: x^3 + x + 1
  is_primitive_poly: True
  primitive_element: x
GF(0, order=2^3) GF(0, order=2^3)
GF(1, order=2^3) GF(1, order=2^3)
GF(2, order=2^3) GF(0, order=2^3)
GF(3, order=2^3) GF(1, order=2^3)
GF(4, order=2^3) GF(0, order=2^3)
GF(5, order=2^3) GF(1, order=2^3)
GF(6, order=2^3) GF(0, order=2^3)
GF(7, order=2^3) GF(1, order=2^3)

which does not seem to be correct over a primitive polynomial of p(x) = x³ + x + 1 for F_2³ since a complete list with the trace for all elements in that finite field would be:

I believe the problem lies in the fact that Tr() calculation over python code must be executed on the polynomial roots and not on decimal elements (although I need to check this with the code and have a more bulletproof opinion).

I will come back to you when I return to office.

[geostergiop]

...also two other side notes;
(1) FYI tried to see results over a big GF(2**100)

GF = galois.GF(2**100)
print(GF.properties)
for a in GF.Elements(): 
    print(a, trace(a))

and the recursive loop throws an error:

Traceback (most recent call last):
  File "scalar_mult.py", line 312, in <module>
    for a in GF.Elements():
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 453, in Elements
    return cls.Range(0, cls.order, step=1, dtype=dtype)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 367, in Range
    return array.view(cls)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 1011, in __array_finalize__
    self._check_array_values(obj)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 254, in _check_array_values
    if np.any(array < 0) or np.any(array >= cls.order):
TypeError: '<' not supported between instances of 'range' and 'int'

and

(2) if I try to create GF(2**256) I get the following error:

LookupError(f"Frank Luebeck's database of Conway polynomials doesn't contain an entry for GF({characteristic}^{degree}). See here http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/index.html for his complete list of polynomials.\n\nAlternatively, you can construct irreducible polynomials with `galois.irreducible_poly(p, m)` or primitive polynomials with `galois.primitive_poly(p, m)`.")

but I dont seem to be able to construct the polynomial x²⁵⁶+x²⁴¹+x¹⁷⁸+x¹²¹+1 (i.e. the primitive binary polynomial for GF(2**256) ) and create a GF object. Can you show me how to do that?

Thanks again. Your help is really valuable.

[mhostetter]

Ok, that's helpful. So in the figure you posted, it is representing beta values as powers of alpha, the primitive element. In galois, the default representation of an element is the "integer" representation, which is the integer equivalent of the polynomial representation. The other possible representation is the "power" representation, which represents each element as a power of alpha. See here for more details.

Here is an example of those different display modes.

In [1]: import galois                                                                                                                        

In [2]: GF = galois.GF(2**3)                                                                                                                 

In [3]: x = GF.Elements()                                                                                                                    

# The default representation as "int"
In [4]: x                                                                                                                                    
Out[4]: GF([0, 1, 2, 3, 4, 5, 6, 7], order=2^3)

# The "poly" representation
In [5]: GF.display("poly"); x                                                                                                                
Out[5]: GF([0, 1, α, α + 1, α^2, α^2 + 1, α^2 + α, α^2 + α + 1], order=2^3)

# The "power" representation
In [6]: GF.display("power"); x                                                                                                               
Out[6]: GF([0, 1, α, α^3, α^2, α^6, α^4, α^5], order=2^3)

There's also a repr_table() method that compares the representations, if that's new to you. Here's an example. Notice the primitive element alpha = x.

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

In [12]: print(GF.repr_table())                                                                                                              
╔═══════╤═════════════╤═══════════╤═════════╗
║ Power │  Polynomial │   Vector  │ Integer ║
║═══════╪═════════════╪═══════════╪═════════║
║   0   │      0      │ [0, 0, 0] │    0    ║
╟───────┼─────────────┼───────────┼─────────╢
║  x^0  │      1      │ [0, 0, 1] │    1    ║
╟───────┼─────────────┼───────────┼─────────╢
║  x^1  │      x      │ [0, 1, 0] │    2    ║
╟───────┼─────────────┼───────────┼─────────╢
║  x^2  │     x^2     │ [1, 0, 0] │    4    ║
╟───────┼─────────────┼───────────┼─────────╢
║  x^3  │    x + 1    │ [0, 1, 1] │    3    ║
╟───────┼─────────────┼───────────┼─────────╢
║  x^4  │   x^2 + x   │ [1, 1, 0] │    6    ║
╟───────┼─────────────┼───────────┼─────────╢
║  x^5  │ x^2 + x + 1 │ [1, 1, 1] │    7    ║
╟───────┼─────────────┼───────────┼─────────╢
║  x^6  │   x^2 + 1   │ [1, 0, 1] │    5    ║
╚═══════╧═════════════╧═══════════╧═════════╝

So to compute the values from your table, we'll need to order the element as ascending powers of alpha. Here's an example.

In [1]: import numpy as np                                                                                                                   

In [2]: import galois                                                                                                                        

In [3]: GF = galois.GF(2**3)                                                                                                                 

In [4]: alpha = GF.primitive_element; alpha                                                                                                  
Out[4]: GF(2, order=2^3)

# An array of elements from alpha^0 to alpha^6
In [5]: x = alpha**np.arange(0, GF.order - 1)                                                                                                

# Add 0 = alpha^-Inf to the beginning of the array
In [6]: x = np.insert(x, 0, 0)                                                                                                               

# The array of element displayed in the "int" representation
In [7]: x                                                                                                                                    
Out[7]: GF([0, 1, 2, 4, 3, 6, 7, 5], order=2^3)

In [8]: GF.display("power");

# The array of elements displayed as powers of alpha (the order you want)
In [9]: x                                                                                                                                    
Out[9]: GF([0, 1, α, α^2, α^3, α^4, α^5, α^6], order=2^3)

In [10]: def trace(a): 
    ...:     field = type(a) 
    ...:     p, m = field.characteristic, field.degree 
    ...:     conjugates = a**(p**np.arange(0, m, dtype=a.dtype)) 
    ...:     return conjugates.sum().vector()[-1] 
    ...:                                                                                                                                     

In [11]: for beta in x: 
    ...:     print(beta, trace(beta)) 
    ...:                                                                                                                                     
GF(0, order=2^3) GF(0, order=2)
GF(1, order=2^3) GF(1, order=2)
GF(α, order=2^3) GF(0, order=2)
GF(α^2, order=2^3) GF(0, order=2)
GF(α^3, order=2^3) GF(1, order=2)
GF(α^4, order=2^3) GF(0, order=2)
GF(α^5, order=2^3) GF(1, order=2)
GF(α^6, order=2^3) GF(1, order=2)

Be warned, for your GF(2^100) field, you won't want to use GF.display("poly") because it computes the discrete logs on the fly to get the exponent of alpha. In such a large field, this is prohibitively costly, so printing will take forever. Just an FYI...

[mhostetter]

Regarding your other two issues...

For one, that error output is a bug, and I'll fix it. However, you won't want to run GF.Elements() on the GF(2^100) field. It will create an array with size 2^100, which will take all of your memory and maybe crash your computer.

For two, for GF(p^m) the default irreducible polynomial (if not explicitly specified) is a Conway polynomial C_{p,m}. We use Frank Luebeck's database of Conway polynomials, although not all have been found or tabulated. This is the case with C_{2, 256}. If you already know of such an irreducible polynomial, as you say, you can create a polynomial object as follows.

In [14]: poly = galois.Poly.Degrees([256, 241, 178, 121, 0]); poly                                                                           
Out[14]: Poly(x^256 + x^241 + x^178 + x^121 + 1, GF(2))

In [15]: galois.is_irreducible(poly)                                                                                                         
Out[15]: True

There are a number of ways to create polynomials, see galois.Poly.

Then you can create your field like this. The constructor will search for a primitive element (alpha) of the irreducible polynomial you specify. If you already have one, it would be more efficient to pass that in explicitly. You can find a primitive element by alpha = galois.primitive_element(poly). NOTE, the properties erroneously labels is_primitive_poly as False when it's True.

In [21]: GF = galois.GF(2**256, irreducible_poly=poly, primitive_element=2, verify=False)                                                    

In [22]: print(GF.properties)                                                                                                                
GF(2^256):
  characteristic: 2
  degree: 256
  order: 115792089237316195423570985008687907853269984665640564039457584007913129639936
  irreducible_poly: x^256 + x^241 + x^178 + x^121 + 1
  is_primitive_poly: False
  primitive_element: x

You could also use syntax like this by passing in string equivalents of the polynomials.

In [21]: GF = galois.GF(2**256, irreducible_poly="x^256 + x^241 + x^178 + x^121 + 1", primitive_element="x", verify=False)                                                    

NOTE: I'm passing in verify=False because my prime factorization algorithm is choking on factoring 2^256 - 1, which is needed to verify your irreducible polynomial is in fact primitive, which a google search confirms.

I'll add issues for:

• 1's error message
• 2's issue factoring 2^256 - 1
• 2's erroneously labeling GF(2^256) as not having a primitive polynomial

Sorry for these minor bugs. I rarely use such large fields... 😞

[geostergiop]

Thanks Matt, I am aware of the theory, that's what I was refering to earlier when I said "python code must be executed on the polynomial roots and not on decimal elements". Thing is I was missing knowledge of steps In[4] to In[8] above + ways to add the poly.

I'll verify the above hopefully within the week and let you know if anything new comes up.

Your help is valuable and your library is very good. Keep up the good work!

[mhostetter]

@geostergiop I'm working to add the finite field trace, and corresponding norm, as methods of Galois field arrays. x = GF([1, 2, 3, 4]) would invoke the trace using x.field_trace() or x.field_norm(). It's .field_trace() and not .trace() to deconflict with the linear algebra sum along the diagonal. I'll add unit tests too. Will report back once merged onto master.

[geostergiop]

Hey Matt, great! I didn't have time to work on it cause this week is hectic. Hopefully will find some time within the weekend.
Again, thanks for this.

[mhostetter]

@geostergiop I just merged #189 onto master. It adds .field_trace() and .field_norm() methods to Galois field arrays. The documentation (minimal) can be found here.

Since these features are on master and not pushed to PyPI in a new version yet, you'll need to pip install from a git source. You can do that this way.

$ pip3 uninstall galois
$ pip3 install git+https://github.com/mhostetter/galois.git

Any feedback is appreciated.

[geostergiop]

Hi again Matt, hope you are well. Just installed your new version and ran a quick check on GF(2**3), seems that field trace returns the decimal trace and not the polynomial version we built previously, output doesn't return the same result you built manually. Specifically:
In:

GF = galois.GF(2**3) 
print(GF.properties)

x = GF.Elements()
print(x.field_trace())
print(x.field_norm())

Out:

GF(2^3):
  characteristic: 2
  degree: 3
  order: 8
  irreducible_poly: x^3 + x + 1
  is_primitive_poly: True
  primitive_element: x
GF([0, 1, 0, 1, 0, 1, 0, 1], order=2)
GF([0, 1, 1, 1, 1, 1, 1, 1], order=2)

Instead of GF([0, 1, 0, 0, 1, 0 ,1, 1], order=2) which should be the case for the field trace of GF(2**3). It seems that it produces the original decimal trace and not the polynomial field one we built in the quoted answer above.

** Quotting previous post here for reference**

So to compute the values from your table, we'll need to order the element as ascending powers of alpha. Here's an example.

In [1]: import numpy as np                                                                                                                   

In [2]: import galois                                                                                                                        

In [3]: GF = galois.GF(2**3)                                                                                                                 

In [4]: alpha = GF.primitive_element; alpha                                                                                                  
Out[4]: GF(2, order=2^3)

# An array of elements from alpha^0 to alpha^6
In [5]: x = alpha**np.arange(0, GF.order - 1)                                                                                                

# Add 0 = alpha^-Inf to the beginning of the array
In [6]: x = np.insert(x, 0, 0)                                                                                                               

# The array of element displayed in the "int" representation
In [7]: x                                                                                                                                    
Out[7]: GF([0, 1, 2, 4, 3, 6, 7, 5], order=2^3)

In [8]: GF.display("power");

# The array of elements displayed as powers of alpha (the order you want)
In [9]: x                                                                                                                                    
Out[9]: GF([0, 1, α, α^2, α^3, α^4, α^5, α^6], order=2^3)

In [10]: def trace(a): 
    ...:     field = type(a) 
    ...:     p, m = field.characteristic, field.degree 
    ...:     conjugates = a**(p**np.arange(0, m, dtype=a.dtype)) 
    ...:     return conjugates.sum().vector()[-1] 
    ...:                                                                                                                                     

In [11]: for beta in x: 
    ...:     print(beta, trace(beta)) 
    ...:                                                                                                                                     
GF(0, order=2^3) GF(0, order=2)
GF(1, order=2^3) GF(1, order=2)
GF(α, order=2^3) GF(0, order=2)
GF(α^2, order=2^3) GF(0, order=2)
GF(α^3, order=2^3) GF(1, order=2)
GF(α^4, order=2^3) GF(0, order=2)
GF(α^5, order=2^3) GF(1, order=2)
GF(α^6, order=2^3) GF(1, order=2)

As always, thanks for the support. I ll be sure to reference the entire project with detailed presentation in our paper, should we manage to publish it of course :)

[mhostetter]

Hey. The issue that you're having is the input to .field_trace(), not the output. GF.Elements() returns all the field elements in lexicographically-increasing polynomial order (which is also increasing integer order), not in "powers of alpha" order. For example:

In [1]: import galois

In [2]: GF = galois.GF(2**3)

# The "integer" representations of the field elements
In [3]: x = GF.Elements(); x
Out[3]: GF([0, 1, 2, 3, 4, 5, 6, 7], order=2^3)

# These integers are equivalent to these polynomials
In [4]: GF.display("poly"); x
Out[4]: GF([0, 1, α, α + 1, α^2, α^2 + 1, α^2 + α, α^2 + α + 1], order=2^3)

# These polynomials are equivalent to these powers of alpha, the primitive element
In [5]: GF.display("power"); x
Out[5]: GF([0, 1, α, α^3, α^2, α^6, α^4, α^5], order=2^3)

# The outputs do match your table, they're just in a different order
In [7]: for i in range(x.size):
   ...:     print(x[i], x[i].field_trace())
   ...: 
GF(0, order=2^3) GF(0, order=2)
GF(1, order=2^3) GF(1, order=2)
GF(α, order=2^3) GF(0, order=2)
GF(α^3, order=2^3) GF(1, order=2)
GF(α^2, order=2^3) GF(0, order=2)
GF(α^6, order=2^3) GF(1, order=2)
GF(α^4, order=2^3) GF(0, order=2)
GF(α^5, order=2^3) GF(1, order=2)

To get the array x in order of powers of alpha, we have to construct it explicitly. For example:

In [10]: alpha = GF.primitive_element; alpha
Out[10]: GF(α, order=2^3)

In [11]: x = alpha**np.arange(0, GF.order-1); x
Out[11]: GF([1, α, α^2, α^3, α^4, α^5, α^6], order=2^3)

In [12]: x = np.insert(x, 0, 0); x
Out[12]: GF([0, 1, α, α^2, α^3, α^4, α^5, α^6], order=2^3)

In [13]: for i in range(x.size):
    ...:     print(x[i], x[i].field_trace())
    ...: 
GF(0, order=2^3) GF(0, order=2)
GF(1, order=2^3) GF(1, order=2)
GF(α, order=2^3) GF(0, order=2)
GF(α^2, order=2^3) GF(0, order=2)
GF(α^3, order=2^3) GF(1, order=2)
GF(α^4, order=2^3) GF(0, order=2)
GF(α^5, order=2^3) GF(1, order=2)
GF(α^6, order=2^3) GF(1, order=2)

Hope this helps. And I appreciate the citation. I'm always trying to improve the library, so all the feedback (warts and all) are greatly appreciated.

[geostergiop]

Hey. The issue that you're having is the input to .field_trace(), not the output. GF.Elements() returns all the field elements in lexicographically-increasing polynomial order (which is also increasing integer order), not in "powers of alpha" order.

Sorry I thought that .field_trace() included the code for the polynomial order. Will check again tommorrow.
Thanks!

[mhostetter]

GF.Elements() will always return elements in this order. I realize the documentation may not be clear on that. All GF.display() does is change the displayed representation of the same underlying element.

In [2]: GF = galois.GF(2**3)

# The "integer" representations of the field elements
In [3]: x = GF.Elements(); x
Out[3]: GF([0, 1, 2, 3, 4, 5, 6, 7], order=2^3)

# These integers are equivalent to these polynomials
In [4]: GF.display("poly"); x
Out[4]: GF([0, 1, α, α + 1, α^2, α^2 + 1, α^2 + α, α^2 + α + 1], order=2^3)

There currently is no function to produce the list of elements in "powers of alpha" order. Perhaps, I could/should amend the GF.Elements() API to add an order keyword argument, e.g. def Elements(self, order="int", dtype=None):. This would work as it currently does by default, but would allow you (for instance) to do this:

In [16]: GF = galois.GF(2**3)

# Would return the elements in order of increasing powers of alpha. Note, the display mode is still "int"
In [17]: GF.Elements(order="power")
Out[17]: GF([0, 1, 2, 4, 3, 6, 7, 5], order=2^3)

# After converting the display mode to "power", you'll see the elements in the ascending order expected
In [18]: GF.display("power");

In [19]: x
Out[19]: GF([0, 1, α, α^2, α^3, α^4, α^5, α^6], order=2^3)

[geostergiop]

Matt, I ran multiple experiments and seems to be ok with small fields, big fields I get some mixed results but I have a firm belief that the problem is on my calculations, not your code.
Quick question that might be able to shed light: Is there a way in your library that can allow me to restrict operations within a subset of a GF field? e.g. set GF(2^8) but restrict all calculations to the maximum no. of elements for order (2^8 - 47) (obviously for cases where maximum element is still a polynomial on x^7.

Didn't seem to find any coding solution on that one, if you know one it will help a lot towards verifying my calculations.

Thanks, as always.

[mhostetter]

A couple questions / thoughts on your performance issues:

1. Computing .field_trace() in any field should take roughly the same amount of time. I'm curious if your slow down is due to using display="poly".
2. The display mode "poly" is not O(1) time. It computes the discrete log p = log_α(x) of the element to be displayed x to determine the power of alpha p, and displays the element x as α^p. The discrete log, in the naive implementation, has running time O(N). So you should not use display="poly" for very large fields, like your GF(2^100).
3. If you'd like to share the code that runs "fast" and the one that runs "slow", I might be able to shed some light.

Quick question that might be able to shed light: Is there a way in your library that can allow me to restrict operations within a subset of a GF field? e.g. set GF(2^8) but restrict all calculations to the maximum no. of elements for order (2^8 - 47) (obviously for cases where maximum element is still a polynomial on x^7.

Are you asking how to produce an array of field elements, not necessarily all the elements? I'm not sure what

set GF(2^8) but restrict all calculations to the maximum no. of elements for order (2^8 - 47)

means.

[geostergiop]

My issue is not in terms of calculation speed but in results, i.e. I get unexpected .field_trace() results (e.g. was expecting 1 but got 0), but as I said this must be an error in my calculations, not in your implementation.

TL;DR, I am trying to calculate the trace of elements from a prime field GF(p) where p is prime but cannot be expressed as p = 2^k so there is no 1-1 transformation to a binary extension field. Thus, I am trying to develop a calculation solution where I map GF1 = GF(p) elements onto the closest GF2 = GF(2^k) field where order(GF1) < order(GF2) and perform polynomial trace calculations on the latter while restricting elements to GF1 order.

For example, I tried the following but didnt seem to do any difference:

def f_trace(a, gfp):     # gfp is the largest element from GF1 expressed as a polynomialin GF2
    field = type(a) 
    p, m = field.characteristic, field.degree 
    conjugates = a**(p**np.arange(0, m, dtype=a.dtype)) 
    
    # delete all occurrences greater than gfp (i.e. p)
    result = conjugates[ (conjugates < gfp) ]
        
    return conjugates.sum().vector()[-1] 

Nevermind, this goes beyond your library's dev code; I was just wandering if you had come across something similar to propose a possible solution.

[mhostetter]

No worries. I am new to the concept to the field trace. Your issue, and some cursory research of my own since, is the totality of my knowledge on the subject. However, it is my understanding that the field trace is computed on extension fields (only) and returns results in subfields of the extension field. For example, L is the extension field and K is a subfield.

Prime fields GF(p) do not have subfields, so I don't believe the field trace is defined over them (could stand to be corrected).

TL;DR, I am trying to calculate the trace of elements from a prime field GF(p) where p is prime but cannot be expressed as p = 2^k so there is no 1-1 transformation to a binary extension field. Thus, I am trying to develop a calculation solution where I map GF1 = GF(p) elements onto the closest GF2 = GF(2^k) field where order(GF1) < order(GF2) and perform polynomial trace calculations on the latter while restricting elements to GF1 order.

This can be done with this library, however I'm not sure the result is meaningful. This is my understanding of what you're trying to do.

In [1]: import galois

# The desired prime for the prime field GF(p)
In [2]: p = 211; galois.is_prime(p)
Out[2]: True

# The next power of 2 greater than p
In [3]: order = 2**8

# The desired prime field GF(p), where order(GF1) < order(GF2)
In [4]: GF1 = galois.GF(p); print(GF1.properties)
GF(211):
  characteristic: 211
  degree: 1
  order: 211
  irreducible_poly: x + 209
  is_primitive_poly: True
  primitive_element: 2

# The larger binary extension field GF(2^k), where order(GF1) < order(GF2)
In [5]: GF2 = galois.GF(order); print(GF2.properties)
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: x^8 + x^4 + x^3 + x^2 + 1
  is_primitive_poly: True
  primitive_element: x

# Here are all the elements of GF(211) which are all integers
In [6]: x = GF1.Elements(); x
Out[6]: 
GF([  0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,
     14,  15,  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,
     28,  29,  30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  40,  41,
     42,  43,  44,  45,  46,  47,  48,  49,  50,  51,  52,  53,  54,  55,
     56,  57,  58,  59,  60,  61,  62,  63,  64,  65,  66,  67,  68,  69,
     70,  71,  72,  73,  74,  75,  76,  77,  78,  79,  80,  81,  82,  83,
     84,  85,  86,  87,  88,  89,  90,  91,  92,  93,  94,  95,  96,  97,
     98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
    112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125,
    126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139,
    140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153,
    154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167,
    168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181,
    182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195,
    196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209,
    210], order=211)

# Here are those integers from GF(211) converted to elements of GF(2^8). Note, the integer 5 from GF(211) maps the field
# element "x^2 + 1" in GF(2^8). I don't believe this transformation is mathematically meaningful (?), but it can be done
# with the library. Again note, the elements are displayed in the integer representation, but could also be printed in the
# polynomial or power representation.
In [7]: y = GF2(x); y
Out[7]: 
GF([  0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,
     14,  15,  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,
     28,  29,  30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  40,  41,
     42,  43,  44,  45,  46,  47,  48,  49,  50,  51,  52,  53,  54,  55,
     56,  57,  58,  59,  60,  61,  62,  63,  64,  65,  66,  67,  68,  69,
     70,  71,  72,  73,  74,  75,  76,  77,  78,  79,  80,  81,  82,  83,
     84,  85,  86,  87,  88,  89,  90,  91,  92,  93,  94,  95,  96,  97,
     98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
    112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125,
    126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139,
    140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153,
    154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167,
    168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181,
    182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195,
    196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209,
    210], order=2^8)

# For completeness, here are the elements in y displayed as polynomials over GF(2) with degree less than 8.
# They don't print very nicely :(
In [9]: with GF2.display("poly"):
   ...:     print(y)
   ...: 
GF([0, 1, α, α + 1, α^2, α^2 + 1, α^2 + α, α^2 + α + 1, α^3, α^3 + 1,
    α^3 + α, α^3 + α + 1, α^3 + α^2, α^3 + α^2 + 1, α^3 + α^2 + α,
    α^3 + α^2 + α + 1, α^4, α^4 + 1, α^4 + α, α^4 + α + 1, α^4 + α^2,
    α^4 + α^2 + 1, α^4 + α^2 + α, α^4 + α^2 + α + 1, α^4 + α^3,
    α^4 + α^3 + 1, α^4 + α^3 + α, α^4 + α^3 + α + 1, α^4 + α^3 + α^2,
    α^4 + α^3 + α^2 + 1, α^4 + α^3 + α^2 + α, α^4 + α^3 + α^2 + α + 1,
    α^5, α^5 + 1, α^5 + α, α^5 + α + 1, α^5 + α^2, α^5 + α^2 + 1,
    α^5 + α^2 + α, α^5 + α^2 + α + 1, α^5 + α^3, α^5 + α^3 + 1,
    α^5 + α^3 + α, α^5 + α^3 + α + 1, α^5 + α^3 + α^2,
    α^5 + α^3 + α^2 + 1, α^5 + α^3 + α^2 + α, α^5 + α^3 + α^2 + α + 1,
    α^5 + α^4, α^5 + α^4 + 1, α^5 + α^4 + α, α^5 + α^4 + α + 1,
    α^5 + α^4 + α^2, α^5 + α^4 + α^2 + 1, α^5 + α^4 + α^2 + α,
    α^5 + α^4 + α^2 + α + 1, α^5 + α^4 + α^3, α^5 + α^4 + α^3 + 1,
    α^5 + α^4 + α^3 + α, α^5 + α^4 + α^3 + α + 1, α^5 + α^4 + α^3 + α^2,
    α^5 + α^4 + α^3 + α^2 + 1, α^5 + α^4 + α^3 + α^2 + α,
    α^5 + α^4 + α^3 + α^2 + α + 1, α^6, α^6 + 1, α^6 + α, α^6 + α + 1,
    α^6 + α^2, α^6 + α^2 + 1, α^6 + α^2 + α, α^6 + α^2 + α + 1, α^6 + α^3,
    α^6 + α^3 + 1, α^6 + α^3 + α, α^6 + α^3 + α + 1, α^6 + α^3 + α^2,
    α^6 + α^3 + α^2 + 1, α^6 + α^3 + α^2 + α, α^6 + α^3 + α^2 + α + 1,
    α^6 + α^4, α^6 + α^4 + 1, α^6 + α^4 + α, α^6 + α^4 + α + 1,
    α^6 + α^4 + α^2, α^6 + α^4 + α^2 + 1, α^6 + α^4 + α^2 + α,
    α^6 + α^4 + α^2 + α + 1, α^6 + α^4 + α^3, α^6 + α^4 + α^3 + 1,
    α^6 + α^4 + α^3 + α, α^6 + α^4 + α^3 + α + 1, α^6 + α^4 + α^3 + α^2,
    α^6 + α^4 + α^3 + α^2 + 1, α^6 + α^4 + α^3 + α^2 + α,
    α^6 + α^4 + α^3 + α^2 + α + 1, α^6 + α^5, α^6 + α^5 + 1,
    α^6 + α^5 + α, α^6 + α^5 + α + 1, α^6 + α^5 + α^2,
    α^6 + α^5 + α^2 + 1, α^6 + α^5 + α^2 + α, α^6 + α^5 + α^2 + α + 1,
    α^6 + α^5 + α^3, α^6 + α^5 + α^3 + 1, α^6 + α^5 + α^3 + α,
    α^6 + α^5 + α^3 + α + 1, α^6 + α^5 + α^3 + α^2,
    α^6 + α^5 + α^3 + α^2 + 1, α^6 + α^5 + α^3 + α^2 + α,
    α^6 + α^5 + α^3 + α^2 + α + 1, α^6 + α^5 + α^4, α^6 + α^5 + α^4 + 1,
    α^6 + α^5 + α^4 + α, α^6 + α^5 + α^4 + α + 1, α^6 + α^5 + α^4 + α^2,
    α^6 + α^5 + α^4 + α^2 + 1, α^6 + α^5 + α^4 + α^2 + α,
    α^6 + α^5 + α^4 + α^2 + α + 1, α^6 + α^5 + α^4 + α^3,
    α^6 + α^5 + α^4 + α^3 + 1, α^6 + α^5 + α^4 + α^3 + α,
    α^6 + α^5 + α^4 + α^3 + α + 1, α^6 + α^5 + α^4 + α^3 + α^2,
    α^6 + α^5 + α^4 + α^3 + α^2 + 1, α^6 + α^5 + α^4 + α^3 + α^2 + α,
    α^6 + α^5 + α^4 + α^3 + α^2 + α + 1, α^7, α^7 + 1, α^7 + α,
    α^7 + α + 1, α^7 + α^2, α^7 + α^2 + 1, α^7 + α^2 + α,
    α^7 + α^2 + α + 1, α^7 + α^3, α^7 + α^3 + 1, α^7 + α^3 + α,
    α^7 + α^3 + α + 1, α^7 + α^3 + α^2, α^7 + α^3 + α^2 + 1,
    α^7 + α^3 + α^2 + α, α^7 + α^3 + α^2 + α + 1, α^7 + α^4,
    α^7 + α^4 + 1, α^7 + α^4 + α, α^7 + α^4 + α + 1, α^7 + α^4 + α^2,
    α^7 + α^4 + α^2 + 1, α^7 + α^4 + α^2 + α, α^7 + α^4 + α^2 + α + 1,
    α^7 + α^4 + α^3, α^7 + α^4 + α^3 + 1, α^7 + α^4 + α^3 + α,
    α^7 + α^4 + α^3 + α + 1, α^7 + α^4 + α^3 + α^2,
    α^7 + α^4 + α^3 + α^2 + 1, α^7 + α^4 + α^3 + α^2 + α,
    α^7 + α^4 + α^3 + α^2 + α + 1, α^7 + α^5, α^7 + α^5 + 1,
    α^7 + α^5 + α, α^7 + α^5 + α + 1, α^7 + α^5 + α^2,
    α^7 + α^5 + α^2 + 1, α^7 + α^5 + α^2 + α, α^7 + α^5 + α^2 + α + 1,
    α^7 + α^5 + α^3, α^7 + α^5 + α^3 + 1, α^7 + α^5 + α^3 + α,
    α^7 + α^5 + α^3 + α + 1, α^7 + α^5 + α^3 + α^2,
    α^7 + α^5 + α^3 + α^2 + 1, α^7 + α^5 + α^3 + α^2 + α,
    α^7 + α^5 + α^3 + α^2 + α + 1, α^7 + α^5 + α^4, α^7 + α^5 + α^4 + 1,
    α^7 + α^5 + α^4 + α, α^7 + α^5 + α^4 + α + 1, α^7 + α^5 + α^4 + α^2,
    α^7 + α^5 + α^4 + α^2 + 1, α^7 + α^5 + α^4 + α^2 + α,
    α^7 + α^5 + α^4 + α^2 + α + 1, α^7 + α^5 + α^4 + α^3,
    α^7 + α^5 + α^4 + α^3 + 1, α^7 + α^5 + α^4 + α^3 + α,
    α^7 + α^5 + α^4 + α^3 + α + 1, α^7 + α^5 + α^4 + α^3 + α^2,
    α^7 + α^5 + α^4 + α^3 + α^2 + 1, α^7 + α^5 + α^4 + α^3 + α^2 + α,
    α^7 + α^5 + α^4 + α^3 + α^2 + α + 1, α^7 + α^6, α^7 + α^6 + 1,
    α^7 + α^6 + α, α^7 + α^6 + α + 1, α^7 + α^6 + α^2,
    α^7 + α^6 + α^2 + 1, α^7 + α^6 + α^2 + α, α^7 + α^6 + α^2 + α + 1,
    α^7 + α^6 + α^3, α^7 + α^6 + α^3 + 1, α^7 + α^6 + α^3 + α,
    α^7 + α^6 + α^3 + α + 1, α^7 + α^6 + α^3 + α^2,
    α^7 + α^6 + α^3 + α^2 + 1, α^7 + α^6 + α^3 + α^2 + α,
    α^7 + α^6 + α^3 + α^2 + α + 1, α^7 + α^6 + α^4, α^7 + α^6 + α^4 + 1,
    α^7 + α^6 + α^4 + α], order=2^8)

# Compute the field trace of those elements. I assume you are trying to use these values as a substitute for
# x.field_trace() ?
In [10]: y.field_trace()
Out[10]: 
GF([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0], order=2)

Is that helpful?

[geostergiop]

That's what I did and seems to "work" in terms of transition, despite my wierd results.
Maybe the issue lies on the fact that I am trying to divmod() two polynomials as elements of a binary extension Field. I tried to find a way to convert elements from a GF(2^k) into galois.Poly() objects but didn't find something. So, I tried explicitly calculating this with the familiar code:

GF = cGF() # that's a GF(2**256) with a manual irr. polynomial as did previously with your code
GF.display("poly")

xg = GF(g)
xp = GF(p)

print( divmod(xg,xp) )  
# this always results in remainder = 0 and some polynomial but the result is incorrect in terms of what should return for polynomials g and p

but the divmod results are incorrect. Do you know what am I missing?

[mhostetter]

Division of elements in GF(2^k) is not equivalent to division of their equivalent degree-k-1 polynomials over GF(2). This tutorial explains some of the theory of how finite field arithmetic in extension fields works.

In finite fields, a / b is not performed by polynomial long division. Instead, the multiplicative inverse b_inv of b is found, such that b * b_inv = 1 in the field. Then, a / b == a * b_inv. The multiplicative inverse b_inv is found through the Extended Euclidean Algorithm.

Here's an example with GF(2^8). This demonstrates division in the finite field. As you noted, the remainder is always zero because in finite fields every element has a multiplicative inverse. Said differently, dividing any two elements always results in a quotient also in the finite field, and thus the remainder is always zero.

In [1]: import galois

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

# A random element of GF(2^8)
In [3]: a = GF(73); a
Out[3]: GF(α^6 + α^3 + 1, order=2^8)

# A random element of GF(2^8)
In [5]: b = GF(35); b
Out[5]: GF(α^5 + α + 1, order=2^8)

# q is the quotient and r is the remainder
In [6]: q, r = divmod(a, b)

In [7]: q, r
Out[7]: (GF(α^4 + α^3 + α, order=2^8), GF(0, order=2^8))

# By definition q*b + r == a
In [8]: q*b + r
Out[8]: GF(α^6 + α^3 + 1, order=2^8)

# Note q*b + r equals a
In [9]: a
Out[9]: GF(α^6 + α^3 + 1, order=2^8)

In this next code block, I convert those elements in GF(2^8) into polynomials over GF(2) with degree less than 8. This answers one of your questions. The vector() method converts the elements into their polynomial / vector coefficients over their prime subfield. Hopefully this example is illustrative.

In [10]: a
Out[10]: GF(α^6 + α^3 + 1, order=2^8)

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

In [12]: galois.Poly(a.vector())
Out[12]: Poly(x^6 + x^3 + 1, GF(2))

And now here is the polynomial arithmetic in GF(2), which is different than in the finite field.

In [12]: a_poly = galois.Poly(a.vector()); a_poly
Out[12]: Poly(x^6 + x^3 + 1, GF(2))

In [13]: b_poly = galois.Poly(b.vector()); b_poly
Out[13]: Poly(x^5 + x + 1, GF(2))

# q is the quotient and r is the remainder
In [14]: q_poly, r_poly = divmod(a_poly, b_poly)

In [15]: q_poly, r_poly
Out[15]: (Poly(x, GF(2)), Poly(x^3 + x^2 + x + 1, GF(2)))

# By definition q*b + r == a
In [16]: q_poly*b_poly + r_poly
Out[16]: Poly(x^6 + x^3 + 1, GF(2))

# Note q*b + r equals a
In [17]: a_poly
Out[17]: Poly(x^6 + x^3 + 1, GF(2))

Is that helpful?

[geostergiop]

Yes, you are right, silly of me sorry its being too long and I think I am at a burnout stage...

In [12]: a_poly = galois.Poly(a.vector()); a_poly
Out[12]: Poly(x^6 + x^3 + 1, GF(2))
In [13]: b_poly = galois.Poly(b.vector()); b_poly
Out[13]: Poly(x^5 + x + 1, GF(2)) # q is the quotient and r is the remainder
In [14]: q_poly, r_poly = divmod(a_poly, b_poly)

that's exactly what I was looking for. Couldn't locate the galois.Poly(b.vector()) code. Will run stuff with a clear head next week.
Thanks mate,
G

[mhostetter]

Cool, hope things work as expected!

[geostergiop]

Hi again Matt, probably stumbled upon another bug (?). Trying to run a .field_trace() on an element like this:

def cGF():
    poly = galois.Poly.Degrees([257,84,72,68,0]) # polynomial = 256, 241, 178, 121, 0 | worse = [256, 10, 5, 2, 0]
    galois.is_irreducible(poly)
    
    GF = galois.GF((2**257), irreducible_poly=poly, primitive_element=2, verify=False) 
    
    return GF

GF = cGF()
print(GF.properties)
GF.display("poly")

x = GF(largeInt[0])

tr1 = x.field_trace()

but I get an error that I do not get on other large GF(2^m) extension fields.

GF(2^257):
  characteristic: 2
  degree: 257
  order: 231584178474632390847141970017375815706539969331281128078915168015826259279872
  irreducible_poly: x^257 + x^84 + x^72 + x^68 + 1
  is_primitive_poly: True
  primitive_element: x
Traceback (most recent call last):
  File "tests.py", line 292, in <module>
    tr1 = x.field_trace() # f_trace(x, gf_p)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 768, in field_trace
    return subfield(trace)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 118, in __new__
    return cls._array(array, dtype=dtype, copy=copy, order=order, ndmin=ndmin)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 173, in _array
    array_like = cls._check_array_like_object(array_like)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 197, in _check_array_like_object
    cls._check_array_values(array_like)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 257, in _check_array_values
    raise ValueError(f"{cls.name} arrays must have elements in `0 <= x < {cls.order}`, not {values}.")
ValueError: GF(2) arrays must have elements in `0 <= x < 2`, not 205392157522362943464215028907705044652389188466109774154079079375363838991217.

Runs fine on other small or large (e.g. GF(2^256) or GF(2^283) ) binary extension fields.
What do you think?

[mhostetter]

The issue is that the specified irreducible polynomial is not actually irreducible. Since the field was created with verify=False, it didn't check and alert you of that. It created the field and performed the arithmetic as if the polynomial was irreducible.

What happened was the trace arithmetic should result in a value 0 <= x < 2 in the subfield GF(2), but it didn't here because the field isn't really a field (i.e., the arithmetic isn't correct due to the non-irreducible reducing polynomial).

In [1]: import galois

In [2]: poly = galois.Poly.Degrees([257,84,72,68,0]); poly
Out[2]: Poly(x^257 + x^84 + x^72 + x^68 + 1, GF(2))

In [3]: galois.is_irreducible(poly)
Out[3]: False

That polynomial can be reduced (factored) into these irreducible polynomial factors.

In [4]: galois.factors(poly)
Out[4]: 
([Poly(x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1, GF(2)),
  Poly(x^16 + x^15 + x^11 + x^9 + x^6 + x^5 + x^3 + x + 1, GF(2)),
  Poly(x^18 + x^13 + x^11 + x^10 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + 1, GF(2)),
  Poly(x^48 + x^47 + x^45 + x^44 + x^42 + x^41 + x^39 + x^38 + x^37 + x^36 + x^35 + x^34 + x^32 + x^31 + x^28 + x^26 + x^24 + x^23 + x^20 + x^19 + x^18 + x^17 + x^15 + x^14 + x^12 + x^11 + x^10 + x^7 + x^6 + 
x^4 + x^3 + x + 1, GF(2)),
  Poly(x^167 + x^166 + x^165 + x^164 + x^161 + x^159 + x^155 + x^153 + x^150 + x^148 + x^146 + x^143 + x^140 + x^138 + x^137 + x^133 + x^131 + x^125 + x^123 + x^122 + x^121 + x^120 + x^117 + x^116 + x^113 + x^109 + x^108 + x^107 + x^106 + x^104 + x^102 + x^98 + x^97 + x^96 + x^93 + x^88 + x^85 + x^84 + x^83 + x^81 + x^78 + x^77 + x^74 + x^71 + x^69 + x^68 + x^67 + x^65 + x^64 + x^63 + x^62 + x^60 + x^59 + x^58 + 
x^57 + x^56 + x^54 + x^52 + x^47 + x^42 + x^41 + x^39 + x^38 + x^36 + x^34 + x^33 + x^31 + x^29 + x^28 + x^26 + x^22 + x^21 + x^18 + x^16 + x^15 + x^14 + x^12 + x^10 + x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1, GF(2))],
 [1, 1, 1, 1, 1])

I suspect maybe there was a typo in entering that polynomial? Did you get it from somewhere?

[geostergiop]

Thanks for the quick reply, I am out of office now but will check on Monday. Happened to another one, maybe it was a typo, have a dedicated system that produces irr. polys (verified ones), maybe a typo slipped in during transfer. Thanks!

[mhostetter]

No problem. Please let me know if you find errors / discrepancies with galois.irreducible_poly() or galois.is_irreducible(). I have a fair bit of unit tests, but there could be subtle bugs that I would love to find / kill.

[geostergiop]

Hi Matt, ok dug a bit more, indeed the poly was a typo, sorry for that. In any case, the same error is thrown when trying to get minimal polynomials of elements in larger groups (this time I checked, irr. polys are ok). Namely:

def cGF():
    poly = galois.Poly.Degrees([256, 241, 178, 121, 0]) # polynomial = [256, 241, 178, 121, 0]
    print("...",galois.is_irreducible(poly))
    
    GF = galois.GF((2**256), irreducible_poly=poly, primitive_element=2, verify=False) 
    
    return GF

GF = cGF()
x = GF(4) # or any other, it doesn't matter

print(x.field_trace())
print( galois.minimal_poly(x) )

gives back:

GF(0, order=2)
Traceback (most recent call last):
  File "tests.py", line 27, in <module>
    print( galois.minimal_poly(x) )
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_polys\_functions.py", line 118, in minimal_poly
    poly = Poly(poly.coeffs, field=field.prime_subfield)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_polys\_poly.py", line 111, in __new__
    coeffs, field = cls._convert_coeffs(coeffs, field)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_polys\_poly.py", line 138, in _convert_coeffs
    coeffs = field([int(-field(abs(c))) if c < 0 else c for c in coeffs])
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 118, in __new__
    return cls._array(array, dtype=dtype, copy=copy, order=order, ndmin=ndmin)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 173, in _array
    array_like = cls._check_array_like_object(array_like)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 190, in _check_array_like_object
    array_like = cls._check_iterable_types_and_values(array_like)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 218, in _check_iterable_types_and_values
    cls._check_array_values(item)
  File "C:\Users\infosec\AppData\Local\Programs\Python\Python38\lib\site-packages\galois\_fields\_array.py", line 257, in _check_array_values
    raise ValueError(f"{cls.name} arrays must have elements in `0 <= x < {cls.order}`, not {values}.")
ValueError: GF(2) arrays must have elements in `0 <= x < 2`, not 68236339013663482758815020232508424264410036681570859108965054260988304132902.

At first I thought that elements tested simply do not have minimal polys but then I tried hundreds of elements and different large fields (e.g. 2^256, 2^283) and always get the same error. Works fine with small GFs (e.g. GF(2^8).
Any insights?

[mhostetter]

@geostergiop can you open a new issue with the comment you just posted?

I'm not sure why it's doing that. Perhaps the minimal polynomial calculation is wrong? I'll need to dig into it. But it's an issue with galois.minimal_poly() not FieldArray.field_trace(). Thanks for bringing this to my attention.

[mhostetter]

@geostergiop I found the problem. I'll open the issue and reference this one.

[mhostetter]

@geostergiop the issue has been resolved and merged into master. The root cause of the issue was the same as discussed here.

If you uninstall and re-install and re-test, you should be fine. Keep me updated on your progress / and further issues.

$ pip3 uninstall galois
$ pip3 install git+https://github.com/mhostetter/galois

[geostergiop]

Perfect, will check tomorrow. As always, you are very efficient, thanks Matt!

[mhostetter]

FieldArray.field_trace() was added in the last release v0.0.22. I'm going to close this issue for now.

@geostergiop if you run into more issues, either related or unrelated to .field_trace(), please open another issue or discussion and I'd be happy to help you. But I think this issue has fulfilled its purpose.

[geostergiop]

Yes Matt, thanks!
No more issues until know, will let you know.