accessibility 101 Useful Trace Zero Varieties

The table below lists genus 2 hyperelliptic curves defined over F_p where p is the Mersenne prime 2⁶¹-1. These curves are distinguished by the fact that #J_3/1(C) is prime (244 bits) and #J₂(C) is not divisible by 3 (see definitions and notation). The row for each curve contains the coefficients a and b of the L-polynomial P(z) = p²z⁴ + apz³+ bz²+ az + 1.
The fact that #J₂(C)=P(1)P(-1) is not divisible by 3 ensures that J(C) has trivial 3-torsion, so J_3/1(C) is in fact equal to the trace zero variety over F_p³ for each of the curves listed. The order of the trace zero variety may be computed explicitly via #J_3/1(C) = P(ω)P(ω²) = p⁴ - p³a + p²(a²+2a - b - 1) - p(a²+ab - 2a) + a²+b² - ab - a - b+1.
The Frobenius endomorphism &phi_p can be used to speed up scalar multiplication in the trace zero variety. For the trace zero variety of a genus 2 curve over F_p³ with #J_3/1(C) prime, the Frobenius map is equivalent to scalar multiplication by s = - (p² - b+a) / (ap - b+1) mod #J_3/1(C). Note that s necessarily satisfies s² + s + 1 = 0 mod #J_3/1(C) (the other solution is s², corresponding to the map (&phi_p)²). To perform scalar multiplication by n, one writes n = sn₁ + n₂ with n₁ and n₂ each containing roughly half the bits of #J_3/1(C). The GLV algorithm can be used to find n₁ and n₂. See sections 15.2 and 15.3 of the Handbook of Elliptic and Hyperelliptic Curve Cryptography for details.

The Mersenne prime p=2⁶¹-1 allows the finite field arithmetic in F_p³ to be heavily optimized (particularly on 64-bit architectures) and small curve coefficients enable further improvements. The security of the trace zero variety for each of the curves listed below is comparable to a 204-bit prime-order genus 2 Jacobian over a prime field. With the optimizations mentioned, the group operation in the trace zero varieties of the curves below will typically be substantially faster than the group operation in a comparable Jacobian. More information about computation in trace zero varieties may be found in Tanja Lange's paper Trace Zero Subvariety for Cryptosystems.

The L-polynomial coefficients for each of these curves was obtained via the algorithm described in A Generic Approach to Searching for Jacobians.

