/*

VERSION: 18 February 2004

========================================================================
In this file, we extract all of the explicit examples of pointless
curves from the paper

  Everett W. Howe, Kristen E. Lauter, and Jaap Top:
  Pointless curves of genus three and four,
  preprint, 2004
  
and verify that they have no rational points.

Note: In Magma version 2.10 and later, HyperellipticCurve(f,h)
means the curve y^2 + h*y = f.

*/

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


K := GF(2);
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
(x^4 + x^3 + x^2 + x + 1)*(x^4 + x^2 + 1),
(x^4 + x^3 + x^2 + x + 1)
);
assert #C eq 0;


K := GF(3);
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
- x^8 + x^7 - x^6 - x^5 - x^3 - x^2 + x - 1
);
assert #C eq 0;


K<a>:=GF(4); assert a^2 + a + 1 eq  0;
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
(x^4 + a*x^3 + x^2 + a*x + 1)*(a*x^4 + a*x^3 + a^2*x^2 + a*x + a),
(x^4 + a*x^3 + x^2 + a*x + 1)
);
assert #C eq 0;

K := GF(5);
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
2*x^8 + 3*x^4 + 2
);
assert #C eq 0;


K := GF(7);
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
3*x^8 + 2*x^6 + 3*x^4 + 2*x^2 + 3
);
assert #C eq 0;

K<a> := GF(8); assert a^3 + a + 1 eq 0;
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
(x^4 + x^3 + x^2 + x + 1)*(x^4 + a^6*x^3 + a^3*x^2 + a^6*x + 1),
(x^4 + x^3 + x^2 + x + 1)
);
assert #C eq 0;

K<a>:= GF(9); assert a^2 - a - 1 eq 0;
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
a*(x^8 + 1)
);
assert #C eq 0;

K := GF(11);
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
2*x^8 + 4*x^6 - 2*x^4 + 4*x^2 + 2
);
assert #C eq 0;

K := GF(13);
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
2*x^8 + 3*x^7 + 3*x^6 + 4*x^4 + 3*x^2 + 3*x + 2
);
assert #C eq 0;

K<a> := GF(16); assert a^4 + a + 1 eq 0;
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
(x^4 + a^3*x^3 + x^2 + a^3*x + 1)*(a^3*x^4 + a^3*x^3 + a^14*x^2 + a^3*x + a^3),
(x^4 + a^3*x^3 + x^2 + a^3*x + 1)
);
assert #C eq 0;

K := GF(17);
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
3*x^8 - 2*x^5 + 4*x^4 - 2*x^3 + 3
);
assert #C eq 0;

K := GF(19);
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
2*x^8 - x^6 - 8*x^4 - x^2 + 2
);
assert #C eq 0;

K := GF(23);
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
5*x^8 + x^6 + 6*x^5 + 7*x^4 - 6*x^3 + x^2 + 5
);
assert #C eq 0;

K<a> := GF(25); assert a^2 - a + 2 eq 0;
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
a*(x^8 + 1)
);
assert #C eq 0;

// =================================================================

q := 5;
K<a> := GF(q);
P2<x,y,z> := ProjectiveSpace(K,2);
f := x^4 + y^4 + z^4 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;


q := 7;
K<a> := GF(q);
P2<x,y,z> := ProjectiveSpace(K,2);
f := x^4 + y^4 + 2*z^4 + 3*x^2*z^2 + 3*y^2*z^2 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;


q := 9;
K<a> := GF(q); assert a^2 - a - 1 eq 0;
P2<x,y,z> := ProjectiveSpace(K,2);
f := x^4 - y^4 + a^2*z^4 + x^2*y^2;
C := Curve(P2,f);
assert #Places(C,1) eq 0;


q := 11;
K<a> := GF(q);
P2<x,y,z> := ProjectiveSpace(K,2);
f := x^4 + y^4 + z^4 + x^2*y^2 + x^2*z^2 + y^2*z^2 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;


