(************************************************************)
(* 
** Arithmetik im Koerper GF(3)[i,xi] = GF(729)
** Dabei ist i eine Nullstelle von X**2 + 1
** und xi eine Nullstelle von X**3 - X + 1
**
** Elemente von GF(729) werden dargestellt als 6-tupel
** (x0,x1,x2,x3,x4,x5) bzgl. der Basis (1, i, xi, i*xi, xi**2, i*xi**2)
** ueber GF(3).
*)
(************************************************************)
(*
** Beispiel-Sitzung:

==> i := (0,1,0,0,0,0).
-: (0, 1, 0, 0, 0, 0)

==> xi := (0,0,1,0,0,0).
-: (0, 0, 1, 0, 0, 0)

==> ixi := f3ixi_mult(i,xi).
-: (0, 0, 0, 1, 0, 0)

==> f3ixi_ord(ixi).
-: 52

==> z := (i + xi) mod 3.
-: (0, 1, 1, 0, 0, 0)

==> f3ixi_chkroot(z).
-: true

==> f3ixi_ord(z).
-: 728

==> k := 0;
    while k /= 728 do
        x := f3ixi_rand();
        k := f3ixi_ord(x);
        writeln(x,"; ord = ",k);
    end.
(1, 2, 2, 1, 2, 0); ord = 364
(0, 1, 0, 0, 2, 2); ord = 728

*)
(************************************************************)
(*
** Multiplikation zweier Elemente von GF(3)[i,xi]
*)
function f3ixi_mult(x,y: array[6]): array[6];
var
	z,u: array[6];
begin
	z := y[0]*x;
	(* u := i*x *)
	u := (-x[1],x[0],-x[3],x[2],-x[5],x[4]);
	z := z + y[1]*u;
	(* u := xi*x *)
	u := (-x[4],-x[5],x[0]+x[4],x[1]+x[5],x[2],x[3]);
	z := z + y[2]*u;
	(* u := i*xi*x *)
	u := (x[5],-x[4],-x[1]-x[5],x[0]+x[4],-x[3],x[2]);
	z := z + y[3]*u;
	(* u := xi**2 * x *)
	u := (-x[2],-x[3],x[2]-x[4],x[3]-x[5],x[0]+x[4],x[1]+x[5]);
	z := z + y[4]*u;
	(* u := i*xi**2 * x *)
	u := (x[3],-x[2],-x[3]+x[5],x[2]-x[4],-x[1]-x[5],x[0]+x[4]);
	z := z + y[5]*u;
	return (z mod 3);
end;
(*----------------------------------------------------------*)
(*
** Berechnet die n-te Potenz von x
*)
function f3ixi_pow(x: array[6]; n: integer): array[6];
var
	z: array[6];
	k, len: integer;
begin
	n := n mod 728;
	if n=0 then
		return (1,0,0,0,0,0);
	end;
	len := bit_length(n);
	z := x;
	for k := len-2 to 0 by -1 do
		z := f3ixi_mult(z,z);
		if bit_test(n,k) then
			z := f3ixi_mult(z,x);
		end;
	end;
	return z;
end;
(*----------------------------------------------------------*)
(*
** Stellt fest, ob x eine Primitivwurzel im Koerper GF(729) ist
*)
function f3ixi_chkroot(x: array[6]): boolean;
begin
	if f3ixi_pow(x,364) = (1,0,0,0,0,0) then
		return false;
	elsif f3ixi_pow(x,104) = (1,0,0,0,0,0) then
		return false;
	elsif f3ixi_pow(x,56) = (1,0,0,0,0,0) then
		return false;
	else
		return true;
	end;
end;
(*----------------------------------------------------------*)
(*
** Berechnet die Ordnung eines Elements x /= 0 aus GF(729)
*)
function f3ixi_ord(x: array[6]): integer;
var
	n, n1, i: integer;
begin
	n := 728;
	for i := 1 to 3 do
		n1 := n div 2;
		if f3ixi_pow(x,n1) = (1,0,0,0,0,0) then
			n := n1;
		else
			break;
		end;
	end;
	n1 := n div 7;
	if f3ixi_pow(x,n1) = (1,0,0,0,0,0) then
		n := n1;
	end;
	n1 := n div 13;
	if f3ixi_pow(x,n1) = (1,0,0,0,0,0) then
		n := n1;
	end;
	return n;
end;
(*----------------------------------------------------------*)
(*
** Gibt ein zufaelliges Element von GF(729) zurueck
*)
function f3ixi_rand(): array[6];
const
	N = 729;
var
	n,k: integer;
	z: array[6];
begin
	n := random(N);
	for k := 0 to 5 do
		z[k] := n mod 3;
		n := n div 3;
	end;
	return z;
end;
(************************************************************)