package cayley

import "math/rand"

// randomSL2Fast generates a random SL(2, Z_P) matrix using extended GCD.
func randomSL2Fast(P int64, rng *rand.Rand) Mat2 {
	for {
		a := int64(rng.Intn(int(P)))
		c := int64(rng.Intn(int(P)))
		if a == 0 && c == 0 {
			continue
		}
		d, negB := extGcd(a, c, P)
		if d < 0 {
			continue
		}
		b := mod(-negB, P)
		return Mat2{mod(a, P), mod(b, P), mod(c, P), mod(d, P)}
	}
}

// extGcd solves a*x + c*y = 1 mod P and returns (x, y).
func extGcd(a, c, P int64) (x, y int64) {
	oldR, r := a, c
	oldS, s := int64(1), int64(0)
	oldT, t := int64(0), int64(1)
	for r != 0 {
		q := oldR / r
		oldR, r = r, oldR-q*r
		oldS, s = s, oldS-q*s
		oldT, t = t, oldT-q*t
	}
	d := oldR
	u := oldS
	v := oldT
	if d < 0 {
		d = -d
		u = -u
		v = -v
	}
	if d != 1 {
		for x = 0; x < P; x++ {
			for y = 0; y < P; y++ {
				if mod(a*x+c*y, P) == 1 {
					return x, y
				}
			}
		}
		return -1, 0
	}
	return mod(u, P), mod(v, P)
}

// randomGens returns a GeneratorSet with b random SL(2) matrices.
func randomGens(P int64, b int, rng *rand.Rand) *GeneratorSet {
	gens := make([]Mat2, b)
	for i := 0; i < b; i++ {
		gens[i] = randomSL2Fast(P, rng)
	}
	return &GeneratorSet{Gens: gens, P: P}
}
func randomWalk(gs *GeneratorSet, depth int, rng *rand.Rand) []int8 {
	p := make([]int8, depth)
	for i := range p { p[i] = int8(rng.Intn(len(gs.Gens))) }
	return p
}