package crypto

// Track 1: Algebraic Foundations — exhaustive proofs over finite state spaces.
//
// Each test verifies a mathematical property by exhaustive enumeration.
// If a test passes, the claim is proven for the entire domain. These are
// not probabilistic checks — they are complete proofs over finite sets.

import (
	"sort"
	"testing"

	"git.mleku.dev/mleku/dendrite/pkg/axiom"
	"git.mleku.dev/mleku/dendrite/pkg/dissolve"
	"git.mleku.dev/mleku/dendrite/pkg/lattice"
	"git.mleku.dev/mleku/dendrite/pkg/permutation"
	"git.mleku.dev/mleku/dendrite/pkg/projection"
	"git.mleku.dev/mleku/dendrite/pkg/ratio"
	"git.mleku.dev/mleku/dendrite/pkg/state"
)

// ---- S_3 Group Axioms (exhaustive over all 6 elements) ----

func TestS3Closure(t *testing.T) {
	// For all a, b in S_3: a.Compose(b) is in S_3.
	all := permutation.All()
	for _, a := range all {
		for _, b := range all {
			c := a.Compose(b)
			if c >= permutation.Count {
				t.Errorf("Compose(%v, %v) = %d, out of range", a, b, c)
			}
		}
	}
}

func TestS3Identity(t *testing.T) {
	// For all a in S_3: Identity.Compose(a) == a == a.Compose(Identity).
	all := permutation.All()
	for _, a := range all {
		if permutation.Identity.Compose(a) != a {
			t.Errorf("Identity.Compose(%v) = %v, want %v",
				a, permutation.Identity.Compose(a), a)
		}
		if a.Compose(permutation.Identity) != a {
			t.Errorf("%v.Compose(Identity) = %v, want %v",
				a, a.Compose(permutation.Identity), a)
		}
	}
}

func TestS3Inverse(t *testing.T) {
	// For all a in S_3: a.Compose(a^-1) == Identity == a^-1.Compose(a).
	all := permutation.All()
	for _, a := range all {
		inv := a.Inverse()
		if a.Compose(inv) != permutation.Identity {
			t.Errorf("%v.Compose(%v.Inverse()) = %v, want Identity",
				a, a, a.Compose(inv))
		}
		if inv.Compose(a) != permutation.Identity {
			t.Errorf("%v.Inverse().Compose(%v) = %v, want Identity",
				a, a, inv.Compose(a))
		}
	}
}

func TestS3Associativity(t *testing.T) {
	// For all a, b, c in S_3: (a.b).c == a.(b.c).
	// 6^3 = 216 cases — exhaustive.
	all := permutation.All()
	for _, a := range all {
		for _, b := range all {
			for _, c := range all {
				ab_c := a.Compose(b).Compose(c)
				a_bc := a.Compose(b.Compose(c))
				if ab_c != a_bc {
					t.Errorf("(%v.%v).%v = %v, but %v.(%v.%v) = %v",
						a, b, c, ab_c, a, b, c, a_bc)
				}
			}
		}
	}
}

func TestS3OrderOfElements(t *testing.T) {
	// S_3 element orders:
	//   Identity: order 1
	//   Transpositions (Swap01, Swap02, Swap12): order 2
	//   3-cycles (Cycle012, Cycle021): order 3
	expected := map[permutation.Perm]int{
		permutation.Identity: 1,
		permutation.Swap01:   2,
		permutation.Swap02:   2,
		permutation.Swap12:   2,
		permutation.Cycle012: 3,
		permutation.Cycle021: 3,
	}

	for p, wantOrder := range expected {
		current := p
		for i := 1; i <= 6; i++ {
			if current == permutation.Identity {
				if i != wantOrder {
					t.Errorf("order of %v = %d, want %d", p, i, wantOrder)
				}
				break
			}
			current = current.Compose(p)
		}
	}
}

func TestS3NonAbelian(t *testing.T) {
	// S_3 is non-abelian: there exist a, b where a.b != b.a.
	// Verify at least one non-commutative pair exists.
	found := false
	all := permutation.All()
	for _, a := range all {
		for _, b := range all {
			if a.Compose(b) != b.Compose(a) {
				found = true
				break
			}
		}
		if found {
			break
		}
	}
	if !found {
		t.Error("S_3 should be non-abelian but all pairs commute")
	}
}

