Finite Fields in Cryptography

A cryptographic calculation must give the same answer on every machine. Finite fields let us add, multiply and divide exactly while keeping every result inside a fixed set.

A finite field, also called a Galois field, is a finite set with addition and multiplication satisfying the field axioms. Subtraction and division by nonzero elements stay within the same set. A prime field with $p$ elements is written $\mathbb F_p$ or $GF(p)$ .

Keep the remainder

For a prime $p$ , the field $\mathbb{F}_p$ contains the integers $0$ through $p-1$ . Arithmetic wraps around modulo $p$ . Two integers are congruent when they have the same remainder:

5+4 \equiv 2 \pmod 7, \qquad 2-5 \equiv 4 \pmod 7.

The answer stays in the set. A negative intermediate value is reduced too: $-3$ and $4$ differ by a multiple of $7$ .

Read the operation tables

Switch between addition and multiplication, then change the prime. Every result stays within the field: this is closure. Symmetry across the diagonal shows commutativity. Rows and columns are numbered from zero; an entry gives the result of combining its row and column.

\mathbb F_p

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
2	4	6	8	10	12	14	16	1	3	5	7	9	11	13	15
3	6	9	12	15	1	4	7	10	13	16	2	5	8	11	14
4	8	12	16	3	7	11	15	2	6	10	14	1	5	9	13
5	10	15	3	8	13	1	6	11	16	4	9	14	2	7	12
6	12	1	7	13	2	8	14	3	9	15	4	10	16	5	11
7	14	4	11	1	8	15	5	12	2	9	16	6	13	3	10
8	16	7	15	6	14	5	13	4	12	3	11	2	10	1	9
9	1	10	2	11	3	12	4	13	5	14	6	15	7	16	8
10	3	13	6	16	9	2	12	5	15	8	1	11	4	14	7
11	5	16	10	4	15	9	3	14	8	2	13	7	1	12	6
12	7	2	14	9	4	16	11	6	1	13	8	3	15	10	5
13	9	5	1	14	10	6	2	15	11	7	3	16	12	8	4
14	11	8	5	2	16	13	10	7	4	1	15	12	9	6	3
15	13	11	9	7	5	3	1	16	14	12	10	8	6	4	2
16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1

Undo multiplication

Division means multiplying by an inverse. The inverse of a nonzero element $a$ is the element $a^{-1}$ satisfying $a\,a^{-1}\equiv1\pmod p$ .

Select a row in the multiplication table. Its entry equal to $1$ identifies the inverse; row zero has none.

Modulus3⁻¹ = 5

1	2	3	4	5	6
0	0	0	0	0	0
1	2	3	4	5	6
2	4	6	1	3	5
3	6	2	5	1	4
4	1	5	2	6	3
5	3	1	6	4	2
6	5	4	3	2	1

Modulo $7$ , $3\times5=15\equiv1$ , so $3^{-1}=5$ . Dividing $4$ by $3$ gives:

4\div3 \equiv 4\times5 \equiv 6 \pmod7.

Check by multiplying back: $3\times6\equiv4$ . This is exact division in the field, not a rounded version of $4/3$ over the real numbers.

Why prime matters

Change the table's modulus to $6$ and select row $2$ . No entry equals $1$ : multiplying by $2$ only reaches $0$ , $2$ and $4$ . In particular,

2\times3\equiv0\pmod6.

Two nonzero elements have multiplied to zero. Such elements are called zero divisors. Integer arithmetic modulo a composite number is not a field. Modulo a prime, every nonzero element has an inverse; division by zero remains undefined.

Finite fields can also contain $p^m$ elements for prime $p$ and integer $m>1$ . Those extension fields use a different construction, not ordinary integer arithmetic modulo $p^m$ .

Multiplication forms a group

The $p-1$ nonzero elements form a cyclic group under multiplication. A generator reaches all of them through repeated multiplication. Modulo $7$ , the powers of $3$ visit

$3,\ 2,\ 6,\ 4,\ 5,\ 1.$

Not every element is a generator: powers of $2$ only visit $2,4,1$ . The full multiplicative group has order $p-1$ ; an individual element can have a smaller order.

From numbers to points

A coordinate pair $(x,y)$ takes two elements of the field. The grid below contains all $p^2$ possible pairs. An elliptic curve ⁠ keeps only the pairs satisfying its equation, then adds a point at infinity.

(x,y)\in\mathbb{F}_p\times\mathbb{F}_p

Field size and security

secp256k1 uses the prime

$p=2^{256}-2^{32}-977.$

