Capstok — learn by doing

Why this matters

A group is the minimum algebraic structure that lets you 'multiply' and 'invert' in a controlled way, and almost every classical zero-knowledge protocol is built inside one. The reason ZK proofs need groups specifically — rather than rings or fields — is that we want a one-way operation: easy to compute, infeasible to undo. The discrete logarithm problem (DLP) gives us exactly that flavour of asymmetry inside a cyclic group: given $g$ and $h = g^x$ , recovering $x$ is believed to be hard, but every prover/verifier check ('is this point really $g^x$ ?') becomes a single group exponentiation. If you can't write down the group axioms and identify a generator from memory, every paper you read for the rest of this course will feel like fog. This is the rebar.

Demo

A group $(G, \cdot)$ is a set with a binary operation that is closed, associative, has an identity, and admits inverses. A cyclic group is one where some element $g$ generates all of $G$ by repeated application of the operation. The DLP asks: given $g$ and $h \in \langle g \rangle$ , find the unique with .

\text{Group axioms: } \forall a,b,c \in G:\ (a \cdot b) \cdot c = a \cdot (b \cdot c),\ \exists e: e \cdot a = a,\ \exists a^{-1}: a \cdot a^{-1} = e. \quad \text{DLP: given } g, h = g^x,\ \text{find } x.

Try it yourself

Run the snippet and verify that $\{1,2,3,4,5,6\}$ under multiplication mod 7 forms a group: list the powers of 3 — you should see $3,2,6,4,5,1$ covering every element, confirming 3 is a generator and the group is cyclic of order 6.
Check the four group axioms by hand for $(Z / 7 Z)^{*}$ : closure (no product gives 0), associativity (inherited from integers), identity (the element 1), and an inverse for every element (find mod 7).

References

x \in \{0, \ldots, |G|-1\}

(\mathbb{Z}/7\mathbb{Z})^*

// main.go — run: go run main.go
package main

import (
	"fmt"
	"math/big"
)

// powMod returns base^exp mod m using big.Int for clarity.
func powMod(base, exp, m int) int {
	b := big.NewInt(int64(base))
	e := big.NewInt(int64(exp))
	mod := big.NewInt(int64(m))
	return int(new(big.Int).Exp(b, e, mod).Int64())
}

func main() {
	// (Z/7Z)* under multiplication mod 7 is a cyclic group of order 6.
	p := 7
	G := make([]int, 0, p-1)
	for i := 1; i < p; i++ {
		G = append(G, i)
	}
	fmt.Println("|G| =", len(G))

	// Find a generator: an element whose powers cover all of G.
	gSet := make(map[int]bool, len(G))
	for _, v := range G {
		gSet[v] = true
	}
	for _, g := range G {
		powers := make(map[int]bool, p-1)
		for k := 1; k < p; k++ {
			powers[powMod(g, k, p)] = true
		}
		match := true
		for v := range gSet {
			if !powers[v] {
				match = false
				break
			}
		}
		if match {
			powerList := make([]int, 0, p-1)
			for k := 1; k < p; k++ {
				powerList = append(powerList, powMod(g, k, p))
			}
			fmt.Printf("%d is a generator; powers = %v\n", g, powerList)
		}
	}

	// Toy DLP: find x s.t. 3^x = 5 mod 7
	base, h := 3, 5
	for x := 1; x < p; x++ {
		if powMod(base, x, p) == h {
			fmt.Printf("discrete log of %d base %d mod %d is %d\n", h, base, p, x)
			break
		}
	}
}

Run: go run main.go

Easy One Way, Impossible the Other (Discrete Log)

Why this matters

Demo

Try it yourself

References