q := 13;
K<a> := GF(q);
P2<x,y,z> := ProjectiveSpace(K,2);
f := x^4 + y^4 + 2*z^4 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;


q := 17;
K<a> := GF(q);
P2<x,y,z> := ProjectiveSpace(K,2);
f := x^4 + y^4 + 2*z^4 + x^2*y^2 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;


q := 19;
K<a> := GF(q);
P2<x,y,z> := ProjectiveSpace(K,2);
f := x^4 + y^4 + z^4 + 7*x^2*y^2 - x^2*z^2 - y^2*z^2 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;


q := 23;
K<a> := GF(q);
P2<x,y,z> := ProjectiveSpace(K,2);
f := x^4 + y^4 + z^4 + 10*x^2*y^2 - 3*x^2*z^2 - 3*y^2*z^2 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;


q := 29;
K<a> := GF(q);
P2<x,y,z> := ProjectiveSpace(K,2);
f := x^4 + y^4 + z^4 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;

// =================================================================

q := 3;
K<a> := GF(q);
P2<x,y,z> := ProjectiveSpace(K,2);
f:= x^4 + x*y*z^2 + y^4 + y^3*z - y*z^3 + z^4  ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;

// =================================================================

q := 2;
K<a> := GF(q);
P2<x,y,z> := ProjectiveSpace(K,2);
f := (x^2 + x*z)^2 + (x^2 + x*z)*(y^2 + y*z) + (y^2 + y*z)^2 + z^4 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;
assert Genus(C) eq 3;


q := 4; 
K<a> := GF(q);  assert a^2 + a + 1 eq 0;
P2<x,y,z> := ProjectiveSpace(K,2);
f := (x^2 + x*z)^2 + a*(x^2 + x*z)*(y^2 + y*z) + (y^2 + y*z)^2 + a^2*z^4 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;
assert Genus(C) eq 3;


q := 8; 
K<a> := GF(q); assert a^3 + a + 1 eq 0;
P2<x,y,z> := ProjectiveSpace(K,2);
f := (x^2 + x*z)^2 + (x^2 + x*z)*(y^2 + y*z) + (y^2 + y*z)^2 + a^3*z^4 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;
assert Genus(C) eq 3;


q := 16; 
K<a> := GF(q); assert a^4 + a + 1 eq 0;
P2<x,y,z> := ProjectiveSpace(K,2);
f := (x^2 + x*z)^2 + a*(x^2 + x*z)*(y^2 + y*z) + (y^2 + y*z)^2 + a^7*z^4 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;
assert Genus(C) eq 3;


q := 32; 
K<a> := GF(q); assert a^5 + a^2 + 1 eq 0;
P2<x,y,z> := ProjectiveSpace(K,2);
f := (x^2 + x*z)^2 + (x^2 + x*z)*(y^2 + y*z) + (y^2 + y*z)^2 + z^4 ;
C := Curve(P2,f);
assert #Places(C,1) eq 0;
assert Genus(C) eq 3;

// =================================================================

function check(f,g);
  K := BaseRing(Parent(f));
  if Degree(f) ne 3 or Degree(g) ne 3 then
    return false;
  end if;
  leadterms := [Coefficient(h,3) : h in [f,g]];
  if #[b : b in leadterms | IsSquare(b)] ne 1 then
    return false;
  end if;
  for a in K do
    if IsSquare(Evaluate(f,a)) and IsSquare(Evaluate(g,a)) then
      return false;
    end if;
  end for;
  return 0 ne Discriminant(f*g);
end function;

K<a>:=GF(3);
R<x>:=PolynomialRing(K);
f := x^3 - x - 1;
g :=  - x^3 + x - 1;
assert check(f,g);

K<a>:=GF(5);
R<x>:=PolynomialRing(K);
f := x^3 - x + 2;
g :=  2 *x^3 - 2 *x;
assert check(f,g);

