Plan
Point counting on hyperelliptic curves ofgenus 3 and higher in large characteristic

Introduction, background
Schoof’s algorithm

Simon Abelard, Pierrick Gaudry, Pierre-Jean Spaenlehauer

Tools for polynomial systems

Caramba – LORIA, Nancy
CNRS, Université de Lorraine, Inria

New complexity for large genus
The case of genus 3 with real multiplication

ECC 2018 – Osaka

1/41

Point counting

2/41

Algorithmic Holy Grail

Let C be a curve of genus g over a finite field Fq .
The number Ni,C of Fqi -rational points of C is finite.
Size of the input: O(g log q)

The Zeta function collects all of them into an analytic object:


i
Ø
T
Z (C, T ) = exp  Ni,C  .
i≥1Weil’s theorem:

Holy Grail of point counting: find an algorithm that compute ZC
in polynomial time in g and log q;ifor a class of curves as large as possible;. . . and maybe in a deterministic way;

Z (C, T ) =. . . and maybe for other algebraic varieties;

PC (T ),
(1 − T )(1 − qT ). . . and maybe also in practice.

where PC (T ) = q 2g T 2g + · · · is with integer coefficients.
Our goal: compute PC (T ) (hence, Z (C, T ) and all of the Ni,C ).
3/41

4/41

A very brief history of point counting

Recent research topics

1985: Schoof’s algorithm, polynomial-time, deterministic for
elliptic curves;

extend p-adic techniques to more varieties (Harvey, Tuitman);

1990: Pila, polynomial-time for fixed genus, deterministic for
Abelian varieties (and therefore Jacobian of curves),

extend average polynomial-time to more varieties (Harvey,
Kedlaya, Sutherland, Massierer);

1999-20xx: Satoh, Kedlaya, Lauder-Wan, polynomial-time,
deterministic in fixed characteristic, with p-adic algorithms.

explicit isogenies and modular equations for genus 2(Couveignes, Ezome, Milio, Martindale);

2014: Harvey, average polynomial-time when dealing withmany C that are reductions of the same curve over Q.

not so much on ℓ-adic methods

5/41

6/41

Our plan for today

Hyperelliptic curves

Let’s concentrate on hyperelliptic curves in large characteristic.

Def. A curve is hyperelliptic if it admits an equationy 2 = f (x ),Known complexities for arbitrary genus:
Pila (1990): O(log q)∆ , where ∆(g) is not explicit;

with f a monic, squarefree polynomial.

2

Huang, with Ierardi (1998) and Adleman (2001): (log q)Õ(g ) .

Remarks:

First goal: make the exponent linear in g.

In characteristic 2, need to modify the equation;
Known complexities for small genus:
Elliptic curves: Schoof (1985), and Schoof-Elkies-Atkin(199x): Õ((log q)4 );Genus 2: G.-Harley (2000) and G.-Schost (2012): Õ((log q)8 );Genus 2 with RM: G.-Kohel-Smith (2011): Õ((log q)5 );Genus 3: ??? Õ((log q)14 ) mentioned here and there.

We assume deg f is odd (imaginary model); enough fortheoretical complexity (maybe not in practice). Thendeg f = 2g + 1 where g is called the genus;
Have to think about the desingularized, projective model;
There is only one point at infinity after desingularization: P∞ ;The Jacobian is an associated Abelian variety of dimension g.

Second goal: give the exponent for genus 3 with and without RM.
7/41

8/41

Divisors

Divisor class group and Jacobian

Let DivC be the free group of points of C:îDivC = D =ØDivisor class group:ïnP P | for almost all P, nP = 0 .

P∈C(Fq )The degree of D ∈ DivC is deg D =q

Pic0C = {Degree-0 divisors}/{Principal divisors}.

nP .

The divisor of a non-zero function ϕ ∈ Fq (C) isdiv(ϕ) =ØThis can be given the geometrical structure of a principally
polarized Abelian variety: the Jacobian of C, and we denote it
JacC .

valP (ϕ)P,

where valP (ϕ) is the valuation of ϕ at P.
The set of such divisors is the group of principal divisors:îRem. A purely geometric definition of JacC can be done via anembedding in a projective space with theta functions.

