group.go raw

   1  package cayley
   2  
   3  // Mat2 is a 2×2 matrix [[a,b],[c,d]] over Z_P for SL(2).
   4  // Determinant is not enforced by the type — caller must ensure det=1 for SL(2).
   5  type Mat2 struct {
   6  	A, B, C, D int64
   7  }
   8  
   9  // ID returns the identity matrix.
  10  func ID() Mat2 { return Mat2{1, 0, 0, 1} }
  11  
  12  // Mul returns m1 * m2 mod P.
  13  func (m1 Mat2) Mul(m2 Mat2, P int64) Mat2 {
  14  	return Mat2{
  15  		A: mod((m1.A*m2.A+m1.B*m2.C)%P, P),
  16  		B: mod((m1.A*m2.B+m1.B*m2.D)%P, P),
  17  		C: mod((m1.C*m2.A+m1.D*m2.C)%P, P),
  18  		D: mod((m1.C*m2.B+m1.D*m2.D)%P, P),
  19  	}
  20  }
  21  
  22  // Eq reports whether m1 == m2.
  23  func (m1 Mat2) Eq(m2 Mat2) bool {
  24  	return mod(m1.A, 1<<60) == mod(m2.A, 1<<60) &&
  25  		mod(m1.B, 1<<60) == mod(m2.B, 1<<60) &&
  26  		mod(m1.C, 1<<60) == mod(m2.C, 1<<60) &&
  27  		mod(m1.D, 1<<60) == mod(m2.D, 1<<60)
  28  }
  29  
  30  // Det returns det(m) mod P.
  31  func (m Mat2) Det(P int64) int64 {
  32  	return mod((m.A*m.D-m.B*m.C)%P, P)
  33  }
  34  
  35  // Inv returns m^{-1} mod P (for SL(2)).
  36  func (m Mat2) Inv(P int64) Mat2 {
  37  	return Mat2{
  38  		A: mod(m.D, P),
  39  		B: mod(-m.B, P),
  40  		C: mod(-m.C, P),
  41  		D: mod(m.A, P),
  42  	}
  43  }
  44  
  45  func mod(x, P int64) int64 {
  46  	x = x % P
  47  	if x < 0 {
  48  		x += P
  49  	}
  50  	return x
  51  }
  52  
  53  // Standard generators of SL(2): g0 = [[1,1],[0,1]], g1 = [[1,0],[1,1]].
  54  var (
  55  	StdG0  = Mat2{1, 1, 0, 1}
  56  	StdG1  = Mat2{1, 0, 1, 1}
  57  	StdG0I = Mat2{1, -1, 0, 1} // g0^{-1}
  58  	StdG1I = Mat2{1, 0, -1, 1} // g1^{-1}
  59  )
  60  
  61  // GeneratorSet holds a set of generators (as matrices) for the Cayley graph.
  62  type GeneratorSet struct {
  63  	Gens  []Mat2 // b generators (each with an inverse implied)
  64  	P     int64
  65  	Names []string // optional names
  66  }
  67  
  68  // StandardGens returns the 4 standard SL(2) generators with their inverses.
  69  func StandardGens(P int64) *GeneratorSet {
  70  	return &GeneratorSet{
  71  		Gens: []Mat2{
  72  			modMat2(StdG0, P),
  73  			modMat2(StdG1, P),
  74  			modMat2(StdG0I, P),
  75  			modMat2(StdG1I, P),
  76  		},
  77  		P:     P,
  78  		Names: []string{"g0", "g1", "g0i", "g1i"},
  79  	}
  80  }
  81  
  82  // Walk returns the group element reached by walking the path from start.
  83  func (gs *GeneratorSet) Walk(start Mat2, path []int8) Mat2 {
  84  	m := start
  85  	for _, idx := range path {
  86  		m = m.Mul(gs.Gens[idx], gs.P)
  87  	}
  88  	return m
  89  }
  90  
  91  // PathToBytes encodes a path as a byte slice. Each step takes 1 byte (index 0..b-1).
  92  func PathToBytes(path []int8) []byte {
  93  	b := make([]byte, len(path))
  94  	for i, idx := range path {
  95  		b[i] = byte(idx)
  96  	}
  97  	return b
  98  }
  99  
 100  // BytesToPath decodes a byte slice to a path.
 101  func BytesToPath(b []byte) []int8 {
 102  	path := make([]int8, len(b))
 103  	for i, v := range b {
 104  		path[i] = int8(v)
 105  	}
 106  	return path
 107  }
 108  
 109  // Norm returns the path length.
 110  func Norm(path []int8) int { return len(path) }
 111  
 112  func modMat2(m Mat2, P int64) Mat2 {
 113  	return Mat2{mod(m.A, P), mod(m.B, P), mod(m.C, P), mod(m.D, P)}
 114  }
 115