Gallery of Jacobians

This page lists zeta functions of various genus 2 and genus 3 hyperelliptic curves with cryptographically interesting Jacobians or trace zero varieties. Before starting the tour, you may want to check out the page of definitions and notation.

Most of the curves in our gallery have small coefficients and are defined over fields Fp where p is a prime of the form 2n-k (near Mersenne). Such curves are convenient to work with (and to type into a web-page). The algorithm used to find all the curves listed here is generic and does not depend on either the coefficients or the particular finite field used (we have some random examples in our collection as well).

Questions, commments, and corrections are welcomed at drew@math.mit.edu.

Exhibit 1a: y2 = x5 + 3x3 + x2 + 4x + 18996, p = 294-3

Our first example is also our most recent addition. This genus 2 curve has L-polynomial P(z) = p2z4 + apz3+ bz2+ az + 1 with coefficients

a = -117945679626530, and b = -3217880959839060804507909012.

The order of the Jacobian is the 188-bit value
#J(C)= P(1) = 2 &sdot 5 &sdot 11 &sdot 3566535076924229196226077384633029743859037115938187019.

The 182-bit prime factor is the largest in our collection of genus 2 Jacobians over prime fields (its binary logarithm is 181.2186..., I call it a 182-bit number for the same reason I call 23 a 2-digit number).

To verify this result, one may use Magma, Sage, or any system that implements the Jacobian group operation for genus 2 hyperelliptic curves. For near-prime Jacobian orders N=cp', it suffices to find an element &alpha in J(C) for which &alphaN is the identity, but &alphac is not. This will be true of almost every element in the group, so a random &alpha suffices. This test demonstrates that p' is a divisor of #J(C). For large p', there is exactly one multiuple of p' in the Weil interval, namely N, which must be #J(C).

This proves the value #J(C) is correct, but is not sufficient to verify the zeta function. One can additionally check that P(-1) = #J(C'), where C' is the quadratic twist, and/or test the values of #Jk(C) given by summing P(z) over the kth roots of unity. The attached Magma transcript demonstrates this for the curve above.

Exhibit 1b: y2 = x5 + 3x3 + x2 + 4x + 53012, p = 294-3

Another curve in the same family, also with a near-prime order Jacobian. The L-polynomial coefficients are

a = -54515123760731, and b = 12528167413341542169377728364.

The Jacobian is a cyclic group of order
#J(C)= P(1) = 22 &sdot 3 &sdot 41 &sdot 797396053783874934870865119384016379165197709928371377.

The large prime factor contains just over 179 bits.

Exhibit 2: y2 = x5 + x + 202214, p = 289-1

This curve was formerly our genus 2 champion over a prime field. The mersenne prime and sparse coefficients make it particularly convenient to work with. The L-polynomial coefficients are

a = -52033004229306, and b = 1618004552234213280766854490.

The order of the Jacobian is the 178-bit value
#J(C)= P(1) = 22 &sdot 32 &sdot 5 &sdot 2128466028980222265110760419187916380742710181533203.

This is a cyclic group. The large prime factor contains 171 bits.

Exhibit 3: y2 = x7 + 3x5 + x4 + 4x3 + x2 + 5x + 84538, p = 261-1

This is a genus 3 curve. Its L-polynomial has the form

P(z) = p3z6 + p2az5 + bpz4+ cz3+ bz2 + cz + 1

with coefficients
a = -255251897, b = 3731171990845206887, and c = -1915761422452218541377951998.

The order of the Jacobian is the 183-bit value
#J(C)= P(1) = 24 &sdot 35 &sdot 17, &sdot 223, &sdot 831781325652289358544190241299568732364985371373.

The Jacobian is not a cyclic, rather it is the product of two cyclic groups of order 2 and a cyclic group of order #J(C)/4 (the 2-rank is three, the 3-rank is one). The 160-bit prime factor is the largest in our collection of genus 3 Jacobians over prime fields.

Exhibit 4: y2 = x7 + 3x5 + x4 + 4x3 + x2 + 5x + 851385, p = 250-27

The L-polynomial of this genus 3 curve has coefficients

a = 13792821, b = 98748931364073, and c = -4912096020329124903571.

The order of the Jacobian is the 150-bit prime
#J(C)= P(1) = 1427247710190335132030763894493884791800228867.

Exhibit 5: x5 + x + 89993 , p = 284-35

This is a genus 2 curve with a trace zero variety of prime order. The L-polynomial coefficients are

a = 1236014582768 and b = -20956811918028115290034218.

The trace zero variety over Fp3 has 336-bit prime order
#J3/1(C)= P(&omega)P(&omega2) = 139984046386103818115409981742174673753855195736794442216213581973640756902748686925716193577915785969.

Here &omega is a principle cube-root of unity. Since #J(C)=P(1) is not divisible by 3, J3/1 is equal to the trace zero variety T3(C). It is also the case that #J2(C)=P(1)P(-1) is not divisible by 3, hence the security of this group is comparable to a 280-bit genus 2 Jacobian of prime order over a 140-bit prime field.

Exhibit 6a: x5 + x + 456579 , p = 261-1

The Mersenne prime p = 261-1 fits conveniently in a 64-bit word, enabling very fast group operations on a 64-bit platform. This curve was found during a scan of curves of the form x5 + x + t. The coefficients of P(z) are

a = 867588246, and b = 503655589160075568.

This curve has the distinction that #J3/1(C) and #J3/1(C') are both 244-bit primes:

#J3/1(C)= P(&omega)P(&omega2) = 28269553025817548279195837042471298247386056982207401577306735450612452941;
#J3/1(C') = P(-&omega)P(-&omega2) = 28269553047090750172038362372022515086539951853784072981017351137960545869.

Since #J(C)=P(1) and #J(C')=P(-1) are not divisible by 3, the two groups J3/1(C) and J3/1(C') are equal to the trace zero varieties of C and C' over Fp3. This also means that J2(C) is not divisible by 3. The security of each of these two groups is comparable to a 204-bit genus 2 Jacobian over a prime field.

Exhibit 6b: x5 + 2050668744648879665x3 + 1948613779828075789x2 + 777475836699358935x + 1981141960889113537 , p = 261-1

This is a similar example with random coefficients. The coefficients of the L-polynomial are

a = -602512302, and b = -1028770098952312018.

Like the curve above, the trace zero varieties of both C and C' over Fp3 have 244-bit prime order:

#J3/1(C)= P(&omega)P(&omega2) = 28269553043840928560747668007160867056404510432183682585252421999447057589;
#J3/1(C') = P(-&omega)P(-&omega2) = 28269553029067369902638199732844220195228941160055850838090599652158940341.

As above, neither P(1) nor P(-1) are divisible by 3.