ï

PrinC = div(ϕ) | ϕ ∈ Fq (C)∗ .
Thm. A principal divisor has degree 0.

9/41

Mumford representation

Weil’s theorem

By Riemann-Roch theorem, each class has a unique representativeof the form

Z (C, T ) =D = P1 + · · · + Pr − r P∞ , with r ≤ g,

Thm. (Mumford representation) Any divisor class can be
uniquely represented by a pair éu(X ), v (X )ê, where
u is monic, of degree at most g;

Link with the Frobenius endomorphism:
Let π be the x Ô→ x q map extended to a map from C to itself andthen linearly to JacC to itself. It can be proven thatP˜C (π) = 0,

deg v < deg u;
u divides v 2 − f ;r

PC (T ),
(1 − T )(1 − qT )Weil’s theorem implies:r
1/2 ;PC (T ) = 2g
i=1 (1 − ui T ), where |ui | = q
if PC (T ) = a0 + a1 T + · · · a2g T 2g , then we havea2g−i = q g−i ai ;! " gthe coeffs are bounded by 2g
g q (could be more precise).

and no two Pi ’s are symmetric w.r.t the x -axis.

If D is as above, then u(X ) =10/41(X − xPi ) and v (xi ) = yi .

Cantor’s algorithm allows to compute efficiently in the Jacobianwhen elements are represented like this.
11/41

where P˜C is PC with reversed-ordered coefficients.
We write χπ (T ) = P˜C (T ) for this characteristic polynomial of
Frobenius.

12/41

Plan

TorsionLet A be an Abelian variety over Fq (A will be JacC ).
The ℓ-torsion subgroup is

Introduction, backgroundA[ℓ] = {P ∈ A(Fq ) | ℓ · P = 0}.
Schoof’s algorithm

Thm. For a prime ℓ coprime to q, the group structure of A[ℓ] is

Tools for polynomial systems

A[ℓ] ∼= (Z/ℓZ)2g .

New complexity for large genus

The set A[ℓ] \ {0} is an algebraic variety of dimension 0, and we
can consider its ideal.
Def. The ideal corresponding to the non-zero ℓ-torsion points isdenoted by Iℓ .

The case of genus 3 with real multiplication

Rem. Iℓ depends on the set of coordinates chosen to represent
A. This could be projective coordinates, or a local affine patch.
14/41

13/41

Frobenius action on A[ℓ]Combining modular information
Main point counting algorithm: (à la Schoof)

Matrix representation of Frobenius.
The Frobenius endomorphism π maps elements of A[ℓ] to A[ℓ].
Viewing A[ℓ] as an Fℓ -vector space of dimension 2g, π acts
linearly on this vector space: it can be represented as a matrix,
whose characteristic polynomial is χC (π) mod ℓ.

g
1. While the product of ℓ’s already handled is < 2gg q :1.1 Pick the next small prime ℓ coprime to q;
1.2 Compute the ℓ-torsion ideal Iℓ ;1.3 Find an efficient representation of Iℓ ;1.4 Compute χC (π) mod ℓ;Thm. The characteristic polynomial of π on A[ℓ] is the
reduction mod ℓ of the global characteristic polynomial of π.

! "2. Reconstruct χC (π) by CRT.
Rem. The number and the size of the ℓ’s is polynomial in g log q.
But the ideal Iℓ is of degree ℓ2g , which is exponential in g.

If Iℓ is an ideal in a coordinate ring Fq [X ], the generic ℓ-torsion
element is represented by the algebra Bℓ = Fq [X ]/Iℓ .
Assuming computing in Bℓ is efficient, we can compute χC (π)
mod ℓ.
Note: “efficient” is not so simple to define, here.

Rem. The step 1.3 does not exist in the elliptic case, where weuse the division polynomial ψℓ to represent Iℓ .
But 1.3 is the most important step for higher genus.
15/41

16/41

Coordinate systems for IℓPlan

An efficient representation starts with a coordinate system.

Introduction, background

Theta functions:
Schoof’s algorithm

Need many coordinates, at least 2g ;But nice projective embedding: less non-genericity to handle.

Tools for polynomial systems

