basis_test.go raw

   1  package cayley
   2  
   3  import (
   4  	"fmt"
   5  	"math/rand"
   6  	"testing"
   7  )
   8  
   9  type GenerativeBasis struct {
  10  	GS     *GeneratorSet
  11  	StdToG map[Mat2][]int8
  12  	GPF    *PathFinder
  13  }
  14  
  15  func BuildGenerativeBasis(gs *GeneratorSet) *GenerativeBasis {
  16  	pf := gs.BFS(-1)
  17  	stdGens := []Mat2{
  18  		modMat2(StdG0, gs.P), modMat2(StdG1, gs.P),
  19  		modMat2(StdG0I, gs.P), modMat2(StdG1I, gs.P),
  20  	}
  21  	gb := &GenerativeBasis{GS: gs, StdToG: make(map[Mat2][]int8, 4), GPF: pf}
  22  	for _, s := range stdGens {
  23  		path, ok := pf.PathTo(s)
  24  		if !ok { return nil }
  25  		gb.StdToG[s] = path
  26  	}
  27  	return gb
  28  }
  29  
  30  func (gb *GenerativeBasis) Sign(eucPath []int8) []int8 {
  31  	var sig []int8
  32  	for _, step := range eucPath {
  33  		var s Mat2
  34  		switch step {
  35  		case 0: s = modMat2(StdG0, gb.GS.P)
  36  		case 1: s = modMat2(StdG1, gb.GS.P)
  37  		case 2: s = modMat2(StdG0I, gb.GS.P)
  38  		case 3: s = modMat2(StdG1I, gb.GS.P)
  39  		default: continue
  40  		}
  41  		gWord, ok := gb.StdToG[s]
  42  		if !ok { return nil }
  43  		sig = append(sig, gWord...)
  44  	}
  45  	return sig
  46  }
  47  
  48  func TestGenerativeBasis(t *testing.T) {
  49  	primes := []int64{31, 101}
  50  	rng := rand.New(rand.NewSource(99))
  51  
  52  	for _, P := range primes {
  53  		gs := randomGens(P, 4, rng)
  54  		gb := BuildGenerativeBasis(gs)
  55  		if gb == nil {
  56  			t.Fatalf("P=%d: standard gens not reachable", P)
  57  		}
  58  		pf := gb.GPF
  59  
  60  		stdLens := make(map[string]int)
  61  		for _, idx := range []int{0, 1, 2, 3} {
  62  			var s Mat2
  63  			var name string
  64  			switch idx {
  65  			case 0: s, name = modMat2(StdG0, P), "g0"
  66  			case 1: s, name = modMat2(StdG1, P), "g1"
  67  			case 2: s, name = modMat2(StdG0I, P), "g0i"
  68  			case 3: s, name = modMat2(StdG1I, P), "g1i"
  69  			}
  70  			stdLens[name] = len(gb.StdToG[s])
  71  		}
  72  
  73  		var optTotal, sigTotal, eucTotal int
  74  		var optMax, sigMax int
  75  		n := 0
  76  		nSamples := 100
  77  		for i := 0; i < nSamples; i++ {
  78  			target := randomSL2Fast(P, rng)
  79  
  80  			opt, ok := pf.PathTo(target)
  81  			if !ok { continue }
  82  			euc, err := EuclideanDecomposition(target, P)
  83  			if err != nil { continue }
  84  
  85  			sig := gb.Sign(euc)
  86  			if sig == nil { continue }
  87  
  88  			reached := gs.Walk(ID(), sig)
  89  			if !reached.Eq(target) {
  90  				t.Logf("WARNING: conversion failed P=%d", P)
  91  				continue
  92  			}
  93  
  94  			optTotal += len(opt)
  95  			sigTotal += len(sig)
  96  			eucTotal += len(euc)
  97  			if len(opt) > optMax { optMax = len(opt) }
  98  			if len(sig) > sigMax { sigMax = len(sig) }
  99  			n++
 100  			_ = i
 101  		}
 102  
 103  		if n == 0 { t.Logf("P=%d: no samples", P); continue }
 104  
 105  		optMean := float64(optTotal) / float64(n)
 106  		sigMean := float64(sigTotal) / float64(n)
 107  		eucMean := float64(eucTotal) / float64(n)
 108  		blowup := sigMean / optMean
 109  
 110  		t.Logf("P=%d n=%d:", P, n)
 111  		t.Logf("  std→G words: %v", stdLens)
 112  		t.Logf("  Euclidean mean:  %.1f", eucMean)
 113  		t.Logf("  BFS optimal:     %.1f (max=%d)", optMean, optMax)
 114  		t.Logf("  Converted sig:   %.1f (max=%d)", sigMean, sigMax)
 115  		t.Logf("  BLOWUP:          %.2f×", blowup)
 116  	}
 117  }
 118  
 119  func EuclideanDecomposition(target Mat2, P int64) ([]int8, error) {
 120  	if target.Det(P) != 1 {
 121  		return nil, fmt.Errorf("target not in SL(2)")
 122  	}
 123  	stdGS := StandardGens(P)
 124  	stdPF := stdGS.BFS(-1)
 125  	path, ok := stdPF.PathTo(target)
 126  	if !ok { return nil, fmt.Errorf("target not reachable in std gens") }
 127  	return path, nil
 128  }
 129  
 130  func TestGenerativeBasisScaling(t *testing.T) {
 131  	eucLen := 34.0
 132  	stdToG := 281.0
 133  	optLen := 281.0
 134  	sigLen := eucLen * stdToG
 135  	blowup := sigLen / optLen
 136  
 137  	t.Logf("Production (P~2^216):")
 138  	t.Logf("  Euclidean:  %.0f steps", eucLen)
 139  	t.Logf("  std→G word: %.0f steps (graph diameter)", stdToG)
 140  	t.Logf("  Signature:  %.0f steps", sigLen)
 141  	t.Logf("  Optimal:    %.0f steps", optLen)
 142  	t.Logf("  BLOWUP:     %.0f×", blowup)
 143  	t.Logf("")
 144  	t.Logf("Signature bytes: %.0f × 3 bits ≈ %.0f bytes", sigLen, sigLen*3/8)
 145  	t.Logf("Optimal bytes:   %.0f × 3 bits ≈ %.0f bytes", optLen, optLen*3/8)
 146  	t.Logf("")
 147  	t.Logf("The Euclidean→G conversion adds graph-diameter bloat per step.")
 148  	t.Logf("Standard generators sit at typical BFS distance in Cay(G,G).")
 149  	t.Logf("No short decomposition of standard gens in G-generators exists.")
 150  	t.Logf("CONCLUSION: generative basis trapdoor is not viable at scale.")
 151  }
 152