/*

VERSION: 10 March 2004

========================================================================
This Magma program finds all pointless hyperelliptic genus-3 curves 
over a finite field K of odd characteristic with #K > 7.

Every hyperelliptic genus-3 curve over K can be written in the form

  y^2 = c8*x^8 + c6*x^6 + c5*x^5 + c4*x^4 + ... + c1*x + c0,
  
where the c's are elements of K, where c8 is nonzero, and where the
degree-8 polynomial f on the right hand side of the equation has 
nonzero discriminant.  

If a curve C defined by an equation of the above form is pointless,
then c8 and c0 are nonsquares.  Suppose we fix a set of representatives
S for the classes of (K^*)^2 mod (K^*)^8.  By scaling x, we can assume 
that c0 differs multiplicatively from c8 by an element of S.  By
scaling y, we can assume that c8 is our favorite nonsquare.

To enumerate the possible f's, we choose 8 nonsquare elements
  v_infinity, v0, v1, v2, v3, v4, v5, v6
of K, which will be the leading coefficient of f and the values
of f at 0,1,...,6.  Thus 
    v_infinity = c8 = our favorite nonsquare
and
    v0 = c0 = our favorite nonsquare times an element of S.
The values of v1 through v6 can range through all nonsquares in K.

Given the v's, we solve for the coefficients of f, and then
check to see whether the resulting polynomial takes nonsquare
values at 7,8,...,#K-1.  If it does, then we check to see whether
f has nonzero discriminant.  If it does, then we have found a 
pointless genus-3 hyperelliptic curve over K.

We will represent our f's as vectors in K^8.  A vector 
[c8,c6,c5,c4,c3,c2,c1,c0],c2,c3,c4,c5,c6] will correspond to the
polynomial
c8*x^8 + c6*x^6 + c5*x^5 + c4*x^4 + c3*x^3 + x2*x^2 + c1*x + c0.

========================================================================
*/

/*
VERSION: 10 March 2004. 
Changed initial comment to explain why v_infinity and v_0 range
over smaller sets than the other v's.
Also fixed a typo in a print statement.

VERSION: 26 February 2004.
First public version.
*/

function firstcheck(fvector, pointvalues)
// Here we check whether f(x) is a nonzero square for any x in K.
// Return false if we find such a point, true if not.
// pointvalues is a list of vectors, one for each x in K
// plus one for the infinite point of P1.  For the affine points x,
// the vector is the vector [x^8,x^6,x^5,x^4,x^3,x^2,x,1].
// For the infinite point, the vector is [1,0,0,0,0,0,0,0], so that 
// we check to see whether the leading coefficient of the function
// is a nonsquare.
  for P in pointvalues do
    if IsSquare((fvector,P)) then
      return false;
    end if;
  end for;
  return true;
end function;

function secondcheck(f)
// Given a polynomial f in K[x],
// we check to see that f has nonzero discriminant.
  return 0 ne Discriminant(f);
end function;


function PointlessHyperellipticGenus3(q)
// List the appropriate f's, and apply tests to them.
// Print the f's that pass both tests.
// Return true if no triples pass, false if not.
  assert IsOdd(q);
  assert q gt 7;
  assert #Factorization(q) eq 1;
  
  K<z> := GF(q);
  for gen0 in [g : g in K | g ne 0] do
    if Order(gen0) eq q - 1 then
      gen := gen0;
      break;
    end if;
  end for;

  nonsquare := gen;
  nonsquares := [x : x in K | not IsSquare(x)];
  nonsquaresmodeighthpowers := [];
  addthis := gen;
  repeat 
    nonsquaresmodeighthpowers cat:=[addthis];
    addthis *:=gen^2;
  until {a : a in nonsquares}
         eq {a*b^8 : a in nonsquaresmodeighthpowers,
                     b in K | b ne 0};

  R<x>:=PolynomialRing(K);

  bool := true; 

  // Make the list of values of the appropriate powers of x on
  // the points of the projective line.
  // First the special vector for the infinite point.
  allpoints := [ [K|1,0,0,0,0,0,0,0] ];
  // Then for 0.
  allpoints cat:= [ [K|0,0,0,0,0,0,0,1] ];
  // Then the vectors for the affine points of P1 other than 0.
  allpoints cat:= [ [Evaluate(g,P) :
                     g in [x^8,x^6,x^5,x^4,x^3,x^2,x,1]
                    ] : P in K | P ne 0];
                
  matrix := Transpose(Matrix(K,8, &cat[allpoints[i] : i in [1..8]]));
  testpoints := [Vector(K,8,allpoints[i]) : i in [9..#allpoints]];
 
  for v0 in nonsquaresmodeighthpowers do for v1 in nonsquares do
  time 
  for v2, v3, v4, v5, v6 in nonsquares do
    valuevector := Vector(K,8,[nonsquare,v0,v1,v2,v3,v4,v5,v6]);
    fvector := Solution(matrix,valuevector);
     
    if firstcheck(fvector,testpoints) then
      // Convert the vector representation of f into a polynomial.
      f :=  fvector[1] * x^8
          + fvector[2] * x^6
          + fvector[3] * x^5
          + fvector[4] * x^4
          + fvector[5] * x^3
          + fvector[6] * x^2
          + fvector[7] * x
          + fvector[8];
      if secondcheck(f) then
        bool := false;
        print "This one gives a pointless curve: ";
        print f;
        print "";
      end if;
    end if;
  end for; end for; end for;
  if bool then
    printf "There are no pointless genus-3 hyperelliptic curves over F_%o.",q;
  end if;
  return bool;
end function;