Number Theory and Modular Arithmetic TODO
Concept
Modular arithmetic identifies integers by their remainder modulo n; addition, subtraction, and multiplication are all compatible with the remainder operation, but division is only defined when an inverse exists. a has a multiplicative inverse mod n if and only if gcd(a, n) = 1, and that inverse can be obtained via the extended Euclidean algorithm by solving ax + ny = 1. When n is a prime p, every nonzero element has an inverse, making it a finite field; by Fermat's little theorem, a^(p-1) ≡ 1 (mod p), so the inverse can also be computed as a^(p-2). Euler's theorem generalizes this: whenever gcd(a, n) = 1, a^φ(n) ≡ 1 (mod n), which is the basis for how exponents are handled in RSA-type systems. The Chinese Remainder Theorem states that a system of congruences over pairwise coprime moduli has a unique solution modulo their product, and it's used to split large-number arithmetic into computations over smaller moduli.
Elliptic curve operations, hash-to-field, and ZK circuit arithmetic all run over finite fields, so without understanding modular inverses and overflow handling you can't judge either the correctness or the performance of cryptographic code.
Code & Formula
# 정수론·모듈러 산술 — 확장 유클리드로 모듈러 역원 구하기 + 페르마 소정리로 교차검증
# ax + ny = gcd(a, n) 을 풀어 gcd=1이면 x가 곧 a의 (mod n) 역원이다.
def ext_gcd(a, n):
"""확장 유클리드: (g, x, y) with a*x + n*y = g = gcd(a, n)."""
old_r, r = a, n
old_x, x = 1, 0
old_y, y = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q * r
old_x, x = x, old_x - q * x
old_y, y = y, old_y - q * y
return old_r, old_x, old_y
def mod_inverse(a, n):
g, x, _ = ext_gcd(a, n)
if g != 1:
raise ValueError(f"{a}는 mod {n}에서 역원이 없음 (gcd={g})")
return x % n
p = 1_000_000_007 # 큰 소수
for a in (3, 12345, 999_999_999):
inv = mod_inverse(a, p)
check = (a * inv) % p
fermat_inv = pow(a, p - 2, p) # 페르마 소정리: a^(p-2) ≡ a^-1 (mod p)
print(f"a={a:>10} ext_gcd 역원={inv:>10} a*inv mod p={check} "
f"페르마 역원과 일치={inv == fermat_inv}")
# 소수가 아닌 법에서는 gcd(a,n)=1일 때만 역원이 존재함을 확인
n = 20
for a in range(1, n):
from math import gcd
if gcd(a, n) == 1:
print(f"mod {n}: a={a} 역원={mod_inverse(a, n)}")
Exercise
Implement the extended Euclidean algorithm yourself to find the inverse of a modulo an arbitrary prime p, then compute the same value as a^(p-2) mod p and confirm the two results match.
Practical Connection
The reason Solidity fixed-point math uses patterns like mulDiv — multiplying before dividing — and the fact that division over a finite field is really multiplication by an inverse, connect directly to both the precision design of LMSR price calculations and the code that verifies them.
Where it lands in Jayverse
- Wallet: guard modular inverse in any custom signature-recovery code. Session-key and mandate verification (EIP-7702/7715) runs over secp256k1's prime field; make sure custom code checks gcd(a,n)=1 rather than assuming a library always guards the non-invertible case.
- Verex: CRT-style splitting is the next lever if order-matching math needs big numbers. Beyond LMSR's mulDiv precision, note Chinese Remainder splitting as the tool if big-integer arithmetic ever becomes a gas bottleneck in matching or settlement.
- DeFi: verify gcd(a,n)=1 before reusing a prime-field exponent trick. If the liquid-staking study needs a custom modular exponent for rebasing or index math, confirm the chosen modulus actually satisfies the condition Euler's theorem requires, don't just borrow the RSA-shaped formula.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| compatible with | ~와 부합하다, 맞아떨어지다 · "are all compatible with the remainder operation" |
| generalize | 일반화하다 · "Euler's theorem generalizes this" |
| pairwise coprime | 쌍마다 서로소인(둘씩 짝지어도 공약수가 1) · "over pairwise coprime moduli" |
| split into | ~로 쪼개어 나누다 · "split large-number arithmetic into computations over smaller moduli" |
| overflow handling | 오버플로 처리 · "modular inverses and overflow handling" |
| multiplying before dividing | 나누기 전에 먼저 곱하는 방식 · "multiplying before dividing" |
| LMSR | 로그마켓점수규칙(Logarithmic Market Scoring Rule) · 예측시장에서 유동성 공급·가격 결정에 쓰이는 자동화 마켓메이커 공식. "the precision design of LMSR price calculations" |
| RSA | RSA(Rivest–Shamir–Adleman) · 소인수분해 난해성에 기반한 공개키 암호 체계, 모듈러 거듭제곱이 지수 처리의 근거. "the basis for how exponents are handled in RSA-type systems" |
| ZK | 영지식(Zero-Knowledge) · 특정 값을 노출하지 않고 계산의 정당성을 증명하는 방식, 유한체 위에서 회로 연산 수행. "ZK circuit arithmetic all run over finite fields" |
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/.