// ---- Trigram Permutation Action (exhaustive over 8 trigrams × 6 perms) ----

func TestPermActionBijective(t *testing.T) {
	// For each permutation p, the map t -> p.ApplyTrigram(t) is a bijection on {0..7}.
	all := permutation.All()
	for _, p := range all {
		seen := make(map[state.Trigram]bool)
		for tri := range uint8(8) {
			result := p.ApplyTrigram(state.Trigram(tri))
			if result > 7 {
				t.Errorf("%v.ApplyTrigram(%d) = %d, out of range", p, tri, result)
			}
			if seen[result] {
				t.Errorf("%v.ApplyTrigram is not injective: %d maps to %d (already seen)", p, tri, result)
			}
			seen[result] = true
		}
		if len(seen) != 8 {
			t.Errorf("%v.ApplyTrigram hit %d/8 values (not surjective)", p, len(seen))
		}
	}
}

func TestPermActionHomomorphism(t *testing.T) {
	// (a.b).ApplyTrigram(t) == a.ApplyTrigram(b.ApplyTrigram(t))
	// for all a, b in S_3 and all trigrams t.
	// 6 × 6 × 8 = 288 cases — exhaustive.
	all := permutation.All()
	for _, a := range all {
		for _, b := range all {
			ab := a.Compose(b)
			for tri := range uint8(8) {
				t_ := state.Trigram(tri)
				direct := ab.ApplyTrigram(t_)
				stepped := a.ApplyTrigram(b.ApplyTrigram(t_))
				if direct != stepped {
					t.Errorf("(%v.%v).Apply(%d)=%d, but %v.Apply(%v.Apply(%d))=%d",
						a, b, tri, direct, a, b, tri, stepped)
				}
			}
		}
	}
}

func TestPermIdentityFixesAllTrigrams(t *testing.T) {
	// Identity.ApplyTrigram(t) == t for all t.
	for tri := range uint8(8) {
		result := permutation.Identity.ApplyTrigram(state.Trigram(tri))
		if result != state.Trigram(tri) {
			t.Errorf("Identity.ApplyTrigram(%d) = %d, want %d", tri, result, tri)
		}
	}
}

// ---- Hexagram Permutation Action (exhaustive over 64 hexagrams × 6 perms) ----

func TestHexPermConsistent(t *testing.T) {
	// ApplyHexagram applies the permutation to both inner and outer trigrams.
	// For all p in S_3 and all hexagrams h:
	//   p.ApplyHexagram(h) == Hex(p.ApplyTrigram(h.Inner()), p.ApplyTrigram(h.Outer()))
	all := permutation.All()
	for _, p := range all {
		for h := range uint8(64) {
			hex := state.Hexagram(h)
			got := p.ApplyHexagram(hex)
			want := state.Hex(p.ApplyTrigram(hex.Inner()), p.ApplyTrigram(hex.Outer()))
			if got != want {
				t.Errorf("%v.ApplyHexagram(%d): got %d, want %d", p, h, got, want)
			}
		}
	}
}

// ---- Projection Key-to-Perm Mapping (exhaustive over 8 keys) ----

func TestProjectionKeyToPermSurjective(t *testing.T) {
	// All 6 S_3 elements are reachable from the 8 projection keys.
	// Keys 6,7 are collapse points that alias to existing perms.
	seen := make(map[permutation.Perm]bool)
	for k := range uint8(projection.KeyCount) {
		p := projection.Key(k).Permutation()
		seen[p] = true
	}
	if len(seen) != int(permutation.Count) {
		t.Errorf("key-to-perm covers %d/%d permutations", len(seen), permutation.Count)
	}
}

func TestProjectionCollapseAliases(t *testing.T) {
	// Collapse keys alias to specific permutations:
	// KeyCollapseA (110) → Identity
	// KeyCollapseB (111) → Swap12
	if projection.KeyCollapseA.Permutation() != permutation.Identity {
		t.Errorf("CollapseA.Perm = %v, want Identity", projection.KeyCollapseA.Permutation())
	}
	if projection.KeyCollapseB.Permutation() != permutation.Swap12 {
		t.Errorf("CollapseB.Perm = %v, want Swap12", projection.KeyCollapseB.Permutation())
	}
}

