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