Supported Fields

Here are the kinds of fields supported in Keelung:

• Any binary extension field!

• Any prime field larger than or equal to $GF(17)$ (fields with 17 elements)

Choice of fields

Commands like compile would ask you to specify which kind of field to use, when compiling the program into the constraint system over that field:

compile gf181 echo [] [2]

The example above uses gf181 , which is actually a prime field defined as:

gf181 :: FieldType
gf181 = Prime 1552511030102430251236801561344621993261920897571225601

The FieldType datatype

You can choose another kind of finite field by giving a different FieldType. Here’s how FieldType is declared under the hood:

data FieldType = Prime Integer
               | Binary Integer

Both Prime and Binary takes an Integer as the parameter, but we’ll see that they have different meanings.

Prime fields

Different prime fields have different prime characteristics. The Integer in Prime stands for that prime characteristics.

Bad things would happen if you attempt to provide composite (non-prime) numbers as parameters for Prime.

Binary fields

Binary extension fields, on the other hand, are characterized by irreducible polynomials.

These irreducible polynomials can be expressed as numbers, and that’s what the Integer in Binary is for.

Take Rijndael's (AES) finite field GF(2)[x]/(x⁸ + x⁴ + x³ + x + 1) as example, if we represent each term of the polynomial as a bit in a binary number, the irreducible polynomial x⁸ + x⁴ + x³ + x + 1 can be encoded in the binary form as 0b100011011 (or 283 in decimal). Put this number in Binary and you’ll get a FieldType:

rijndael :: FieldType
rijndael = Binary 0b100011011

Examples

You can use any Prime or Binary field you like. Here are some other popular choices:

-- | Binary field of 64 bits
b64 :: FieldType
b64 = Binary 18446744073709551643

-- | For Barreto-Naehrig curve of 128 bits
bn128 :: FieldType
bn128 = Prime 21888242871839275222246405745257275088548364400416034343698204186575808495617