func TestProjectionKeyOrder(t *testing.T) {
	// Verify geometric orders: collapse=1, face/edge=2, vertex=3.
	orders := map[projection.Key]int{
		projection.KeyFaceXY:    2,
		projection.KeyFaceXZ:    2,
		projection.KeyFaceYZ:    2,
		projection.KeyEdgeBias:  2,
		projection.KeyVertexA:   3,
		projection.KeyVertexB:   3,
		projection.KeyCollapseA: 1,
		projection.KeyCollapseB: 1,
	}
	for k, want := range orders {
		if got := k.Order(); got != want {
			t.Errorf("Key(%d).Order() = %d, want %d", k, got, want)
		}
	}
}

func TestProjectionPackRoundTrip(t *testing.T) {
	// For all vertex × key pairs, Pack → Vertex/Key round-trips.
	// 8 × 8 = 64 cases — exhaustive.
	for v := range uint8(projection.VertexCount) {
		for k := range uint8(projection.KeyCount) {
			p := projection.Pack(projection.Vertex(v), projection.Key(k))
			if p.Vertex() != projection.Vertex(v) {
				t.Errorf("Pack(%d,%d).Vertex() = %d", v, k, p.Vertex())
			}
			if p.Key() != projection.Key(k) {
				t.Errorf("Pack(%d,%d).Key() = %d", v, k, p.Key())
			}
		}
	}
}

func TestProjection64Distinct(t *testing.T) {
	// All 64 Projection values are distinct.
	seen := make(map[projection.Projection]bool)
	for v := range uint8(projection.VertexCount) {
		for k := range uint8(projection.KeyCount) {
			p := projection.Pack(projection.Vertex(v), projection.Key(k))
			if seen[p] {
				t.Errorf("duplicate projection for vertex=%d, key=%d", v, k)
			}
			seen[p] = true
		}
	}
	if len(seen) != projection.ProjectionCount {
		t.Errorf("got %d distinct projections, want %d", len(seen), projection.ProjectionCount)
	}
}

// ---- ContextualLockIn Formula Verification (exhaustive over rationals) ----

func TestContextualLockInFormula(t *testing.T) {
	// Formula: 0.3 + 0.7 * (occupied / total_neighbors)
	// Verified for all combinations of occupied in {0..total} and total in {1..10}.
	for total := 1; total <= 10; total++ {
		for occupied := 0; occupied <= total; occupied++ {
			rate := ratio.New(int64(occupied), int64(total))
			expected := ratio.New(3, 10).Add(ratio.New(7, 10).Mul(rate))

			// Build a lattice node with `total` neighbors, `occupied` of them occupied.
			l := lattice.New()
			center := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})

			var neighbors []*lattice.Node
			for i := 0; i < total; i++ {
				nb := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
				l.Connect(center, nb)
				neighbors = append(neighbors, nb)
			}

			// Bond the center node.
			center.Bond(testElem{"test", "center"})

			// Bond `occupied` neighbors.
			for i := 0; i < occupied; i++ {
				neighbors[i].Bond(testElem{"test", "nb"})
			}

			got := center.ContextualLockIn()
			if !got.Equal(expected) {
				t.Errorf("ContextualLockIn(occupied=%d, total=%d) = %s, want %s",
					occupied, total, got, expected)
			}
		}
	}
}

func TestContextualLockInBounds(t *testing.T) {
	// ContextualLockIn is always in [0.3, 1.0] for bonded nodes with neighbors.
	lo := ratio.New(3, 10)
	hi := ratio.One

	for total := 1; total <= 10; total++ {
		for occupied := 0; occupied <= total; occupied++ {
			l := lattice.New()
			center := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
			for i := 0; i < total; i++ {
				nb := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
				l.Connect(center, nb)
				if i < occupied {
					nb.Bond(testElem{"test", "nb"})
				}
			}
			center.Bond(testElem{"test", "center"})

			got := center.ContextualLockIn()
			if got.Less(lo) {
				t.Errorf("ContextualLockIn(occ=%d, total=%d) = %s < 0.3", occupied, total, got)
			}
			if hi.Less(got) {
				t.Errorf("ContextualLockIn(occ=%d, total=%d) = %s > 1.0", occupied, total, got)
			}
		}
	}
}

