Linear Algebra over the Finite Field GF(p) (December bridge, Thread A) TODO
Concept
GF(p) is the finite field formed by the residue classes modulo a prime p, in which every nonzero element has a multiplicative inverse. Linear algebra over this field defines concepts like vector spaces, rank, determinant, and inverse matrices exactly as over the reals, and Gaussian elimination works the same way — except division is replaced by modular multiplicative inverses. A decisive difference from real-number computation is that there's no notion of magnitude comparison or rounding error, so partial pivoting for numerical stability is unnecessary — any nonzero element can serve as a pivot. Also, because every operation is exact, rank and solution sets are determined with zero error, and the fact that the characteristic is p produces phenomena that don't exist over the reals, such as adding something to itself p times giving zero. Interpolation — uniquely recovering a polynomial from its values at distinct points — also holds exactly over this field.
Secret sharing, erasure codes, and most ZK proof systems are all described in terms of polynomials and linear algebra over finite fields, so without this computational intuition you end up treating the libraries as a black box.
Code & Formula
# 유한체 GF(p) 위 선형대수 — 페르마 소정리로 모듈러 역원을 구하고,
# 가우스 소거법을 mod p 로 그대로 적용해 Ax=b (mod p) 를 정확히 푼다.
P = 17 # 작은 소수를 법으로 사용
def mod_inv(a: int, p: int = P) -> int:
return pow(a % p, p - 2, p) # 페르마 소정리: a^(p-1) ≡ 1 => a^(p-2) ≡ a^-1
def gauss_solve_mod_p(A: list, b: list, p: int = P) -> list:
n = len(A)
M = [row[:] + [b[i]] for i, row in enumerate(A)] # 첨가행렬
for col in range(n):
pivot_row = next(r for r in range(col, n) if M[r][col] % p != 0) # 실수와 달리 크기 비교 불필요
M[col], M[pivot_row] = M[pivot_row], M[col]
inv = mod_inv(M[col][col], p)
M[col] = [(x * inv) % p for x in M[col]] # 피벗을 1로
for r in range(n):
if r != col and M[r][col] != 0:
factor = M[r][col]
M[r] = [(M[r][k] - factor * M[col][k]) % p for k in range(n + 1)]
return [row[-1] for row in M]
A = [[2, 3], [5, 1]]
b = [7, 4]
x = gauss_solve_mod_p(A, b)
print(f"GF({P}) 위에서 Ax ≡ b (mod {P}) 풀이: x = {x}")
# 검산: Ax mod p == b
check = [sum(A[i][j] * x[j] for j in range(2)) % P for i in range(2)]
print(f"검산 Ax mod {P} = {check}, b = {b} → {'일치' if check == b else '불일치'}")
print(f"\n예: 5의 모듈러 역원 mod {P} = {mod_inv(5)} (검산: 5*inv mod {P} = {5 * mod_inv(5) % P})")
Exercise
Pick a small prime p, implement Gaussian elimination and matrix inversion over GF(p) yourself, and use inverses computed via the extended Euclidean algorithm to check how rank and solution sets differ from the real-number version.
Practical Connection
Shamir secret sharing, Reed-Solomon codes, and polynomial commitments including KZG all stand on polynomial interpolation and linear algebra over finite fields — this is the basic grammar for reading blob data availability and ZK circuits.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.