Adding imaginary unit to finite field

let P be a prime number. then integer mod P Create a finite area.

The number of elements in a finite field must be a power of a prime, i.e. the order Why , Pⁿ for some nWhen? n > 1, we can consider the elements of our field as polynomials of degree n – 1 with coefficients in integer mod P,

Addition works exactly as you would expect since addition works by adding coefficients mod PBut multiplication is a little more complicated. You multiply the field elements by multiplying their polynomial representatives, but then you divide by an invariant polynomial and take the remainder.

When? n = 2, for some P You can define area by adding an imaginary unit.

When you can and can’t add one I

For some limited range of sequences PYou can create a field of orders P² By adding an element I In the field, just like you create complex numbers from real numbers. For example, you can create a field with 49 elements (taking pairs ofA, b) of integer mod 7 and multiplying them as if they were A , biso

,A, b,C, D,AC B.D, Advertisement , BC,

This is equivalent to choosing the polynomial x² + 1 as your unsolvable polynomial and follow each polynomial multiplication by taking the remainder modulo x² + 1.

This works for a field with 49 elements, but not for a field with 25 elements. This is because the integer is a polynomial greater than mod 5. x² + 1 already has a root. Actually two of them: x = 2 or x = 3. So you can say that mod 5, I = 2. or I = 3. If you want, you can still create a field of 25 elements by taking pairs of elements from a field of 5 elements, but you must choose a different polynomial as your unsolvable polynomial because x²+1 is No irrelevant because

x² + 1 = (x − 2)(x +2)

You can use this when working on integer mod 5

x²+ x +1

As your unsolvable polynomial. To prove that this polynomial is invariant mod 5, add the numbers 0, 1, 2, 3, and 4 and verify that none of them makes the polynomial equal to 0.

In general, you can create a field of orders P² By joining some element I if and only if P = 3 mod 4.

Next we will see 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 pairing two elliptic curves – more on this in a future post, bn254 And alt_bn128BN254 curve is defined

this²= x³ + 3

over the field F_Pinteger mod PWhere?

P = 21888242871839275222246405745257275088696311157297823662689037894645226208583.

The curve is defined by alt_bn128

this²= x³ + 3/(9 + I,

over the field F_P[i]ie field F_Pwith one element I attached. Note the last two digits of P There are 83, etc. P is analogous to 3 mod 4.

special point on the curve

The Ethereum document (EIP-197) highlights a particular point (x, this) on alt_bn128:

x , A , bi
this , C , di

Where?

A = 10857046999023057135944570762232829481370756359578518086990519993285655852781
b = 11559732032986387107991004021392285783925812861821192530917403151452391805634
C = 8495653923123431417604973247489272438418190587263600148770280649306958101930
D = 4082367875863433681332203403145435568316851327593401208105741076214120093531.

We will show that this point is on the curve as practice in field work shows F_P[i]We will write Python code from scratch without using any libraries, so all details will be clear,

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 = 21888242871839275222246405745257275088696311157297823662689037894645226208583
a = 10857046999023057135944570762232829481370756359578518086990519993285655852781
b = 11559732032986387107991004021392285783925812861821192530917403151452391805634
c = 8495653923123431417604973247489272438418190587263600148770280649306958101930
d = 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)) % p
f = (-e*pow(9, -1, p)) % p
prod = 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