The prime’s form makes modular reduction efficient: $2^{256}\equiv2^{32}+977\pmod p$ , so high bits can be folded back into smaller terms. This field underpins the curve arithmetic used for Bitcoin’s public keys and signatures.

Its coordinates fit in 256 bits. That does not mean 256-bit security: the curve targets roughly 128-bit classical security. Field size, curve choice and subgroup order all matter; a larger coordinate representation is not itself a security proof. See SEC 2, §2.4.1 for the parameters and NIST SP 800-57, Table 2 for the security-strength comparison.

Other applications

AES uses $\mathbb F_{2^8}$ for byte arithmetic, while Curve25519 uses the prime field $\mathbb F_{2^{255}-19}$ . The AES field is an extension field: its multiplication is not integer multiplication modulo $256$ . See FIPS 197, §4 and RFC 7748, §4.1.

Finite fields also support error-correcting codes. Reed–Solomon codes evaluate polynomials over a finite field, allowing missing symbols to be recovered from enough remaining evaluations. Here the same exact arithmetic serves reliable transmission and storage.

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
2	4	6	8	10	12	14	16	1	3	5	7	9	11	13	15
3	6	9	12	15	1	4	7	10	13	16	2	5	8	11	14
4	8	12	16	3	7	11	15	2	6	10	14	1	5	9	13
5	10	15	3	8	13	1	6	11	16	4	9	14	2	7	12
6	12	1	7	13	2	8	14	3	9	15	4	10	16	5	11
7	14	4	11	1	8	15	5	12	2	9	16	6	13	3	10
8	16	7	15	6	14	5	13	4	12	3	11	2	10	1	9
9	1	10	2	11	3	12	4	13	5	14	6	15	7	16	8
10	3	13	6	16	9	2	12	5	15	8	1	11	4	14	7
11	5	16	10	4	15	9	3	14	8	2	13	7	1	12	6
12	7	2	14	9	4	16	11	6	1	13	8	3	15	10	5
13	9	5	1	14	10	6	2	15	11	7	3	16	12	8	4
14	11	8	5	2	16	13	10	7	4	1	15	12	9	6	3
15	13	11	9	7	5	3	1	16	14	12	10	8	6	4	2
16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
2	4	6	8	10	12	14	16	1	3	5	7	9	11	13	15
3	6	9	12	15	1	4	7	10	13	16	2	5	8	11	14
4	8	12	16	3	7	11	15	2	6	10	14	1	5	9	13
5	10	15	3	8	13	1	6	11	16	4	9	14	2	7	12
6	12	1	7	13	2	8	14	3	9	15	4	10	16	5	11
7	14	4	11	1	8	15	5	12	2	9	16	6	13	3	10
8	16	7	15	6	14	5	13	4	12	3	11	2	10	1	9
9	1	10	2	11	3	12	4	13	5	14	6	15	7	16	8
10	3	13	6	16	9	2	12	5	15	8	1	11	4	14	7
11	5	16	10	4	15	9	3	14	8	2	13	7	1	12	6
12	7	2	14	9	4	16	11	6	1	13	8	3	15	10	5
13	9	5	1	14	10	6	2	15	11	7	3	16	12	8	4
14	11	8	5	2	16	13	10	7	4	1	15	12	9	6	3
15	13	11	9	7	5	3	1	16	14	12	10	8	6	4	2
16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
2	4	6	8	10	12	14	16	1	3	5	7	9	11	13	15
3	6	9	12	15	1	4	7	10	13	16	2	5	8	11	14
4	8	12	16	3	7	11	15	2	6	10	14	1	5	9	13
5	10	15	3	8	13	1	6	11	16	4	9	14	2	7	12
6	12	1	7	13	2	8	14	3	9	15	4	10	16	5	11
7	14	4	11	1	8	15	5	12	2	9	16	6	13	3	10
8	16	7	15	6	14	5	13	4	12	3	11	2	10	1	9
9	1	10	2	11	3	12	4	13	5	14	6	15	7	16	8
10	3	13	6	16	9	2	12	5	15	8	1	11	4	14	7
11	5	16	10	4	15	9	3	14	8	2	13	7	1	12	6
12	7	2	14	9	4	16	11	6	1	13	8	3	15	10	5
13	9	5	1	14	10	6	2	15	11	7	3	16	12	8	4
14	11	8	5	2	16	13	10	7	4	1	15	12	9	6	3
15	13	11	9	7	5	3	1	16	14	12	10	8	6	4	2
16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1