# Hyperelliptic curve point counting record: 254 bit Jacobian

### Pierrick Gaudry and Éric Schost

#### June 2008

Thanks to Dan Bernstein and Nikki Pitcher for their suggestions.

### Curve data

Let p=2^127-1 and C the genus 2 curve over GF(p) defined by

y^2 = 31375376347971734085670496609836615726 + 27953605038214221253645981475511570657 x + 62420003626849852428332554437765277161 x^2 + 88005954939527387244239849284058473679 x^3 + 155062477294917469622604436777931982527 x^4 + x^5

The characteristic polynomial of its Frobenius endomorphism is

Z(T) = T^4 - s1 T^3 + s2 T^2 - p s1 T + p^2

with

s1 = -15671660075779706640 and s2 = 86154286096042006774781271889300357630

Thus the number of points on the Jacobian of C and on its twist are

N = 28948022309329048858559141044255323173240361153110759925351350586742398190080

Nt = 28948022309329048853226351460088630752886375018059729181000254746129230922240

This curve has been more or less randomly chosen, according to the following requisites:
• The Kummer surface associated to C is rational, when using the Theta-coordinates of [Gaudry07]. The corresponding parameters are

a = 70749273537019715197487696660857318100

b = 13297111293698997518530805629493053456

c = 31962724788629373720348362255515893454

d = 39961846205204383608694313460795530917

This implies, in particular that the group order of the Jacobian is divisible by 16. On the other hand, this allows fast arithmetic (see also Bernstein's ECC talk).
• The prime p=2^127-1 is chosen so that the finite field arithmetic is facilitated. This was not used in this record-computation, but would make sense for using the curve in cryptography.
• The curve C was selected among half a dozen of curves, so that the divisions by 2,3,5,7 algorithms were facilitated. This bias should be removed for proper cryptographic curve construction.

### Previous records

• Previous record was held by Sutherland: in 2007, he computed some 188-bit genus 2 Jacobian over a prime field. Note that this is not exactly point counting, since only a curve whose quadratic twist has a Jacobian with a smooth order can be counted with his method.
• The previous record was held by Gaudry and Schost: in 2004, they computed genus 2 Jacobians of 164 bits, over a prime field with p=5*10^24+8503491 ~ 2^82.
• Previously, the record was held by Gaudry and Harley: in 2000, they computed genus 2 Jacobians of 126 bits, over a prime field with p=10^19+51 ~ 2^63.

### Algorithm used

The algorithm used is a collection of variants and generalizations of Schoof's algorithm for genus 2. The characteristic polynomial is computed modulo several primes or prime powers. This modular information is collected using the Chinese Remainder Theorem. Once the missing part is small enough, a generic «square-root» algorithm is used. Most of these algorithms are based on the work on 2004 with several improvements in almost every place. Everything is implemented in C++, using the NTL and the GMP libraries.
##### Powers of 2
Elements of 2^k-torsion are computed using a novel algorithm, that makes use of the Kummer surface parametrization. This simplifies a bit the lifting. We no longer use a general purpose Gröbner basis implementation.
##### Powers of 3
Elements of 3^k-torsion are computed using a novel algorithm. At each step, the algebraic system that has to be inverted is solved using deformation techniques and Newton lifting of power series. Again, we no longer use a general purpose Gröbner basis implementation.
##### Powers of 5, 7
Elements of 5^k- and 7^k-torsion are computed. At each step, the algebraic system that has to be inverted is solved using resultant computations.
##### Other primes
Computations modulo primes have been enhanced; now it proceeds as follows. First the full, exact, l-torsion ideal is computed. The "refining of resultant" step has been modified to save time and space, allowing larger torsions to be computed. Thereafter, the Frobenius equation is tested against the full ideal, without trying to factor it. The theoretical complexity is better, and this is also better in practice for current sizes.
For the record computation, we did more modular computation than needed, so that the 2-dimensional version of the algorithm was not used. The classical "kangaroo" algorithm was used.

### Timings

All times are in seconds on a single CPU of an AMD Opteron 250 at 2.4 GHz. Memory usage peaked around 8GB (the maximun available on our computers).

2^k-torsion
Torsion Degree Halving Schoof Get Z mod
2^5 16 0.19 0.04 2^2
2^6 32 0.25 0.29 2^3
2^7 64 0.7 0.75 2^4
2^8 128 2.0 1.8 2^6
2^9 256 6.5 4.6 2^7
2^10 512 20 12 2^8
2^11 1024 70 30 2^9
2^12 2048 243 71 2^10
2^13 4096 903 168 2^11
2^14 8192 3554 425 2^12
2^15 16384 13329 1026 2^13
2^16 32768 58751 2753 2^14
2^17 65536 257425 9842 2^15

3^k-torsion
Torsion Degree Halving Schoof Get Z mod
3^2 6 543 0.1 3^2
3^3 6 57 0.1 3^3
3^4 18 59 0.2 3^4
3^5 54 265 1 3^5
3^6 162 1330 4 3^6
3^7 486 4905 11 3^7
3^8 1458 22642 44 3^8
3^9 4374 134530 211 3^9

5^k-torsion
Torsion Degree Halving Schoof Get Z mod
5^2 10 1639 0.1 5^2
5^3 50 12334 2 5^3
5^4 250 221740 17 5^4

7^k-torsion
Torsion Degree Halving Schoof Get Z mod
7^2 56 95975 2.7 7^2

Other primes
ell resultants reduction of res Frobeniuses end of Schoof
11974 411 148 45
133173 1174 312 203
1719374 3685 1183 927
1939198 12443 3382 2245
2315077640729 1458112725
296126021349933145637285
318748861784313821344493

Combining this modular information gives s1 exactly, and s2 was recovered using kangaroos in about 2 hours.
It is to be noted that computing so much modular information is far from optimal: putting more pressure on the square-root part would save some time. These timing tables are also benches for better tuning in next computations.
A conclusion of these experiments is that counting one curve over GF(2^127-1) can be done in about one CPU-month.

### Future computations

##### Secure Kummer surface of 254 bits
This new record computation is the beginning of a search for a secure Kummer surface over GF(2^127-1), possibly having small coefficients, so that the pseudo-group law gets as fast as possible. We also require both Jacobians of C and of its twist to have an order that is 16 times a prime.
##### Larger record
With our current software, and a computer with 32 GB of RAM, we expect to be able to count points of a Jacobian with about 330 bits.

### Thanks

• INRIA for invitation of É. Schost in Spring 2008
• LORIA for invitation of D. J. Bernstein in Fall 2007
• SHARCNET for providing computer resources
• NSERC and the Canada Research Chair Program for funding.
... and a few logos: