101 Useful Trace Zero Varieties

The table below lists genus 2 hyperelliptic curves defined over Fp where p is the Mersenne prime 261-1. These curves are distinguished by the fact that #J3/1(C) is prime (244 bits) and #J2(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) = p2z4 + apz3+ bz2+ az + 1.

The fact that #J2(C)=P(1)P(-1) is not divisible by 3 ensures that J(C) has trivial 3-torsion, so J3/1(C) is in fact equal to the trace zero variety over Fp3 for each of the curves listed. The order of the trace zero variety may be computed explicitly via
#J3/1(C) = P(&omega)P(&omega2) = p4 - p3a + p2(a2+2a - b - 1) - p(a2+ab - 2a) + a2+b2 - ab - a - b+1.

The Frobenius endomorphism &phip can be used to speed up scalar multiplication in the trace zero variety. For the trace zero variety of a genus 2 curve over Fp3 with #J3/1(C) prime, the Frobenius map is equivalent to scalar multiplication by
s = - (p2 - b+a) / (ap - b+1) mod #J3/1(C).
Note that s necessarily satisfies s2 + s + 1 = 0 mod #J3/1(C) (the other solution is s2, corresponding to the map (&phip)2). To perform scalar multiplication by n, one writes n = sn1 + n2 with n1 and n2 each containing roughly half the bits of #J3/1(C). The GLV algorithm can be used to find n1 and n2. See sections 15.2 and 15.3 of the Handbook of Elliptic and Hyperelliptic Curve Cryptography for details.

The Mersenne prime p=261-1 allows the finite field arithmetic in Fp3 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.