Mumford coordinates:
New complexity for large genus

Optimal number of coordinates O(g);But local affine coordinates: many non-generic cases if anintermediate point is not in this affine patch.

The case of genus 3 with real multiplication

17/41

What do we want?

18/41

Gröbner bases – F4 / F5 algorithm
What is it?
Algorithm that computes a Gröbner basis of the ideal, for any
monomial order; (Faugère)

Coordinates of a generic ℓ-torsion element will be in

Usually done in two steps: GB for grevlex and then changeof ordering for lex;

Bℓ = Fq [X ]/Iℓ ,where X is the set of 2g Mumford coordinates.

Heavily relies on linear algebra.
Good points, bad points.

Applying Frobenius = raising to the q-th power in Bℓ .
This means being able to work “modulo the ideal”.
This is essentially the definition of a Gröbner basis.

Bad complexity bounds if nothing is known.
Good complexity bounds require hard-to-prove properties of
the input system.

Rem. We are interested both in proven complexity bounds andpractical efficiency.

Really compute the GB: need to take care about parasite
components (saturation).
Robust to many situations.
Some public and efficient implementations.
19/41

20/41

Resultants (univariate)

Geometric resolution

What is it ?
Algorithm to compute a combination of two input
polynomials, with one less variable;
Produces an element in the ideal: need to repeat to produce a
generating set;
Polynomial arithmetic;
There exist multivariate resultants, but mostly of theoreticalinterest.
Good points, bad points.
Not always easy to guarantee that we have a complete set ofgenerators;
Really bad complexities when there are many variables;
Complexity bound do not assume too much on the input
system;Some public and efficient implementations.

What is it ?
Algorithm to put the system in triangular form, close to GB
for lex order (Giusti, Lecerf, Salvy, Cafure, Matera, . . . );Incremental process based on Newton lifting;Relies on (univariate) polynomial arithmetic and (Jacobian)matrix inversion.
Good points, bad points.
Intrinsically probabilistic (Monte Carlo);
Only prototype implementations available;
Requires some nice properties of the input system;
Said properties easier to prove than for GB;
Good complexity bounds.
22/41

21/41

XL

Summary of the situation for Iℓ

What is it ?
The following is specific to our case.
Multi-homogeneity is an important property of our systems (seebelow).

Algorithm that compute a solution in a given field ofdefinition (Courtois, Klimov, Patarin, Shamir, . . . )Same general idea as F4 (Lazard’s algorithm using Macaulay
matrices);
Heavily relies on linear algebra.
Good points, bad points.

F4
ResultantsGeom. resol.
XL

Efficient only for solution with coordinates in a small finite
field;
Complexity bounds require hard-to-prove properties of the
input system;

Applicablein theory?

Applicablein practice

Can usemulti-homog.

?
?

Rem. For your own problem, you’ll have to write your own table.

Some public and efficient implementations (for basic XL);
Sometimes heuristically more efficient than F4.
23/41

24/41

Plan

Equations for the torsion (1)Take a generic divisor:
D=

Introduction, backgroundgØ(Pi − P∞ ),i=1

Schoof’s algorithm

where Pi = (xi , yi ) and write ℓD = 0.

Tools for polynomial systems

For any i, ℓ(Pi − P∞ ) is equivalent to a reduced divisor in
Mumford representation:ℓ(Pi − P∞ ) = éui (X ), vi (X )ê,New complexity for large genus

where ui and vi are polynomials with coeffs that depends on xi
and yi . They are exactly Cantor’s division polynomials:

The case of genus 3 with real multiplicationui (X ) = δℓAxi − X
4yi2

B, vi (X ) = εℓAxi − X
4yi2

B

.
26/41

25/41

Equations for the torsion (2)Multi-homogeneityℓD = 0 ⇐⇒ éu1 (X ), v1 (X )ê + · · · + éug (X ), v1 (X )ê = 0.

This strategy looks bogus, because we have increased the numberof variables from O(g) to O(g 2 ), and the degrees O(ℓ2 ) of theequations did not decrease to compensate for it.

Applying g − 1 times the group law: difficult to control the
degrees.

