Group Theory Basics (Cyclic Groups, Discrete Log) TODO
Concept
A group is a set with a binary operation satisfying associativity, an identity element, and inverses; if the powers of a single element g generate the whole group, it's called cyclic, and g is called a generator. In a finite group, the order of an element is the size of the cyclic subgroup it generates, and by Lagrange's theorem, the size of any subgroup always divides the size of the whole group. The discrete logarithm problem asks: given g and h = g^x in a cyclic group, find the exponent x. Computing the exponent (exponentiation) is fast via repeated squaring, while going the other direction is believed to be hard in a well-chosen group — this asymmetry is the foundation of public-key cryptography. However, hardness depends entirely on the choice of group: if the order of a multiplicative group factors into only small primes, Pohlig-Hellman breaks the problem into smaller pieces, so the group's order needs to be a large prime. Elliptic curve groups are widely used in practice because they offer shorter element representations at the same security level.
When handling signatures or commitments, scalars need to be reduced modulo the group's order — without understanding this structure, it's easy to end up accepting out-of-range scalars or small-subgroup points without checking them, which creates a real vulnerability.
Code & Formula
# 군론 기초(순환군·이산로그) — Z_p^*의 생성원 찾기, 위수(Lagrange), 이산로그 브루트포스
# 교육용 예시: 실제 암호에는 훨씬 큰 소수를 쓴다.
p = 23 # 소수 => Z_p^* = {1,...,p-1}는 위수 p-1 = 22인 순환군
def order_of(g, p):
"""g의 위수: g^k = 1이 되는 최소 양의 k."""
k, x = 1, g % p
while x != 1:
x = (x * g) % p
k += 1
return k
group_order = p - 1
print(f"|Z_{p}^*| = {group_order}")
# 모든 원소의 위수를 나열하고 Lagrange 정리(위수는 항상 군의 크기를 나눔) 확인
orders = {g: order_of(g, p) for g in range(1, p)}
for g, o in orders.items():
assert group_order % o == 0, "Lagrange 정리 위반!"
print("각 원소의 위수(Lagrange 정리: 모두 22를 나눔):")
print({g: o for g, o in list(orders.items())[:6]}, "...")
# 위수가 group_order와 같은 원소 = 생성원(primitive root)
generators = [g for g, o in orders.items() if o == group_order]
print(f"\n생성원들: {generators}")
g = generators[0]
x_secret = 15 # 비밀 지수
h = pow(g, x_secret, p)
print(f"\ng={g}, h=g^x mod p={h} (x는 비밀)")
# 이산로그 브루트포스: h = g^x가 되는 x를 처음부터 찾아본다 (작은 군이라 가능)
for x in range(group_order):
if pow(g, x, p) == h:
print(f"브루트포스로 복원한 이산로그 x={x} (정답과 일치: {x == x_secret})")
break
print("-> 군이 커지면(p가 수백 비트) 이 브루트포스는 우주 나이보다 오래 걸린다 — 이 비대칭성이 공개키 암호의 토대.")
Exercise
For a small prime p, find a generator of the multiplicative group, list the order of every element, and confirm Lagrange's theorem; then brute-force the discrete log in the same group to get a feel for how the difficulty scales with size.
Practical Connection
The secp256k1 curve used by Ethereum signatures is a cyclic group of prime order, and failing to reduce the signature scalar modulo that order leads to real incidents such as signature malleability or key leakage through nonce issues.
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/.