Adding an imaginary unit to a finite field

Let p be a prime number. Then the integers mod p form a finite field.

The number of elements in a finite field must be a power of a prime, i.e. the order q = pⁿ for some n. When n > 1, we can take the elements of our field to be polynomials of degree n - 1 with coefficients in the integers mod p.

Addition works just as you'd expect addition to work, adding coefficients mod p, but multiplication is a little more complicated. You multiply field elements by multiplying their polynomial representatives, but then you divide by an irreducible polynomial and take the remainder.

Whenn = 2, for somep you can define the field by adding an imaginary unit.

When you can and cannot adjoin ani

For some finite fields of orderp, you can construct a field of orderp^2 by joining an element i to the field, very much the way you form the complex numbers from the real numbers. For example, you can create a field with 49 elements by taking pairs of (a, b) of integers mod 7 and multiplying them as if they werea +bi. So

(a,b) * (c,d) = (ac -bd,ad +bc).

This is equivalent to choosing the polynomialx^2 + 1 as your irreducible polynomial and following every polynomial multiplication by taking the remainder modulo x^2 + 1.

This works for a field with 49 elements, but not for a field of 25 elements. That's because over the integers mod 5 the polynomial x^2 + 1 already has a root. Two of them in fact:x = 2 orx = 3. So you could say that mod 5,i = 2. Ori = 3 if you prefer. You can still form a field of 25 elements by taking pairs of elements from a field of 5 elements, but you have to choose a different polynomial as your irreducible polynomial because x^2 + 1 isnot irreducible because

x^2 + 1 = (x - 2)(x + 2)

when working over the integers mod 5. You could use

x^2 +x + 1

as your irreducible polynomial. To prove that this polynomial is irreducible mod 5, plug in the numbers 0, 1, 2, 3, and 4 and confirm that none of them make the polynomial equal 0.

In general, you can create a field of orderp^2 by adjoining an elementi if and only ifp = 3 mod 4.

Next we'll look at an example of making a very large finite field even larger by adding an imaginary element.

Example from Ethereum

The Ethereum virtual machine has support for a pairing-more on that in a future post-of two elliptic curves, BN254 and alt_bn128. The BN254 curve is defined by

y^2 = x^3 + 3

over the field F_p, the integers mod p, where

p = 21888242871839275222246405745257275088696311157297823662689037894645226208583.

The curve alt_bn128 is defined by

y^2 = x^3 + 3/(9 + i)

over the field F_p[i], i.e. the field F_p, with an element i adjoined. Note the that last two digits ofp are 83, and sop is congruent to 3 mod 4.

Special point on curve

The Ethereum documentation (EIP-197) singles out a particular point (x,y) on alt_bn128:

x =a +bi
y =c +di

where

a = 10857046999023057135944570762232829481370756359578518086990519993285655852781
b = 11559732032986387107991004021392285783925812861821192530917403151452391805634
c = 8495653923123431417604973247489272438418190587263600148770280649306958101930
d = 4082367875863433681332203403145435568316851327593401208105741076214120093531.

We will show that this point is on the curve as an exercise in working in the field F_p[i]. We'll write Python code from scratch, not using any libraries, so all the details will be explicit.

def add(pair0, pair1, p): a, b = pair0 c, d = pair1 return ((a + c) % p, (b + d) % p)def mult(pair0, pair1, p): a, b = pair0 c, d = pair1 return ((a*c - b*d) % p, (b*c + a*d) % p)p = 21888242871839275222246405745257275088696311157297823662689037894645226208583a = 10857046999023057135944570762232829481370756359578518086990519993285655852781b = 11559732032986387107991004021392285783925812861821192530917403151452391805634c = 8495653923123431417604973247489272438418190587263600148770280649306958101930d = 4082367875863433681332203403145435568316851327593401208105741076214120093531# Find (e, f) such that (e, f)*(9, 1) = (1, 0).# 9e - f = 1# e + 9f = 0# Multiply first equation by 9 and add.e = (9*pow(82, -1, p)) % pf = (-e*pow(9, -1, p)) % pprod = mult((e, f), (9, 1), p)assert(prod[0] == 1 and prod[1] == 0)y2 = mult((c, d), (c, d), p)x3 = mult((a, b), mult((a, b), (a, b), p), p)rhs = add(x3, mult((3, 0), (e, f), p), p)assert(y2[0] == rhs[0])assert(y2[1] == rhs[1])

Related posts

• Finite fields
• Elliptic curve in Ethereum's consensus layer
• Misleading plots of elliptic curves

The post Adding an imaginary unit to a finite field first appeared on John D. Cook.