Def. A multi-homogeneous polynomial system is a set of
equations f1 (X , Y ) = 0, . . . , fk (X , Y ) = 0, in two blocks ofvariables, where for each equation, the degree in X is ≤ dX andthe degree in Y is ≤ dY .

Cantor sketched the following approach:Consider the function
ϕ(X , Y ) = P(X ) + YQ(X )and divϕ = éu1 (X ), v1 (X )ê + · · · + éug (X ), v1 (X )ê.

Key quantity for complexity analysis:

Degrees of P and Q must be ≈ g 2 /2 (parity of g − ℓ plays a role).

ndxnx dy y ,Set g 2 indeterminates for the coefficients of P and Q. We have asystem of equations
P(X ) + εℓAxi − X
4yi2

B

Q(X ) ≡ 0 mod δℓAxi − X
4yi2

B

where nx and ny are the number of variables in each block.
We have added g 2 variables, but they occur in degree 1, so
this won’t hurt the multi-homogeneous complexity.

.
27/41

28/41

Geometric resolution and multi-homogeneity

Technicalities to get a proven complexity

With the geometric resolution algorithms in the end, thecomplexity of solving the system should be polynomial in

0-dimensional: careful when writing equations; any denominatorclearing must come with the appropriate saturation.
Corresponding non-generic sub-cases must be handledindependently with other polynomial systems.

ndxnx dy y = Og (ℓ2g ).

radicality: comes from the fact that the multiplication by ℓ map
can not involve multiplicities, but care must be taken to ensurethat we did not introduce new multiplicities in our equation.

But for that, we need the input system to be
0-dimensional (need to clean-up any higher dimensional
parasite component);

regular sequence: need to make a random (linear) change of
coordinates and apply a positive characteristic, multi-homogeneous
variant of Bertini’s theorem.

radical (no multiple roots);a regular sequence (each equation cuts cleanly the previousones).

degrees: Cantor’s paper on division polynomials does not provide
all the degree bounds we need.

Rem. The first system you write to describe an algebraic situation isnever like this.

30/41

29/41

Main result

Plan

Thm. There is a probabilistic algorithm that given a hyperelliptic
curve of genus g over a finite field Fq computes its local Zeta
function in expected time Og ((log q)O(g) ).

Introduction, background(before, the best known complexity was with a quadratic exponent)

Tools for polynomial systems

Schoof’s algorithm

New complexity for large genus
Rem. We do not claim more than a purely theoretical complexity result.
Don’t try to implement it following all the steps of the paper; several
parts deal with things that should almost never occur in practice.

The case of genus 3 with real multiplication

31/41

32/41

Equations for the torsion in genus 3

Two ways of solving the polynomial system

For genus 3, the equation for the torsion becomes ℓD = 0 ⇔In theory, with resultants:
The number of variables is low (essentially 3, because the yi
do not count);éu1 (X ), v1 (X )ê + éu2 (X ), v2 (X )ê + éu3 (X ), v3 (X )ê = 0,
where

ui (X ) = δℓAxi − X
4yi2

B, vi (X ) = εℓAxi − X
4yi2

B

The intermediate degrees do not grow too much compared tothe degree of Iℓ ;.

Complexity ends-up being quasi-quadratic in deg Iℓ , which is
better than the other approaches.

Here, the indeterminates are (x1 , y1 ), (x2 , y2 ), (x3 , y3 ).
We apply the group law once, between the first two divisors andgetéu12 (X ), v12 (X )ê = −éu3 (X ), v3 (X )ê.

In practice, with F4:
The F4 algorithm behaves surprisingly well on these systems;
Absolutely no hope to prove this;Now, u12 and v12 ’s coefficients depend on x1 , y1 , x2 , y2 , (and we
use the symmetries).

Many unexpected degree falls during the computation
Rem. Experiments with F4 done with Magma and tinyGB. For
resultants, time estimates based on FLINT and NTL.

Rem. Computing this input system can be done by working in theappropriate function field and takes no time compared to solving it.
33/41

34/41

Results for genus 3 curves (without RM)

Real multiplication (RM)
G.-Kohel-Smith (2011): In genus 2, the complexity drops fromÕ((log q)8 ) to Õ((log q)5 ), if an explicit real endormorphism isknown.
Let’s follow this path in genus 3