func TestContextualLockInZeroForUnbonded(t *testing.T) {
	// An unbonded node returns zero regardless of neighbors.
	l := lattice.New()
	center := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
	nb := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
	l.Connect(center, nb)
	nb.Bond(testElem{"test", "nb"})

	got := center.ContextualLockIn()
	if !got.IsZero() {
		t.Errorf("ContextualLockIn of unbonded node = %s, want 0", got)
	}
}

func TestContextualLockInNoNeighbors(t *testing.T) {
	// A bonded node with no neighbors returns 0.3.
	l := lattice.New()
	n := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
	n.Bond(testElem{"test", "solo"})

	got := n.ContextualLockIn()
	if !got.Equal(ratio.New(3, 10)) {
		t.Errorf("ContextualLockIn of isolated node = %s, want 3/10", got)
	}
}

// ---- Dissolution Determinism ----

func TestDissolutionDeterministic(t *testing.T) {
	// Running ScanOnce on two identically constructed lattices with the
	// same config produces the same dissolution set.
	build := func() *lattice.Lattice {
		l := lattice.New()
		var nodes []*lattice.Node
		for range 10 {
			n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
			nodes = append(nodes, n)
		}
		for i := range nodes {
			l.Connect(nodes[i], nodes[(i+1)%len(nodes)])
		}
		// Bond only every other node → isolated bonds have low contextual lock-in.
		for i := 0; i < 10; i += 2 {
			nodes[i].Bond(testElem{"word", "x"})
		}
		return l
	}

	cfg := dissolve.Config{Threshold: ratio.New(6, 10)}

	// Run on first lattice.
	l1 := build()
	d1 := make(chan axiom.Element, 10)
	e1 := make(chan dissolve.Event, 10)
	dissolve.ScanOnce(l1, cfg, d1, e1)
	close(d1)
	close(e1)
	var ids1 []uint64
	for ev := range e1 {
		ids1 = append(ids1, uint64(ev.NodeID))
	}
	sort.Slice(ids1, func(i, j int) bool { return ids1[i] < ids1[j] })

	// Run on second lattice.
	l2 := build()
	d2 := make(chan axiom.Element, 10)
	e2 := make(chan dissolve.Event, 10)
	dissolve.ScanOnce(l2, cfg, d2, e2)
	close(d2)
	close(e2)
	var ids2 []uint64
	for ev := range e2 {
		ids2 = append(ids2, uint64(ev.NodeID))
	}
	sort.Slice(ids2, func(i, j int) bool { return ids2[i] < ids2[j] })

	// Same dissolution set.
	if len(ids1) != len(ids2) {
		t.Fatalf("dissolution count differs: %d vs %d", len(ids1), len(ids2))
	}
	for i := range ids1 {
		if ids1[i] != ids2[i] {
			t.Errorf("dissolution[%d]: %d vs %d", i, ids1[i], ids2[i])
		}
	}
}

func TestDissolutionThresholdMonotonic(t *testing.T) {
	// Higher threshold dissolves at least as many nodes as lower threshold.
	build := func() *lattice.Lattice {
		l := lattice.New()
		var nodes []*lattice.Node
		for range 20 {
			n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
			nodes = append(nodes, n)
		}
		for i := range nodes {
			l.Connect(nodes[i], nodes[(i+1)%len(nodes)])
		}
		// Bond all nodes.
		for _, n := range nodes {
			n.Bond(testElem{"word", "x"})
		}
		return l
	}

	thresholds := []ratio.Ratio{
		ratio.New(1, 10),
		ratio.New(3, 10),
		ratio.New(5, 10),
		ratio.New(7, 10),
		ratio.New(9, 10),
	}

	var prevCount int
	for i, threshold := range thresholds {
		l := build()
		d := make(chan axiom.Element, 20)
		e := make(chan dissolve.Event, 20)
		dissolve.ScanOnce(l, dissolve.Config{Threshold: threshold}, d, e)
		close(d)
		close(e)
		count := 0
		for range e {
			count++
		}
		for range d {
		}
		if i > 0 && count < prevCount {
			t.Errorf("threshold %s dissolved %d, but lower threshold dissolved %d",
				threshold, count, prevCount)
		}
		prevCount = count
	}
}

