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

Bitwise xor for field elements:

>>> z ^ z
>>> z ^ 0
>>> 1 ^ z


>>> x**3

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

>>> x.sqrt()

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.

Inheritance diagram of GF256


Field modulus, always 256.


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


Add this and another GF256 element.

>>> GF256(0x01) + GF256(0x01)
>>> GF256(0x01) + GF256(0x02)

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

>>> GF256(0x01) + 1



Equality testing.

Testing for equality with integers works as expected:

>>> GF256(10) == 10

Extract integer value from the field element.

>>> int(GF256(10))


Raises ZeroDivisionError if trying to inverse the zero element.


Multiply this and another GF256.

>>> GF256(0) * GF256(47)
>>> GF256(2) * GF256(3)
>>> GF256(16) * GF256(32)



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))
>>> bool(GF256(1))
>>> x = GF256(1)
>>> not x



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)

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

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
>>> a * b
>>> a.sqrt()
>>> a.bit(100)

Previous topic

Utility Functions Module

Next topic

Shamir Module

This Page