Curveab
y2 = x5 + 1x3 + 5x2 + 24x + 15-6339851763688227127843326974
y2 = x5 + 1x3 - 22x2 + 2x - 6-34558714366015560809562439892
y2 = x5 - 1x3 + 10x2 + 1x - 9-6036079403119086433192129134
y2 = x5 - 1x3 - 15x2 + 21x + 46929483743391785687916638646
y2 = x5 - 1x3 - 17x2 + 24x + 27-8278818363669243749472297882
y2 = x5 + 2x3 - 15x2 - 17x + 2816649004303903268197891864350
y2 = x5 + 2x3 - 18x2 - 10x - 15802078722904435708332601516
y2 = x5 - 2x3 + 2x2 + 3x + 8567616271066085003088636607
y2 = x5 - 2x3 + 11x2 + 2x - 115797654221113533573831578370
y2 = x5 - 2x3 - 17x2 - 7x - 4-7839081023694520425325002186
y2 = x5 + 3x3 - 17x2 - 21x + 1811699140023286573584919315994
y2 = x5 + 3x3 - 20x2 - 19x - 824044148103140306862713679784
y2 = x5 - 3x3 + 3x2 + 2x - 913903543914247176971238898671
y2 = x5 - 3x3 + 18x2 - 2x + 23-23315184468940901610261086
y2 = x5 - 3x3 - 20x2 + 25x - 9-8081957851144606523576656097
y2 = x5 + 4x3 + 24x2 - 24x - 23482385862611350750063816042
y2 = x5 + 5x3 + 11x2 - 1x - 311794782463144941922522754486
y2 = x5 - 5x3 - 2x2 + 6x - 2124567148645058337296276459694
y2 = x5 - 5x3 - 15x2 + 1x - 21-44826054209385391019386172088
y2 = x5 + 5x3 - 19x2 - 21x - 7-932518377851882762326511823
y2 = x5 + 6x3 + 19x2 - 18x + 69002700871681409594599723479
y2 = x5 - 6x3 + 4x2 - 5x + 4-567062434-1541505880631351906
y2 = x5 - 6x3 + 14x2 + 9x - 1526299495285990334030731387008
y2 = x5 + 7x3 - 26x2 + 15x + 23-980285561990982977778348698
y2 = x5 + 7x3 + 3x2 - 25x + 14-11584927863206276227367326238
y2 = x5 + 7x3 + 5x2 - 26x - 12-6165889723358090349682525358
y2 = x5 + 7x3 - 5x2 + 22x + 427503404664882148079490761214
y2 = x5 - 7x3 + 9x2 - 11x - 13-8451137583522271499650203042
y2 = x5 - 7x3 + 15x2 - 11x - 289303687882667992027582084158
y2 = x5 - 7x3 - 13x2 - 2x + 2236904498407947307838813563534
y2 = x5 + 8x3 - 4x2 - 28x - 13-17966487684339098899120320792
y2 = x5 - 8x3 - 3x2 - 15x - 20-8497735181772469534127689832
y2 = x5 - 8x3 - 25x2 + 7x - 1734364478756676919608247713145
y2 = x5 - 8x3 - 27x2 - 8x + 2132454167545710539433590617902
y2 = x5 + 9x3 - 28x2 - 15x + 16470738209-2032246687489909031
y2 = x5 + 10x3 + 9x2 + 4x + 225335547925456432672250638402
y2 = x5 + 10x3 - 15x2 + 12x - 2822774518605101487784894160062
y2 = x5 - 10x3 - 4x2 - 11x-305401294-2372382383725854722
y2 = x5 + 11x3 + 4x2 - 1x + 1674893956-1309411197053636586
y2 = x5 + 11x3 - 4x2 - 13x + 11-23515024502615096594254747898
y2 = x5 + 11x3 + 10x2 + 18x - 26-396657224-940915150439885054
y2 = x5 + 11x3 + 17x2 - 22x - 24381690399-1215182247642932431
y2 = x5 - 11x3 + 23x2 - 2x - 1522069291522959564477607794972
y2 = x5 - 11x3 - 5x2 - 6x - 14-4328978402134651233297053940
y2 = x5 + 12x3 - 3x2 + 12x + 9-7015200862056688788182909436
y2 = x5 + 12x3 - 19x2 - 19x + 530784551235813400134878057327
y2 = x5 - 12x3 - 4x2 + 5x + 1-18644781095109465719683973865
y2 = x5 + 13x3 - 1x2 + 9x - 26-33525821-1729086428147166791
y2 = x5 + 13x3 - 9x2 + 23x + 16-11733539183007199206682770384
y2 = x5 - 13x3 + 25x2 - 13x - 1913633218402188490801565741934
y2 = x5 - 13x3 - 17x2 + 1x - 16642110751-183552762946739601
y2 = x5 + 14x3 + 27x2 - 27x - 21914707020551766793069606850
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-2497753363849452185264303546
y2 = x5 + 16x3 + 22x2 + 3x - 215922176322567070424203236500
y2 = x5 + 16x3 - 20x2 + 8x + 28-18014462181574662304984426302
y2 = x5 - 16x3 + 9x2 - 24x + 135106521587368826912628223726
y2 = x5 - 16x3 - 17x2 - 21x + 6-6219307183298354539821558242
y2 = x5 - 16x3 - 23x2 - 22x - 20-15411477601431217692155145594
y2 = x5 + 17x3 + 16x2 + 15x + 1120072336262982319287299445790
y2 = x5 - 17x3 + 6x2 - 13x12243768364655138469229100574
y2 = x5 - 17x3 - 26x2 - 9x - 273396164523076718597076694062
y2 = x5 + 18x3 + 3x2 - 23x + 1221376871582493220815705185462
y2 = x5 + 18x3 + 14x2 - 17x + 181324412998793445505796501966
y2 = x5 - 18x3 - 2x2 - 22x - 3-12934381202172651771060601118
y2 = x5 - 18x3 - 15x2 - 10x-8952200461774618546323243966
y2 = x5 + 19x3 + 14x2 + 26x - 20-19655496954800496999366770547
y2 = x5 + 19x3 + 17x2 + 17x - 7-210735141-3271823812187761051
y2 = x5 - 19x3 - 4x2 - 16x + 11-751719723917253588445025412
y2 = x5 - 19x3 - 18x2 + 16x + 15-266877028-1553758697746851800
y2 = x5 + 20x3 + 13x2 - 5x + 13436461295-540675751729963277
y2 = x5 + 20x3 - 25x2 - 15x - 2032553668505318534650696233310
y2 = x5 + 21x3 + 21x2 - 20x + 2521169719574315505636217448811
y2 = x5 + 22x3 - 15x2 + 1x + 2021640711904083816709505548120
y2 = x5 + 22x3 - 18x2 - 8x + 6768757254-1137469015675261924
y2 = x5 + 22x3 - 24x2 + 25x - 8695888808880832459365115022
y2 = x5 - 22x3 - 23x2 + 9x - 1623027891044832241579123663798
y2 = x5 + 23x3 - 2x2 + 28x + 27-257860086-440908668286911444
y2 = x5 - 23x3 - 14x2 - 7x + 27251927752291143438228329342
y2 = x5 + 24x3 + 1x2 + 9x - 11-21238655914424876728228825509
y2 = x5 + 24x3 - 21x2 + 13x + 19489277074-2271960452432220498
y2 = x5 - 24x3 + 15x2 - 15x - 51329183736564449411897756590
y2 = x5 + 25x3 + 10x2 + 13279831902689272028134703454
y2 = x5 - 25x3 + 10x2 + 9x + 1189085476-3451553343006962034
y2 = x5 - 25x2 + 26x - 1520295106232970839189236333007
y2 = x5 - 25x3 + 7x2 - 25x + 5-236753802136047225215150360
y2 = x5 - 25x3 - 23x2 + 8x + 215686979292811214889515792669
y2 = x5 - 25x3 - 26x2 - 4x + 1119289750072562893415122471129
y2 = x5 - 25x3 - 26x2 - 2515808231003206638507330568404
y2 = x5 + 26x3 + 10x2 - 14x - 710095206641496162328907836672
y2 = x5 + 26x3 + 26x2 + 13x + 23-24307312625869373480107023620
y2 = x5 + 26x3 - 6x2 + 27x + 25-12339560922868391691634812572
y2 = x5 + 26x3 - 8x2 + 18x-8535397121129749128766422758
y2 = x5 + 26x3 - 17x2 - 4x + 2-2807019961969848772246486686
y2 = x5 + 27x3 + 3x2 + 13x - 10-7739916152316571477561295133
y2 = x5 + 27x3 - 15x2 - 12x + 5-21110105463635357409246105054
y2 = x5 + 27x2 - 28x + 16-8961061142265682764738438686
y2 = x5 - 27x3 - 26x2 + 16x - 131703153682765082804759396160