// ---- Bond Determinism ----

func TestBondDeterministic(t *testing.T) {
	// Bond(element) on the same node with the same constraint produces
	// the same result (success/failure) deterministically.
	for range 10 {
		l := lattice.New()
		n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
		e := testElem{"word", "test"}
		result := n.Bond(e)
		if !result {
			t.Error("matching element should bond")
		}
	}
}

func TestBondRejectsNonMatching(t *testing.T) {
	// An element that doesn't match the constraint is rejected.
	l := lattice.New()
	n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
	e := testElem{"punct", "!"}
	if n.Bond(e) {
		t.Error("mismatched element should not bond")
	}
}

func TestBondIdempotent(t *testing.T) {
	// Bonding a second element to an already-occupied node fails.
	l := lattice.New()
	n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
	n.Bond(testElem{"word", "a"})
	if n.Bond(testElem{"word", "b"}) {
		t.Error("bonding to occupied node should fail")
	}
}

// ---- Hamadryad Hash Determinism and Distinctness ----

func TestHamadryadDeterministic(t *testing.T) {
	// Same input → same hash.
	msgs := []string{"", "hello", "dendrite", "test message"}
	for _, msg := range msgs {
		h1 := Hash([]byte(msg))
		h2 := Hash([]byte(msg))
		if h1 != h2 {
			t.Errorf("Hash(%q) not deterministic", msg)
		}
	}
}

func TestHamadryadDistinct(t *testing.T) {
	// Different inputs → different hashes (collision resistance test over small domain).
	msgs := []string{"a", "b", "c", "d", "aa", "ab", "ba", "bb", "", "test"}
	hashes := make(map[Hamadryad]string)
	for _, msg := range msgs {
		h := Hash([]byte(msg))
		if prev, ok := hashes[h]; ok {
			t.Errorf("collision: Hash(%q) == Hash(%q)", msg, prev)
		}
		hashes[h] = msg
	}
}

// NTT correctness is proven exhaustively in ntt_test.go:
//   - TestNTTRoundTrip: forward + inverse recovers original polynomial
//   - TestNTTConvolution: pointwise multiply = polynomial product mod x^64+1
//   - TestNTTNegacyclicWraparound: x^64 ≡ -1 (mod x^64+1)
//   - TestBitRev6: bit-reversal permutation is an involution
//   - TestPowMod: modular exponentiation correctness
// Those tests are exhaustive over their input domains and are not duplicated here.

// ---- Hexagram State Space ----

func TestHexagramInnerOuterRoundTrip(t *testing.T) {
	// For all 64 hexagrams: Hex(h.Inner(), h.Outer()) == h.
	for h := range uint8(64) {
		hex := state.Hexagram(h)
		reconstructed := state.Hex(hex.Inner(), hex.Outer())
		if reconstructed != hex {
			t.Errorf("Hex((%d).Inner(), (%d).Outer()) = %d, want %d",
				h, h, reconstructed, h)
		}
	}
}

func TestHexagramInnerOuterPartition(t *testing.T) {
	// Inner uses low 3 bits, outer uses high 3 bits.
	// All 8 × 8 = 64 combinations should be representable.
	seen := make(map[state.Hexagram]bool)
	for inner := range uint8(8) {
		for outer := range uint8(8) {
			h := state.Hex(state.Trigram(inner), state.Trigram(outer))
			if h.Inner() != state.Trigram(inner) {
				t.Errorf("Hex(%d,%d).Inner() = %d", inner, outer, h.Inner())
			}
			if h.Outer() != state.Trigram(outer) {
				t.Errorf("Hex(%d,%d).Outer() = %d", inner, outer, h.Outer())
			}
			seen[h] = true
		}
	}
	if len(seen) != 64 {
		t.Errorf("got %d distinct hexagrams, want 64", len(seen))
	}
}

// ---- Trigram Bit Manipulation ----

