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

```
__div__(other)

Division.

__eq__(other)

Equality testing.

Testing for equality with integers works as expected:

```>>> GF256(10) == 10
True
```
__int__()

Extract integer value from the field element.

```>>> int(GF256(10))
10
```
__invert__()

Invertion.

Raises ZeroDivisionError if trying to inverse the zero element.

__mul__(other)

Multiply this and another GF256.

```>>> GF256(0) * GF256(47)

>>> GF256(2) * GF256(3)

>>> GF256(16) * GF256(32)

```
__neg__()

Negation.

__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
```
__pow__(exponent)

Exponentiation.

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)

```

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

#### Previous topic

Utility Functions Module

Shamir Module