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.
Where it lands in Jayverse
- Bridge/Wallet: if key management ever needs threshold signing, implement the Shamir split over GF(p) and verify it in code. Don't trust a library black box for the share-reconstruction math — run the extended-Euclidean inverse and interpolation yourself once, the way the exercise asks.
- Number: any ZK or polynomial-commitment feature rests on this exact interpolation math. A KZG-style proof for a reading or index should be read as linear algebra over GF(p) before trusting the proof library's claims.
- OFA: if a private solver-auction scheme uses secret sharing or erasure coding for bids, the same finite-field grammar applies. Rank and solution sets are exact here, so a bug shows up as wrong output, not noise.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| residue class | 잉여류 · 소수로 나눈 나머지에 따라 묶은 수의 집합. "formed by the residue classes modulo a prime" |
| black box | 내부 원리를 모른 채 결과만 쓰는 대상 · 라이브러리를 이해 없이 쓴다는 비판. "you end up treating the libraries as a black box" |
| partial pivoting | 부분 피벗팅 · 수치 안정성을 위해 계산 순서의 행을 바꾸는 기법. "partial pivoting for numerical stability is unnecessary" |
| characteristic | 체의 표수 · 그 체에서 0이 되는 최소 반복 횟수. "the fact that the characteristic is p produces phenomena" |
| basic grammar | 기본 문법 · 어떤 분야를 이해하는 데 필요한 기초 체계를 비유. "this is the basic grammar for reading blob data availability" |
| stand on | ~에 기반하다, ~위에 서 있다 · 여러 개념이 같은 토대 위에 있다는 뜻. "all stand on polynomial interpolation and linear algebra" |
| GF(p) | p를 소수로 하는 유한체(Galois Field) · 모듈러 나머지류로 이루어진 유한체, 이 카드 전체의 배경 구조. "GF(p) is the finite field formed by the residue classes modulo a prime p" |
| KZG | KZG 다항식 커밋먼트(Kate-Zaverucha-Goldberg) · 다항식 보간을 이용하는 커밋먼트 방식의 예. "polynomial commitments including KZG all stand on polynomial interpolation" |
| Shamir secret sharing | 샤미르 비밀 분산(Shamir secret sharing) · 다항식 보간으로 비밀을 여러 조각으로 나누는 기법, 유한체 선형대수의 응용 예. "Shamir secret sharing, Reed-Solomon codes, and polynomial commitments" |
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/.