sl2.go raw

   1  package cayley
   2  
   3  import "math/rand"
   4  
   5  // randomSL2Fast generates a random SL(2, Z_P) matrix using extended GCD.
   6  func randomSL2Fast(P int64, rng *rand.Rand) Mat2 {
   7  	for {
   8  		a := int64(rng.Intn(int(P)))
   9  		c := int64(rng.Intn(int(P)))
  10  		if a == 0 && c == 0 {
  11  			continue
  12  		}
  13  		d, negB := extGcd(a, c, P)
  14  		if d < 0 {
  15  			continue
  16  		}
  17  		b := mod(-negB, P)
  18  		return Mat2{mod(a, P), mod(b, P), mod(c, P), mod(d, P)}
  19  	}
  20  }
  21  
  22  // extGcd solves a*x + c*y = 1 mod P and returns (x, y).
  23  func extGcd(a, c, P int64) (x, y int64) {
  24  	oldR, r := a, c
  25  	oldS, s := int64(1), int64(0)
  26  	oldT, t := int64(0), int64(1)
  27  	for r != 0 {
  28  		q := oldR / r
  29  		oldR, r = r, oldR-q*r
  30  		oldS, s = s, oldS-q*s
  31  		oldT, t = t, oldT-q*t
  32  	}
  33  	d := oldR
  34  	u := oldS
  35  	v := oldT
  36  	if d < 0 {
  37  		d = -d
  38  		u = -u
  39  		v = -v
  40  	}
  41  	if d != 1 {
  42  		for x = 0; x < P; x++ {
  43  			for y = 0; y < P; y++ {
  44  				if mod(a*x+c*y, P) == 1 {
  45  					return x, y
  46  				}
  47  			}
  48  		}
  49  		return -1, 0
  50  	}
  51  	return mod(u, P), mod(v, P)
  52  }
  53  
  54  // randomGens returns a GeneratorSet with b random SL(2) matrices.
  55  func randomGens(P int64, b int, rng *rand.Rand) *GeneratorSet {
  56  	gens := make([]Mat2, b)
  57  	for i := 0; i < b; i++ {
  58  		gens[i] = randomSL2Fast(P, rng)
  59  	}
  60  	return &GeneratorSet{Gens: gens, P: P}
  61  }
  62  func randomWalk(gs *GeneratorSet, depth int, rng *rand.Rand) []int8 {
  63  	p := make([]int8, depth)
  64  	for i := range p { p[i] = int8(rng.Intn(len(gs.Gens))) }
  65  	return p
  66  }
  67