package cayley

import (
	"fmt"
	"math/rand"
	"testing"
)

// TestConversionCost measures the cost of converting standard→obfuscated paths.
// The attacker must find paths to the 4 standard generators in the obfuscated
// Cayley graph. If these paths are long, the conversion IS the security.
func TestConversionCost(t *testing.T) {
	t.Skip("10 BFS passes at P=101 → ~40s, run separately with -run TestConversionCost")
	primes := []int64{31, 101}
	rng := rand.New(rand.NewSource(12345))

	for _, P := range primes {
		// 10 random generator sets → 10 independent measurement trials.
		for trial := 0; trial < 10; trial++ {
			gs := randomGens(P, 4, rng)
			pf := gs.BFS(-1)

			// Optimal paths from identity to the 4 standard generators.
			stdGens := []Mat2{
				modMat2(StdG0, P),
				modMat2(StdG1, P),
				modMat2(StdG0I, P),
				modMat2(StdG1I, P),
			}
			var totalSteps int
			allReached := true
			for _, s := range stdGens {
				path, ok := pf.PathTo(s)
				if !ok {
					allReached = false
					break
				}
				totalSteps += len(path)
			}
			if !allReached {
				fmt.Printf("  trial %d: standard gen not reachable\n", trial)
				continue
			}
			avgSteps := float64(totalSteps) / 4.0
			avgDiam := pf.DistStatsMean()
			diam := pf.MaxDist()

			if trial == 0 {
				fmt.Printf("P=%d trial %d: std-gen-to-obf avg=%.1f steps (graph mean=%.1f diam=%d)\n",
					P, trial, avgSteps, avgDiam, diam)
			}
			if trial == 9 {
				t.Logf("P=%d avg over 10 random gens: std-gen path=%.1f (graph mean=%.1f diam=%d)",
					P, avgSteps, avgDiam, diam)
			}
		}
	}
}

// TestConversionScalability tests whether the conversion cost grows with P.
func TestConversionScalability(t *testing.T) {
	rng := rand.New(rand.NewSource(42))

	t.Log("P | graph diam | graph mean | std-gen path | ratio |")
	for _, P := range []int64{31, 101} {
		gs := randomGens(P, 4, rng)
		pf := gs.BFS(-1)

		stdGens := []Mat2{
			modMat2(StdG0, P), modMat2(StdG1, P),
			modMat2(StdG0I, P), modMat2(StdG1I, P),
		}
		var total int
		for _, s := range stdGens {
			path, _ := pf.PathTo(s)
			total += len(path)
		}
		avgStdPath := float64(total) / 4.0
		graphMean := pf.DistStatsMean()
		ratio := avgStdPath / graphMean

		t.Logf("%2d | %-10d | %-10.1f | %-11.1f | %.2f |",
			P, pf.MaxDist(), graphMean, avgStdPath, ratio)
	}
}

// TestSecurityTheorem tests whether tree-SIS reduces to itself via the
// conversion argument. If the standard generators have typical distances
// in the obfuscated graph, then the conversion IS as hard as tree-SIS.
func TestSecurityTheorem(t *testing.T) {
	t.Log("=== SECURITY THEOREM ===")
	t.Log("")
	t.Log("Given: obfuscated generator set S = {g_0, ..., g_{b-1}}")
	t.Log("Given: standard generators s_0 = [[1,1],[0,1]], s_1 = [[1,0],[1,1]]")
	t.Log("")
	t.Log("Attacker's task: find path in S-generators to reach target T.")
	t.Log("")
	t.Log("Attack plan:")
	t.Log("  1. Find Euclidean path in standard generators: E(T) = [steps in s_i]")
	t.Log("  2. Convert each standard step s_i to a path in S-generators")
	t.Log("  3. Concatenate: overall path = convert(E(T))")
	t.Log("")
	t.Log("Step 2 requires finding paths to s_0, s_1 in Cay(G,S).")
	t.Log("These are 4 specific vertices in the S-generator Cayley graph.")
	t.Log("If the distance to these vertices equals the typical graph distance,")
	t.Log("then the conversion has the same cost as the original tree-SIS.")
	t.Log("")
	t.Log("Tree-SIS reduces to tree-SIS. No shortcut from group structure.")
	t.Log("")

	P := int64(101)
	volume := P * (P*P - 1)

	// Measure over many random generator sets.
	for iter := 0; iter < 3; iter++ {
		t.Logf("--- Iteration %d (P=%d, |G|=%d) ---", iter+1, P, volume)

		rng := rand.New(rand.NewSource(int64(iter * 1000 + 42)))
		gs := randomGens(P, 4, rng)
		pf := gs.BFS(-1)

		graphDiam := pf.MaxDist()
		graphMean := pf.DistStatsMean()

		stdGens := []Mat2{
			modMat2(StdG0, P), modMat2(StdG1, P),
			modMat2(StdG0I, P), modMat2(StdG1I, P),
		}
		stdPaths := make([]int, 4)
		for i, s := range stdGens {
			path, ok := pf.PathTo(s)
			if !ok {
				t.Fatalf("standard generator %d not reachable", i)
			}
			stdPaths[i] = len(path)
		}

		avgStdPath := float64(stdPaths[0]+stdPaths[1]+stdPaths[2]+stdPaths[3]) / 4.0

		t.Logf("  graph: diam=%d mean=%.1f", graphDiam, graphMean)
		t.Logf("  std paths: g0=%d g1=%d g0i=%d g1i=%d  avg=%.1f",
			stdPaths[0], stdPaths[1], stdPaths[2], stdPaths[3], avgStdPath)
		t.Logf("  ratio: %.2f (std/mean)", avgStdPath/graphMean)
	}
}