bench251_test.go raw

   1  package cayley
   2  
   3  import (
   4  	"math"
   5  	"math/rand"
   6  	"testing"
   7  	"time"
   8  )
   9  
  10  func TestFullBench251(t *testing.T) {
  11  	if testing.Short() {
  12  		t.Skip("P=251 BFS takes ~2min")
  13  	}
  14  	P := int64(251)
  15  	rng := rand.New(rand.NewSource(42))
  16  	volume := P * (P*P - 1)
  17  
  18  	// === BFS: graph statistics ===
  19  	t.Logf("=== P=%d |G|=%d ===", P, volume)
  20  	start := time.Now()
  21  	gs := randomGens(P, 4, rng)
  22  	pf := gs.BFS(-1)
  23  	bfsTime := time.Since(start)
  24  	t.Logf("Obfuscated BFS: %s, %d vertices, diam=%d, mean=%.1f",
  25  		bfsTime.Round(time.Millisecond), pf.Reachable(),
  26  		pf.MaxDist(), pf.DistStatsMean())
  27  
  28  	// === Standard generator BFS ===
  29  	stdGS := StandardGens(P)
  30  	start = time.Now()
  31  	stdPF := stdGS.BFS(-1)
  32  	stdTime := time.Since(start)
  33  	t.Logf("Standard BFS:   %s, diam=%d, mean=%.1f",
  34  		stdTime.Round(time.Millisecond), stdPF.MaxDist(), stdPF.DistStatsMean())
  35  
  36  	// === Generative basis ===
  37  	gb := BuildGenerativeBasis(gs)
  38  	if gb == nil {
  39  		t.Fatal("standard gens not reachable")
  40  	}
  41  	stdLens := make(map[string]int)
  42  	for _, idx := range []int{0, 1, 2, 3} {
  43  		var s Mat2; var name string
  44  		switch idx {
  45  		case 0: s, name = modMat2(StdG0, P), "g0"
  46  		case 1: s, name = modMat2(StdG1, P), "g1"
  47  		case 2: s, name = modMat2(StdG0I, P), "g0i"
  48  		case 3: s, name = modMat2(StdG1I, P), "g1i"
  49  		}
  50  		stdLens[name] = len(gb.StdToG[s])
  51  	}
  52  	t.Logf("std→G words:  %v (avg=%.1f)", stdLens, avgMap(stdLens))
  53  
  54  	// === Blowup: sample 20 targets, reusing precomputed BFS ===
  55  	var eucT, sigT, optT int
  56  	n := 0
  57  	for i := 0; i < 20; i++ {
  58  		target := randomSL2Fast(P, rng)
  59  		euc, ok := stdPF.PathTo(target)
  60  		if !ok { continue }
  61  		opt, ok := pf.PathTo(target)
  62  		if !ok { continue }
  63  		sig := gb.Sign(euc)
  64  		if sig == nil { continue }
  65  		if !gs.Walk(ID(), sig).Eq(target) { continue }
  66  		eucT += len(euc); sigT += len(sig); optT += len(opt); n++
  67  	}
  68  	if n > 0 {
  69  		t.Logf("Blowup n=%d:", n)
  70  		t.Logf("  Euclidean:     %.1f", float64(eucT)/float64(n))
  71  		t.Logf("  Converted sig: %.1f", float64(sigT)/float64(n))
  72  		t.Logf("  BFS optimal:   %.1f", float64(optT)/float64(n))
  73  		t.Logf("  Euc→sig blowup: %.1f×", float64(sigT)/float64(eucT))
  74  		t.Logf("  Sig→opt blowup: %.1f×", float64(sigT)/float64(optT))
  75  	}
  76  
  77  	// === Security ===
  78  	diam := pf.MaxDist()
  79  	mim := math.Pow(4.0, float64(diam)/2.0)
  80  	t.Logf("Security: diam=%d MIM≈2^%.0f", diam, math.Log2(mim))
  81  }
  82  
  83  func avgMap(m map[string]int) float64 {
  84  	var s int
  85  	for _, v := range m { s += v }
  86  	return float64(s) / float64(len(m))
  87  }
  88