package cayley

import (
	"math/rand"
	"testing"
)

// MultiPathSig signs a target using k parallel paths. The signer has a
// trapdoor (generative basis). Splits target into k factors: first k-1
// are random trapdoor paths (short), last factor uses Euclidean+conversion.
func MultiPathSign(target Mat2, gb *GenerativeBasis, k int, rng *rand.Rand) [][]int8 {
	P := gb.GS.P
	gs := gb.GS
	paths := make([][]int8, k)

	// k-1 trapdoor paths (random short walks).
	product := ID()
	for i := 0; i < k-1; i++ {
		depth := int(3 + rng.Intn(5)) // random depth 3-7
		p := randomWalk(gs, depth, rng)
		paths[i] = p
		product = gs.Walk(product, p)
	}

	// Last factor: residual = (product)^{-1} · target.
	residual := product.Inv(P).Mul(target, P)
	euc, err := EuclideanDecomposition(residual, P)
	if err != nil {
		return nil
	}
	converted := gb.Sign(euc)
	if converted == nil {
		return nil
	}
	paths[k-1] = converted

	return paths
}

// MultiPathVerify checks k paths whose product equals target.
func MultiPathVerify(gs *GeneratorSet, paths [][]int8, target Mat2) bool {
	v := ID()
	for _, p := range paths {
		v = gs.Walk(v, p)
	}
	return v.Eq(target)
}

// TestMultiPathSign measures the blowup factor for k=1,2,3.
func TestMultiPathSign(t *testing.T) {
	P := int64(31)
	rng := rand.New(rand.NewSource(42))
	gs := randomGens(P, 4, rng)
	gb := BuildGenerativeBasis(gs)
	if gb == nil {
		t.Fatal("standard gens not reachable")
	}
	pf := gb.GPF

	for _, k := range []int{1, 2, 3, 5, 10} {
		nSamples := 50
		var totalSteps int
		var totalTrap int
		var totalEuc int
		n := 0

		for i := 0; i < nSamples; i++ {
			target := randomSL2Fast(P, rng)

			paths := MultiPathSign(target, gb, k, rng)
			if paths == nil { continue }

			if !MultiPathVerify(gs, paths, target) {
				t.Logf("k=%d: verification failed", k)
				continue
			}

		steps := 0
		for _, p := range paths {
			steps += len(p)
		}

		totalSteps += steps
			totalTrap += len(paths[0]) // first is trapdoor
			if k > 1 {
				totalEuc += len(paths[k-1]) // last is Euclidean-converted
			}
			n++
		}

		if n == 0 { t.Logf("k=%d: no samples", k); continue }
		mean := float64(totalSteps) / float64(n)
		trapMean := float64(totalTrap) / float64(n)
		eucMean := float64(totalEuc) / float64(n)

		t.Logf("k=%d n=%d: sig=%.0f steps (trap=%.0f euc=%.0f) opt~=%.0f",
			k, n, mean, trapMean, eucMean, float64(pf.DistStatsMean()))
	}
}

// TestMultiPathSecurity reports the MIM cost for k-path signatures.
func TestMultiPathSecurity(t *testing.T) {
	t.Log("=== MULTI-PATH SECURITY ===")
	t.Log("")
	t.Log("For k paths of length D each (b generators):")
	t.Log("  Total path encoding: k·D·log₂(b) bits")
	t.Log("  MIM cost: b^{kD/2} (product of k forward/backward half-sets)")
	t.Log("")

	for _, k := range []int{1, 2, 3, 4, 5} {
		// Solve for D such that b^{kD/2} = 2^{128}
		// kD/2 × log₂(b) = 128
		// kD = 256 / log₂(b) = 256/3 ≈ 85.3
		// D = 85.3/k
		D := 85.3 / float64(k)
		totalBits := float64(k) * D * 3.0
		totalBytes := totalBits / 8.0
		t.Logf("  k=%d: D=%.0f steps/path, total=%d steps, %.0f bytes (path) + 43B (target+salt) = %.0f bytes",
			k, D, int(k*int(D)), totalBytes, totalBytes+43)
	}

	t.Log("")
	t.Log("The security is fixed by kD = constant. Multi-path changes")
	t.Log("the number of paths but NOT the total encoding length.")
	t.Log("The lock analogy benefit: eliminates local-search attacks.")
	t.Log("MIM complexity unchanged for fixed security parameter.")
}