// Code verifying the correctness of the challlenge logarithm

q := 3^6;

F3 := FiniteField(3);
P3<U> := PolynomialRing(F3);
poly := U^6 + 2*U^4 + U^2 + 2*U + 2;
Fq<u> := ext<F3|poly>;
Pq<Z> := PolynomialRing(Fq);

r := (3^509 - 3^255 + 1) div 7;
Fr := GF(r);

h0 := u^316*Z + u^135;
h1 := Z^2 + u^424*Z;

F := h1*Z^q - h0;
factorsF := Factorization(F);
Ix := factorsF[#factorsF][1];
Fn<X> := ext<Fq|Ix>;
N := #Fn - 1;

// Generator of GF(3^(6*509))-{0}
g := X + u^2;

// Encoding pi
Re := RealField(2000);
pival := Pi(Re);
hp := 0;
for i := 0 to 508 do
	hp := hp + u^(Floor(pival*(#Fq)^(i+1)) mod #Fq)*(X^i);
end for;

// This is the logarithm challenge
cofactor := N div r;
h := hp^cofactor;

// log_g(h) mod r is:
x := 1491873998603182663602166336932969933774562818915699213253138\
178777703786430493066480809525652983536765790074515932016074643909\
955366015387428992219846518967940088550218976628414869296477962794\
4571222053133596965907357777487989092312353851456;

// Define the exponent y to be used in the verification:
y := IntegerRing()!(Fr!(x/cofactor));

// Check that h = (g^cofactor)^y
h eq (g^cofactor)^y;