Curve	a	b
y2 = x5 + 1x3 + 5x2 + 24x + 15	-633985176	3688227127843326974
y2 = x5 + 1x3 - 22x2 + 2x - 6	-3455871436	6015560809562439892
y2 = x5 - 1x3 + 10x2 + 1x - 9	-603607940	3119086433192129134
y2 = x5 - 1x3 - 15x2 + 21x + 4	692948374	3391785687916638646
y2 = x5 - 1x3 - 17x2 + 24x + 27	-827881836	3669243749472297882
y2 = x5 + 2x3 - 15x2 - 17x + 28	1664900430	3903268197891864350
y2 = x5 + 2x3 - 18x2 - 10x - 1	580207872	2904435708332601516
y2 = x5 - 2x3 + 2x2 + 3x + 8	56761627	1066085003088636607
y2 = x5 - 2x3 + 11x2 + 2x - 1	1579765422	1113533573831578370
y2 = x5 - 2x3 - 17x2 - 7x - 4	-783908102	3694520425325002186
y2 = x5 + 3x3 - 17x2 - 21x + 18	1169914002	3286573584919315994
y2 = x5 + 3x3 - 20x2 - 19x - 8	2404414810	3140306862713679784
y2 = x5 - 3x3 + 3x2 + 2x - 9	1390354391	4247176971238898671
y2 = x5 - 3x3 + 18x2 - 2x + 23	-23315184	468940901610261086
y2 = x5 - 3x3 - 20x2 + 25x - 9	-808195785	1144606523576656097
y2 = x5 + 4x3 + 24x2 - 24x - 23	482385862	611350750063816042
y2 = x5 + 5x3 + 11x2 - 1x - 3	1179478246	3144941922522754486
y2 = x5 - 5x3 - 2x2 + 6x - 21	2456714864	5058337296276459694
y2 = x5 - 5x3 - 15x2 + 1x - 21	-4482605420	9385391019386172088
y2 = x5 + 5x3 - 19x2 - 21x - 7	-932518377	851882762326511823
y2 = x5 + 6x3 + 19x2 - 18x + 6	900270087	1681409594599723479
y2 = x5 - 6x3 + 4x2 - 5x + 4	-567062434	-1541505880631351906
y2 = x5 - 6x3 + 14x2 + 9x - 15	2629949528	5990334030731387008
y2 = x5 + 7x3 - 26x2 + 15x + 23	-98028556	1990982977778348698
y2 = x5 + 7x3 + 3x2 - 25x + 14	-1158492786	3206276227367326238
y2 = x5 + 7x3 + 5x2 - 26x - 12	-616588972	3358090349682525358
y2 = x5 + 7x3 - 5x2 + 22x + 4	2750340466	4882148079490761214
y2 = x5 - 7x3 + 9x2 - 11x - 13	-845113758	3522271499650203042
y2 = x5 - 7x3 + 15x2 - 11x - 28	930368788	2667992027582084158
y2 = x5 - 7x3 - 13x2 - 2x + 22	3690449840	7947307838813563534
y2 = x5 + 8x3 - 4x2 - 28x - 13	-1796648768	4339098899120320792
y2 = x5 - 8x3 - 3x2 - 15x - 20	-849773518	1772469534127689832
y2 = x5 - 8x3 - 25x2 + 7x - 17	3436447875	6676919608247713145
y2 = x5 - 8x3 - 27x2 - 8x + 21	3245416754	5710539433590617902
y2 = x5 + 9x3 - 28x2 - 15x + 16	470738209	-2032246687489909031
y2 = x5 + 10x3 + 9x2 + 4x + 2	2533554792	5456432672250638402
y2 = x5 + 10x3 - 15x2 + 12x - 28	2277451860	5101487784894160062
y2 = x5 - 10x3 - 4x2 - 11x	-305401294	-2372382383725854722
y2 = x5 + 11x3 + 4x2 - 1x + 16	74893956	-1309411197053636586
y2 = x5 + 11x3 - 4x2 - 13x + 11	-2351502450	2615096594254747898
y2 = x5 + 11x3 + 10x2 + 18x - 26	-396657224	-940915150439885054
y2 = x5 + 11x3 + 17x2 - 22x - 24	381690399	-1215182247642932431
y2 = x5 - 11x3 + 23x2 - 2x - 15	2206929152	2959564477607794972
y2 = x5 - 11x3 - 5x2 - 6x - 14	-432897840	2134651233297053940
y2 = x5 + 12x3 - 3x2 + 12x + 9	-701520086	2056688788182909436
y2 = x5 + 12x3 - 19x2 - 19x + 5	3078455123	5813400134878057327
y2 = x5 - 12x3 - 4x2 + 5x + 1	-1864478109	5109465719683973865
y2 = x5 + 13x3 - 1x2 + 9x - 26	-33525821	-1729086428147166791
y2 = x5 + 13x3 - 9x2 + 23x + 16	-1173353918	3007199206682770384
y2 = x5 - 13x3 + 25x2 - 13x - 19	1363321840	2188490801565741934
y2 = x5 - 13x3 - 17x2 + 1x - 16	642110751	-183552762946739601
y2 = x5 + 14x3 + 27x2 - 27x - 21	914707020	551766793069606850
y2 = x5 - 14x3 + 4x2 + 20x - 1	-98795804	-985099148312324324
y2 = x5 - 15x3 + 5x2 - 23x + 5	-27059807	-314827906522042397
y2 = x5 - 15x3 + 28x2 + 19x - 17	-1072585698	-428492544151609566
y2 = x5 - 15x3 - 6x2 + 20x - 2	-249775336	3849452185264303546
y2 = x5 + 16x3 + 22x2 + 3x - 21	592217632	2567070424203236500
y2 = x5 + 16x3 - 20x2 + 8x + 28	-1801446218	1574662304984426302
y2 = x5 - 16x3 + 9x2 - 24x + 1	3510652158	7368826912628223726
y2 = x5 - 16x3 - 17x2 - 21x + 6	-621930718	3298354539821558242
y2 = x5 - 16x3 - 23x2 - 22x - 20	-1541147760	1431217692155145594
y2 = x5 + 17x3 + 16x2 + 15x + 11	2007233626	2982319287299445790
y2 = x5 - 17x3 + 6x2 - 13x	1224376836	4655138469229100574
y2 = x5 - 17x3 - 26x2 - 9x - 27	339616452	3076718597076694062
y2 = x5 + 18x3 + 3x2 - 23x + 12	2137687158	2493220815705185462
y2 = x5 + 18x3 + 14x2 - 17x + 18	1324412998	793445505796501966
y2 = x5 - 18x3 - 2x2 - 22x - 3	-1293438120	2172651771060601118
y2 = x5 - 18x3 - 15x2 - 10x	-895220046	1774618546323243966
y2 = x5 + 19x3 + 14x2 + 26x - 20	-1965549695	4800496999366770547
y2 = x5 + 19x3 + 17x2 + 17x - 7	-210735141	-3271823812187761051
y2 = x5 - 19x3 - 4x2 - 16x + 11	-75171972	3917253588445025412
y2 = x5 - 19x3 - 18x2 + 16x + 15	-266877028	-1553758697746851800
y2 = x5 + 20x3 + 13x2 - 5x + 13	436461295	-540675751729963277
y2 = x5 + 20x3 - 25x2 - 15x - 20	3255366850	5318534650696233310
y2 = x5 + 21x3 + 21x2 - 20x + 25	2116971957	4315505636217448811
y2 = x5 + 22x3 - 15x2 + 1x + 20	2164071190	4083816709505548120
y2 = x5 + 22x3 - 18x2 - 8x + 6	768757254	-1137469015675261924
y2 = x5 + 22x3 - 24x2 + 25x - 8	695888808	880832459365115022
y2 = x5 - 22x3 - 23x2 + 9x - 16	2302789104	4832241579123663798
y2 = x5 + 23x3 - 2x2 + 28x + 27	-257860086	-440908668286911444
y2 = x5 - 23x3 - 14x2 - 7x + 27	251927752	291143438228329342
y2 = x5 + 24x3 + 1x2 + 9x - 11	-2123865591	4424876728228825509
y2 = x5 + 24x3 - 21x2 + 13x + 19	489277074	-2271960452432220498
y2 = x5 - 24x3 + 15x2 - 15x - 5	1329183736	564449411897756590
y2 = x5 + 25x3 + 10x2 + 1	327983190	2689272028134703454
y2 = x5 - 25x3 + 10x2 + 9x + 1	189085476	-3451553343006962034
y2 = x5 - 25x2 + 26x - 15	2029510623	2970839189236333007
y2 = x5 - 25x3 + 7x2 - 25x + 5	-23675380	2136047225215150360
y2 = x5 - 25x3 - 23x2 + 8x + 21	568697929	2811214889515792669
y2 = x5 - 25x3 - 26x2 - 4x + 11	1928975007	2562893415122471129
y2 = x5 - 25x3 - 26x2 - 25	1580823100	3206638507330568404
y2 = x5 + 26x3 + 10x2 - 14x - 7	1009520664	1496162328907836672
y2 = x5 + 26x3 + 26x2 + 13x + 23	-2430731262	5869373480107023620
y2 = x5 + 26x3 - 6x2 + 27x + 25	-1233956092	2868391691634812572
y2 = x5 + 26x3 - 8x2 + 18x	-853539712	1129749128766422758
y2 = x5 + 26x3 - 17x2 - 4x + 2	-280701996	1969848772246486686
y2 = x5 + 27x3 + 3x2 + 13x - 10	-773991615	2316571477561295133
y2 = x5 + 27x3 - 15x2 - 12x + 5	-2111010546	3635357409246105054
y2 = x5 + 27x2 - 28x + 16	-896106114	2265682764738438686
y2 = x5 - 27x3 - 26x2 + 16x - 13	1703153682	765082804759396160