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.
Common base class for elements.
Models an element of the GF(2^8) field.
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)
[0]
>>> GF256(0x01) + GF256(0x02)
[3]
Adding integers works too, the other operand is coerced into a GF256 element automatically:
>>> GF256(0x01) + 1
[0]
Division.
Equality testing.
Testing for equality with integers works as expected:
>>> GF256(10) == 10
True
Extract integer value from the field element.
>>> int(GF256(10))
10
Invertion.
Raises ZeroDivisionError if trying to inverse the zero element.
Multiply this and another GF256.
>>> GF256(0) * GF256(47)
[0]
>>> GF256(2) * GF256(3)
[6]
>>> GF256(16) * GF256(32)
[54]
Negation.
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
Exponentiation.
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
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