1package fptower 2 3// Expt set z to x^t in E12 and return z 4func (z *E12) Expt(x *E12) *E12 { 5 // const tAbsVal uint64 = 9586122913090633729 6 // tAbsVal in binary: 1000010100001000110000000000000000000000000000000000000000000001 7 // drop the low 46 bits (all 0 except the least significant bit): 100001010000100011 = 136227 8 // Shortest addition chains can be found at https://wwwhomes.uni-bielefeld.de/achim/addition_chain.html 9 10 var result, x33 E12 11 12 // a shortest addition chain for 136227 13 result.Set(x) // 0 1 14 result.CyclotomicSquare(&result) // 1( 0) 2 15 result.CyclotomicSquare(&result) // 2( 1) 4 16 result.CyclotomicSquare(&result) // 3( 2) 8 17 result.CyclotomicSquare(&result) // 4( 3) 16 18 result.CyclotomicSquare(&result) // 5( 4) 32 19 result.Mul(&result, x) // 6( 5, 0) 33 20 x33.Set(&result) // save x33 for step 14 21 result.CyclotomicSquare(&result) // 7( 6) 66 22 result.CyclotomicSquare(&result) // 8( 7) 132 23 result.CyclotomicSquare(&result) // 9( 8) 264 24 result.CyclotomicSquare(&result) // 10( 9) 528 25 result.CyclotomicSquare(&result) // 11(10) 1056 26 result.CyclotomicSquare(&result) // 12(11) 2112 27 result.CyclotomicSquare(&result) // 13(12) 4224 28 result.Mul(&result, &x33) // 14(13, 6) 4257 29 result.CyclotomicSquare(&result) // 15(14) 8514 30 result.CyclotomicSquare(&result) // 16(15) 17028 31 result.CyclotomicSquare(&result) // 17(16) 34056 32 result.CyclotomicSquare(&result) // 18(17) 68112 33 result.Mul(&result, x) // 19(18, 0) 68113 34 result.CyclotomicSquare(&result) // 20(19) 136226 35 result.Mul(&result, x) // 21(20, 0) 136227 36 37 // the remaining 46 bits 38 for i := 0; i < 46; i++ { 39 result.CyclotomicSquare(&result) 40 } 41 result.Mul(&result, x) 42 43 z.Set(&result) 44 return z 45} 46 47// MulByVW set z to x*(y*v*w) and return z 48// here y*v*w means the E12 element with C1.B1=y and all other components 0 49func (z *E12) MulByVW(x *E12, y *E2) *E12 { 50 51 var result E12 52 var yNR E2 53 54 yNR.MulByNonResidue(y) 55 result.C0.B0.Mul(&x.C1.B1, &yNR) 56 result.C0.B1.Mul(&x.C1.B2, &yNR) 57 result.C0.B2.Mul(&x.C1.B0, y) 58 result.C1.B0.Mul(&x.C0.B2, &yNR) 59 result.C1.B1.Mul(&x.C0.B0, y) 60 result.C1.B2.Mul(&x.C0.B1, y) 61 z.Set(&result) 62 return z 63} 64 65// MulByV set z to x*(y*v) and return z 66// here y*v means the E12 element with C0.B1=y and all other components 0 67func (z *E12) MulByV(x *E12, y *E2) *E12 { 68 69 var result E12 70 var yNR E2 71 72 yNR.MulByNonResidue(y) 73 result.C0.B0.Mul(&x.C0.B2, &yNR) 74 result.C0.B1.Mul(&x.C0.B0, y) 75 result.C0.B2.Mul(&x.C0.B1, y) 76 result.C1.B0.Mul(&x.C1.B2, &yNR) 77 result.C1.B1.Mul(&x.C1.B0, y) 78 result.C1.B2.Mul(&x.C1.B1, y) 79 z.Set(&result) 80 return z 81} 82 83// MulByV2W set z to x*(y*v^2*w) and return z 84// here y*v^2*w means the E12 element with C1.B2=y and all other components 0 85func (z *E12) MulByV2W(x *E12, y *E2) *E12 { 86 87 var result E12 88 var yNR E2 89 90 yNR.MulByNonResidue(y) 91 result.C0.B0.Mul(&x.C1.B0, &yNR) 92 result.C0.B1.Mul(&x.C1.B1, &yNR) 93 result.C0.B2.Mul(&x.C1.B2, &yNR) 94 result.C1.B0.Mul(&x.C0.B1, &yNR) 95 result.C1.B1.Mul(&x.C0.B2, &yNR) 96 result.C1.B2.Mul(&x.C0.B0, y) 97 z.Set(&result) 98 return z 99} 100 101// MulBy034 multiplication by sparse element 102func (z *E12) MulBy034(c0, c3, c4 *E2) *E12 { 103 104 var z0, z1, z2, z3, z4, z5, tmp1, tmp2 E2 105 var t [12]E2 106 107 z0 = z.C0.B0 108 z1 = z.C0.B1 109 z2 = z.C0.B2 110 z3 = z.C1.B0 111 z4 = z.C1.B1 112 z5 = z.C1.B2 113 114 tmp1.MulByNonResidue(c3) 115 tmp2.MulByNonResidue(c4) 116 117 t[0].Mul(&tmp1, &z5) 118 t[1].Mul(&tmp2, &z4) 119 t[2].Mul(c3, &z3) 120 t[3].Mul(&tmp2, &z5) 121 t[4].Mul(c3, &z4) 122 t[5].Mul(c4, &z3) 123 t[6].Mul(c3, &z0) 124 t[7].Mul(&tmp2, &z2) 125 t[8].Mul(c3, &z1) 126 t[9].Mul(c4, &z0) 127 t[10].Mul(c3, &z2) 128 t[11].Mul(c4, &z1) 129 130 z.C0.B0.Mul(c0, &z0). 131 Add(&z.C0.B0, &t[0]). 132 Add(&z.C0.B0, &t[1]) 133 z.C0.B1.Mul(c0, &z1). 134 Add(&z.C0.B1, &t[2]). 135 Add(&z.C0.B1, &t[3]) 136 z.C0.B2.Mul(c0, &z2). 137 Add(&z.C0.B2, &t[4]). 138 Add(&z.C0.B2, &t[5]) 139 z.C1.B0.Mul(c0, &z3). 140 Add(&z.C1.B0, &t[6]). 141 Add(&z.C1.B0, &t[7]) 142 z.C1.B1.Mul(c0, &z4). 143 Add(&z.C1.B1, &t[8]). 144 Add(&z.C1.B1, &t[9]) 145 z.C1.B2.Mul(c0, &z5). 146 Add(&z.C1.B2, &t[10]). 147 Add(&z.C1.B2, &t[11]) 148 149 return z 150} 151