func TestTrigramBitAccessors(t *testing.T) {
	// For all 8 trigrams, verify bit accessors match bit positions.
	for tri := range uint8(8) {
		tg := state.Trigram(tri)
		if tg.Bonding() != (tri&1 != 0) {
			t.Errorf("Trigram(%d).Bonding() = %v, want %v", tri, tg.Bonding(), tri&1 != 0)
		}
		if tg.Constraint() != (tri&2 != 0) {
			t.Errorf("Trigram(%d).Constraint() = %v, want %v", tri, tg.Constraint(), tri&2 != 0)
		}
		if tg.Energy() != (tri&4 != 0) {
			t.Errorf("Trigram(%d).Energy() = %v, want %v", tri, tg.Energy(), tri&4 != 0)
		}
	}
}

func TestTrigramFlipInvolution(t *testing.T) {
	// Flipping the same bit twice returns to original.
	for tri := range uint8(8) {
		for bit := range uint8(3) {
			tg := state.Trigram(tri)
			if tg.Flip(bit).Flip(bit) != tg {
				t.Errorf("Trigram(%d).Flip(%d).Flip(%d) != original", tri, bit, bit)
			}
		}
	}
}

// ---- Ratio Arithmetic Correctness ----

func TestRatioFieldAxioms(t *testing.T) {
	// Verify commutativity, associativity, distributivity over a small domain.
	vals := []ratio.Ratio{
		ratio.Zero, ratio.One, ratio.Half,
		ratio.New(1, 3), ratio.New(2, 3), ratio.New(3, 7),
		ratio.New(-1, 2), ratio.New(5, 1),
	}

	for _, a := range vals {
		for _, b := range vals {
			// Commutativity of addition.
			if !a.Add(b).Equal(b.Add(a)) {
				t.Errorf("%s + %s != %s + %s", a, b, b, a)
			}
			// Commutativity of multiplication.
			if !a.Mul(b).Equal(b.Mul(a)) {
				t.Errorf("%s * %s != %s * %s", a, b, b, a)
			}
		}
	}

	// Distributivity: a*(b+c) == a*b + a*c.
	for _, a := range vals {
		for _, b := range vals {
			for _, c := range vals {
				lhs := a.Mul(b.Add(c))
				rhs := a.Mul(b).Add(a.Mul(c))
				if !lhs.Equal(rhs) {
					t.Errorf("distributivity: %s*(%s+%s) = %s, but %s*%s + %s*%s = %s",
						a, b, c, lhs, a, b, a, c, rhs)
				}
			}
		}
	}
}

func TestRatioNormalized(t *testing.T) {
	// All constructed ratios are in lowest terms with positive denominator.
	cases := [][2]int64{
		{2, 4}, {3, 9}, {-6, 8}, {0, 5}, {7, 1}, {-3, -6},
	}
	for _, tc := range cases {
		r := ratio.New(tc[0], tc[1])
		if r.Denom <= 0 {
			t.Errorf("New(%d,%d) has non-positive denom: %s", tc[0], tc[1], r)
		}
		// Check GCD is 1 (unless numerator is 0).
		if r.Num != 0 {
			g := gcd(abs64(r.Num), abs64(r.Denom))
			if g != 1 {
				t.Errorf("New(%d,%d) = %s not fully reduced (gcd=%d)", tc[0], tc[1], r, g)
			}
		}
	}
}

// ---- Sign/Verify Determinism ----

func TestSignDeterministicChallenge(t *testing.T) {
	// The challenge is Hash(message) which is deterministic.
	msg := []byte("determinism test")
	c1 := Hash(msg)
	c2 := Hash(msg)
	if c1 != c2 {
		t.Error("Hash(message) not deterministic")
	}
}

func TestVerifyRejectsTamperedChallenge(t *testing.T) {
	// Manually construct a signature with wrong challenge.
	l := buildMatureLattice()
	params := DefaultParams(Security128)
	kp := GenerateKeyPair(l, params, testFactory)

	msg := []byte("test")
	sig, err := Sign(&kp.Private, msg, params)
	if err != nil {
		t.Fatalf("Sign: %v", err)
	}

	fp := FingerprintFromSpore(kp.Public.Spore)

	// Tamper with challenge.
	sig.Challenge[0] ^= 0xFF
	if Verify(fp, msg, sig) {
		t.Error("tampered challenge should not verify")
	}
}

// ---- Helper functions ----

func gcd(a, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func abs64(n int64) int64 {
	if n < 0 {
		return -n
	}
	return n
}