Finite Fields Module

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.

class viff.field.FieldElement

Common base class for elements.

class viff.field.GF256(value)

Models an element of the GF(2^8) field.

modulus

Field modulus, always 256.

__sub__(other)

__xor__(other)

Subtraction and exclusive-or. Since GF(2^8) has characteristic 2, these two operations are identical to addition.

__add__(other)

Add this and another GF256 element.

>>> GF256(0x01) + GF256(0x01)
[0]
>>> GF256(0x01) + GF256(0x02)
[3]

Adding integers works too, the other operand is coerced into a GF256 element automatically:

>>> GF256(0x01) + 1
[0]

__mul__(other)

Multiply this and another GF256.

>>> GF256(0) * GF256(47)
[0]
>>> GF256(2) * GF256(3)
[6]
>>> GF256(16) * GF256(32)
[54]

__pow__(exponent)

Exponentiation.

__div__(other)

Division.

__neg__()

Negation.

__invert__()

Invertion.

Raises ZeroDivisionError if trying to inverse the zero element.

__eq__(other)

Equality testing.

Testing for equality with integers works as expected:

>>> GF256(10) == 10
True

__nonzero__()

Truth value testing.

Returns False if this element is zero, True otherwise. This allows GF256 elements to be used directly in Boolean formula:

>>> bool(GF256(0))
False
>>> bool(GF256(1))
True
>>> x = GF256(1)
>>> not x
False

__int__()

Extract integer value from the field element.

>>> int(GF256(10))
10

viff.field.GF(modulus)

Generate a Galois (finite) field with the given modulus.

The modulus must be a prime:

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

A modulus of 256 is special since it returns the GF(2^8) field even though 256 is no prime:

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

Please note, that if you wish to calculate square roots, the modulus must be a Blum prime (congruent to 3 mod 4):

>>> 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

viff.field.FakeGF(modulus)

Construct a fake field.

These fields should only be used in benchmarking. They work like any other field except that all computations will give -1 as the result:

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