Make `GammaLMeetSU` faster by avoiding `MapGammaLToGL`

[fingolfin]

Right now:

gap> GammaLMeetSU(9, 8, 3);; time;
3396

That's over three seconds to compute the generators. That's really slow, by 2-3 orders of magnitude.

A core problems seems to be the use of MapGammaLToGL, which relies on LogFFE, which is slow except for tiny fields: in the tiny fields it is fast because they are implemented using Zech logarithms, so log is fast. But of course in general discrete log is hard (and hence the backbone of many crypto systems).

But we could completely do away with it, because we know the generator matrices and how they are produced. We could look at the paper by Taylor; or just the GAP source code.

So the ideal replacement would duplicate that code but instead of inserting powers of the primitive element omega, immediately insert corresponding powers.

Alternatively, we could "cheat" by collecting together all possible exponents such that omega^e occurs as a matrix entry (there will be maybe a dozen), and using those as a 'hint' for the logarithm computation. That requires less code duplication right now. Unfortunately, this gets difficult if the input matrix has rank 2, as GAP then annoyingly uses the value

e:= Z(q^2) - Z(q^2)^q;

as matrix entry; computing the discrete logarithm of that (at least when q is odd) depends on the defining polynomial of the field. If GAP just used the following value instead (as it does in all other cases), the logarithm would be trivial to compute:

if q mod 2 = 1 then e:= z^( (q+1)/2 ); else e:= o; fi;

Finally I should point out that there are more functions which call MapGammaLToGL and which may need to be improved, but for most of them it's not a big deal because the matrices all only contain 0, 1 or omega. Still, would be worth checking their performance, too.

[fingolfin]

I noticed that there is another problematic value, beta := -(1+z^q/z)^-1 which is chosen like that in Tay87 as an element satisfying \beta + \overline{\beta} = -1, i.e. a zero of the polynomial x^q+x+1 (this is similar to e above, which was chosen to satisfy e + e^q = 0).

[fingolfin]

Argh, but of course Theta is a homomorphism, so we can just resolve this as follows: instead of providing "hints" of the form field element => exponent which then results in field element being mapped to As^exponent we directly provide mappings field element => some-power-of-As, and then we map -(1+z^q/z)^-1 to -(As^0+As^(q-1))^-1.

But probably better on the long term is to refactor the code in the GAP library to expose the functions creating the generators in such a way that one can plug in other values than a primitive root (such as an indeterminate in a rational function field), and then call that function from here. I'll look into writing a corresponding patch for GAP.