Complexity result:Thm. Point counting for genus 3 hyperelliptic curves over afinite field Fq can be done in time Õ((log q)14 ).
Practical result: Experiments for a curve of genus 3, over Fp ,with a 64-bit prime p, and ℓ = 3.
All things put together, we get a system with

RM curves considered by Tautz, Top, and Verberkmoes (1991):
Ct : y 2 = x 7 − 7x 5 + 14x 3 − 7x + t, (t Ó= ±2)

5 variables;

Explicit RM endomorphism on JacCt (Kohel, Smith 2006):

5 equations of degrees 7, 53, 54, 55, 26.

η7 (x , y ) = éX 2 + 11 xX /2 + x 2 − 16/9, y ê,

The system can be solved (with F4, in Magma) in
14 days;

and we have

140 GB of RAM.

η73 + η72 − 2η7 − 1 = 0,

The next prime ℓ = 5 is already out of reach !

so that Z[η7 ] ∼= Z[2 cos(2π/7)] ⊂ End(JacCt ).
35/41

36/41

Explicit RM kernel

Results for genus 3 with RM
Complexity result:

Let ℓ = be a split prime in Z[η7 ], for instanceThm. Point counting for genus 3 hyperelliptic curves overa finite field Fq with an explicit real multiplication endomorphism can be done in time Õ((log q)6 ).

(13) = (2 − η7 − 2η72 ) (−2 + 2η7 + η72 ) (3 + η7 − η72 ).
Then the kernel JacCt [13] decomposes as a direct sum of thekernels of these 3 endomorphisms of degree ℓ2 .

Practical result: Experiments for Ct , with t = 42 over Fp , with
p = 264 − 59:

The same strategy as before will work, in theory with resultants,
and in practice with F4.

Modular information obtained:
mod ℓk#var degree of each eq.
2——
4 (inert2 )6
7, 7, 14, 15, 15, 10
3 (inert)
5
7, 53, 54, 55, 26
13 = p1 p2 p3
57, 44, 45, 46, 52
3
7 = p1
5
7, 35, 36, 37, 36
29 = p1 p2 p3
57, 92, 93, 94, 100

E.g. for ℓ = 13, we have to solve three systems with
5 variables,
5 equations of degrees 7, 44, 45, 46, 52.
Each of them is smaller than what we had for ℓ = 3.

time
—
1 min
14 days3 × 3 days
3.5h

memory—negl.
140 GB
41 GB
6.6 GB> 3×2 weeks> 0.8 TB

37/41

Practical results for genus 3 with RM (con’t)

38/41

Conclusion

For ℓ = 29, we failed to find the torsion (note that over a small
finite field, the GB computation finished).
For ℓ = 7, only partial information was obtained but not used.
But we got χC (T ) mod 3 × 4 × 13 = 156.

New complexity bounds:
Arbitrary genus: Og ((log q)O(g) ) (previous exponent wasquadratic);
Genus 3: Õ((log q)14 ) in general
Genus 3: Õ((log q)6 ) with explicit RM

Final parallel collision search:
We used the low-memory variant (G., Schost, 2004) of thealgorithm by Matsuo, Chao and Tsujii (2002).
The complexity is O(p 3/4 /m3/2 ), where m = 156 is the known
modular information.

See also recent result by Abelard, for arbitray genus with RM.
Take-home message about polynomial systems:
No tool is perfect in all situations;

Here: 190,000 3d pseudo-random walks of average length
32,000,000 led to a useful collision, in about 105 days (done inparallel in a few hours).

Proving (good) complexity bounds can be really, really hard;
Look for multi-homogeneity in your favorite systems.

39/41

40/41

Our genus 3 RM curve
The curve C42 of equationy 2 = x 7 − 7x 5 + 14x 3 − 7x + 42
over Fp with p = 264 − 59 has characteristic polynomial
χ(T ) = T 6 − σ1 T 5 + σ2 T 4 − σ3 T 3 + pσ2 T 2 − p 2 σ1 T + p 3 ,with

σ1 = 986268198,
σ2 = 35389772484832465583,
σ3 = 10956052862104236818770212244.

41/41