K<a>:=GF(7);
R<x>:=PolynomialRing(K);
f := x^3 - 3;
g :=  3* x^3 - 1;
assert check(f,g);

K<a>:=GF(9);
assert 0 eq a^2 - a - 1;
R<x>:=PolynomialRing(K);
f := x^3 - x + 1 ;
g :=  a *(x^3 - x - 1) ;
assert check(f,g);

K<a>:=GF(11);
R<x>:=PolynomialRing(K);
f := x^3 - x - 3;
g :=  2* x^3 - 2 *x - 5;
assert check(f,g);

K<a>:=GF(13);
R<x>:=PolynomialRing(K);
f := x^3 + 1 ;
g :=  2*x^3 - 5;
assert check(f,g);

K<a>:=GF(17);
R<x>:=PolynomialRing(K);
f := x^3 + x ;
g :=  3* x^3 - 8* x^2 - 3* x + 5 ;
assert check(f,g);

K<a>:=GF(19);
R<x>:=PolynomialRing(K);
f := x^3 + 2;
g :=  2 *x^3 + 1;
assert check(f,g);

K<a>:=GF(23);
R<x>:=PolynomialRing(K);
f := x^3 + x + 6 ;
g :=  5 *x^3 + 9 *x^2 - 3 *x + 10;
assert check(f,g);

K<a>:=GF(25);
assert 0 eq a^2 - a + 2;
R<x>:=PolynomialRing(K);
f := x^3 + x + 1 ;
g :=  a*(x^3 + x^2 + 2);
assert check(f,g);

K<a>:=GF(27);
assert 0 eq a^3 - a + 1;
R<x>:=PolynomialRing(K);
f := x^3 - x + a^5;
g :=  -x^3 + x + a^5;
assert check(f,g);

K<a>:=GF(29);
R<x>:=PolynomialRing(K);
f := x^3 + x ;
g :=  2 *x^3 + 12* x + 14;
assert check(f,g);

K<a>:=GF(31);
R<x>:=PolynomialRing(K);
f := x^3 - 10;
g :=  3 *x^3 + 9;
assert check(f,g);

K<a>:=GF(37);
R<x>:=PolynomialRing(K);
f := x^3 + x + 4 ;
g :=  2 *x^3 - 17* x^2 + 5 *x + 15 ;
assert check(f,g);

K<a>:=GF(41);
R<x>:=PolynomialRing(K);
f := x^3 + x + 17 ;
g :=  3* x^3 - x^2 - 12 *x - 16;
assert check(f,g);

K<a>:=GF(43);
R<x>:=PolynomialRing(K);
f := x^3 - 9;
g :=  2 *x^3 + 18;
assert check(f,g);

K<a>:=GF(47);
R<x>:=PolynomialRing(K);
f := x^3 + 5* x - 12 ;
g :=  5* x^3 + 2* x^2 + 19* x - 9;
assert check(f,g);

K<a>:=GF(49);
assert 0 eq a^2 - a + 3;
R<x>:=PolynomialRing(K);
f := x^3 + 4 ;
g :=  a *(x^3 + 2) ;
assert check(f,g);


// =================================================================

function eqcheck(f,g);
  K := BaseRing(Parent(f));
  A2<x,y>:=AffineSpace(K,2);
  numg := Numerator(g^2/g);
  deng := Denominator(g^2/g); 
  F := Evaluate(deng,y)*Evaluate(f,x) - Evaluate(numg,y);
  C := ProjectiveClosure(Curve(A2,F));
  return Genus(C) eq 4 and #Places(C,1) eq 0;
end function;


q := 3;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3 - x;
g := (x^4 + 1)/(x^2 + 1)^2;
assert eqcheck(f,g);

q := 5;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3 - x;
g := -2*(x^2 - 2)^2/(x^2 + 2)^2;
assert eqcheck(f,g);

q := 7;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3;
g := 2* x^6 + 2;
assert eqcheck(f,g);

