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).

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

In one paragraph, explain what a group is to someone who knows arithmetic but not abstract algebra. Use $(\mathbb{Z}/7\mathbb{Z})^*$ as the running example, and explain why we say it is *cyclic*.

2. Why it works (the mechanism)

Walk me step by step through how the discrete log problem creates a one-way function. Where exactly does the asymmetry between computing $g^x$ and recovering $x$ come from, and why don't standard tricks (binary search, gradient descent) apply?

3. Advanced — application & what's next

Given the group of points on the elliptic curve secp256k1 (used in Bitcoin), why is the DLP there harder per-bit than DLP in $(\mathbb{Z}/p\mathbb{Z})^*$? Sketch what extra structure $(\mathbb{Z}/p\mathbb{Z})^*$ has that allows index-calculus attacks, and why elliptic curves dodge it.

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

Groups, generators, and the discrete logarithm problem