Package viff :: Module field
[hide private]
[frames] | no frames]

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.

Classes [hide private]
  FieldElement
Common base class for elements.
  GF256
Models an element of the GF(2^8) field.
Functions [hide private]
 
_generate_tables()
Generate multiplication and inversion tables.
source code
 
GF(modulus)
Generate a Galois (finite) field with the given modulus.
source code
 
FakeGF(modulus)
Construct a fake field.
source code
Variables [hide private]
  _inv_table = {1: [1], 2: [141], 3: [246], 4: [203], 5: [82], 6...
Inversion table.
  _mul_table = {(0, 0): [0], (0, 1): [0], (0, 2): [0], (0, 3): [...
Multiplication table.
  _field_cache = {256: <class 'viff.field.GF256'>}
Cached fields.
Function Details [hide private]

_generate_tables()

source code 

Generate multiplication and inversion tables.

This updates the _mul_table and _inv_table. The generator used is 0x03.

Code adapted from http://www.samiam.org/galois.html.

GF(modulus)

source code 

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

FakeGF(modulus)

source code 

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

Variables Details [hide private]

_inv_table

Inversion table.

Maps a value x to x^-1. See _generate_tables.

Value:
{1: [1],
 2: [141],
 3: [246],
 4: [203],
 5: [82],
 6: [123],
 7: [209],
 8: [232],
...

_mul_table

Multiplication table.

Maps (x,y) to xy. See _generate_tables.

Value:
{(0, 0): [0],
 (0, 1): [0],
 (0, 2): [0],
 (0, 3): [0],
 (0, 4): [0],
 (0, 5): [0],
 (0, 6): [0],
 (0, 7): [0],
...

_field_cache

Cached fields.

Calls to GF with identical modulus must return the same class (field), so we cache them here. The cache is seeded with the GF256 class which is always defined.

Value:
{256: <class 'viff.field.GF256'>}