q := 9;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3 - x;
g := (x^4 + a^2)/(x^2 + a^5)^2;
assert eqcheck(f,g);

q := 11;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3 - x;
g := (3* x^4 + 4 *x^2 + 3)/(x^2 + 1)^2;
assert eqcheck(f,g);

q := 13;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3;
g := 4* x^6 + 6;
assert eqcheck(f,g);

q := 19;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3;
g := 2 *x^6 + 2;
assert eqcheck(f,g);

q := 27;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3 - x;
g := a^18 * (x^4 + 1)/(x^2 + 1)^2;
assert eqcheck(f,g);

q := 31;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3;
g := 5 *x^6 + 20 *x^4 + 20 *x^2 + 5;
assert eqcheck(f,g);

q := 43;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3;
g := 7 *x^6 + 8 *x^4 + 8 *x^2 + 7;
assert eqcheck(f,g);

q := 49;
K<a>:=GF(q);
R<x>:=PolynomialRing(K);
f := x^3;
g := 2* x^6 + a;
assert eqcheck(f,g);

// =================================================================

K<a>:=GF(2); t := K!1; assert Trace(t) eq 1;
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
(x^5 + x^2 + 1)*(x^4 + x^3 + x^2 + x) + t*(x^5 + x^2 + 1)^2,
(x^5 + x^2 + 1)
);
assert Genus(C) eq 4 and #Places(C,1) eq 0;

K<a>:=GF(4); t := a; assert Trace(t) eq 1;
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
(x^5 + x^2 + 1)*(x^3 + 1) + t*(x^5 + x^2 + 1)^2,
(x^5 + x^2 + 1)
);
assert Genus(C) eq 4 and #Places(C,1) eq 0;

K<a>:=GF(8); t := a^3; assert Trace(t) eq 1;
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
(x^5 + x^2 + 1)*(x^4 + x^3 + x^2 + x) + t*(x^5 + x^2 + 1)^2,
(x^5 + x^2 + 1)
);
assert Genus(C) eq 4 and #Places(C,1) eq 0;


K<a>:=GF(16); t := a^3; assert Trace(t) eq 1;
R<x>:=PolynomialRing(K);
C := HyperellipticCurve(
(x^5 + x^2 + 1)*(x^3 + 1) + t*(x^5 + x^2 + 1)^2,
(x^5 + x^2 + 1)
);
assert Genus(C) eq 4 and #Places(C,1) eq 0;

// =================================================================

K<a>:=GF(32); assert a^5 + a^2 + 1 eq 0;

P2<u,v,w>:=ProjectiveSpace(K,2);
R3<x,y,z>:=PolynomialRing(K,3);

f := Numerator(y^2 + y + x + 1/x + 1);
g := Numerator(z^2 + z + 
              (a^7*x^4 + a^30*x^3*y + a^13*x^2 + x + a^23*x*y + a^6)
              /(x^3 + a^15*x^2 + x + a^28));
             
I := ideal<R3 | [f,g]>;
II := EliminationIdeal(I,{x,z});
F := Basis(II)[1];
G := Numerator(Evaluate(F,[u/w,0,v/w]));
G := Factorization(G)[2][1];
C := Curve(P2,G);
assert Genus(C) eq 4 and #Places(C,1) eq 0;


f := Numerator(y^2 + y + x + a^7/x);
g := Numerator(z^2 + z + 
              (a^4*x^4 + a^7*x^3*y + a^3*x^3 + a^23*x^2*y 
                       + a^28*x^2 + a^28*x*y + a^16)
              /(x^3 + a^25*x^2 + a^22*x + a^25));
             
I := ideal<R3 | [f,g]>;
II := EliminationIdeal(I,{x,z});
F := Basis(II)[1];
G := Numerator(Evaluate(F,[u/w,0,v/w]));
G := Factorization(G)[2][1];
C := Curve(P2,G);
assert Genus(C) eq 4 and #Places(C,1) eq 0;