Module field

source code

Modeling of Galois (finite) fields. The GF function creates classes which implements Galois (finite) fields of prime order whereas the GF256 class implements the the GF(2^8) field with characteristic 2.

All fields work the same: instantiate an object from a field to get hold of an element of that field. Elements implement the normal arithmetic one would expect: addition, multiplication, etc.

Defining a field:

>>> Zp = GF(19)

Defining field elements:

>>> x = Zp(10)
>>> y = Zp(15)
>>> z = Zp(1)

Addition and subtraction (with modulo reduction):

>>> x + y
{6}
>>> x - y
{14}

Bitwise xor for field elements:

>>> z ^ z
{0}
>>> z ^ 0
{1}
>>> 1 ^ z
{0}

Exponentiation:

>>> x**3
{12}

Square roots can be found for elements based on GF fields with a Blum prime modulus (see GF for more information):

>>> x.sqrt()
{3}

Field elements from different fields cannot be mixed, you will get a type error if you try:

>>> Zq = GF(17)
>>> z = Zq(2)
>>> x + z
Traceback (most recent call last):
    ...
TypeError: unsupported operand type(s) for +: 'GFElement' and 'GFElement'

The reason for the slightly confusing error message is that x and z are instances of two different classes called GFElement.

>>> Z23 = GF(23) # works
>>> Z10 = GF(10) # not a prime
Traceback (most recent call last):
    ...
ValueError: 10 is not a prime

>>> GF256 = GF(256)
>>> print GF256(1)
[1]

>>> Z17 = GF(17) # 17 % 4 == 1, so 17 is no Blum prime
>>> x = Z17(10)
>>> x.sqrt()
Traceback (most recent call last):
    ...
AssertionError: Cannot compute square root of {10} with modulus 17

>>> F = FakeGF(1031)
>>> a = F(123)
>>> b = F(234)
>>> a + b
{{1030}}
>>> a * b
{{1030}}
>>> a.sqrt()
{{1030}}
>>> a.bit(100)
1