Debian Codegraph @

dh/sidh/internal/templates/fp2.gotemp

raw
1 // Code generated by go generate; DO NOT EDIT.
2 // This file was generated by robots.
3
4 package {{.PACKAGE}}
5
6 import (
7 "github.com/cloudflare/circl/dh/sidh/internal/common"
8 )
9
10 // Montgomery multiplication. Input values must be already
11 // in Montgomery domain.
12 func mulP(dest, lhs, rhs *common.Fp) {
13 var ab common.FpX2
14 mul{{.FIELD}}(&ab, lhs, rhs) // = a*b*R*R
15 rdc{{.FIELD}}(dest, &ab) // = a*b*R mod p
16 }
17
18 // Set dest = x^((p-3)/4). If x is square, this is 1/sqrt(x).
19 // Uses variation of sliding-window algorithm from with window size
20 // of 5 and least to most significant bit sliding (left-to-right)
21 // See HAC 14.85 for general description.
22 //
23 // Allowed to overlap x with dest.
24 // All values in Montgomery domains
25 // Set dest = x^(2^k), for k >= 1, by repeated squarings.
26 func p34(dest, x *common.Fp) {
27 var lookup [16]common.Fp
28
29 // This performs sum(powStrategy) + 1 squarings and len(lookup) + len(mulStrategy)
30 // multiplications.
31 powStrategy := {{.P34_POW_STRATEGY}}
32 mulStrategy := {{.P34_MUL_STRATEGY}}
33 initialMul := uint8({{.P34_INITIAL_MUL}})
34
35 // Precompute lookup table of odd multiples of x for window
36 // size k=5.
37 var xx common.Fp
38 mulP(&xx, x, x)
39 lookup[0] = *x
40 for i := 1; i < 16; i++ {
41 mulP(&lookup[i], &lookup[i-1], &xx)
42 }
43
44 // Now lookup = {x, x^3, x^5, ... }
45 // so that lookup[i] = x^{2*i + 1}
46 // so that lookup[k/2] = x^k, for odd k
47 *dest = lookup[initialMul]
48 for i := uint8(0); i < uint8(len(powStrategy)); i++ {
49 mulP(dest, dest, dest)
50 for j := uint8(1); j < powStrategy[i]; j++ {
51 mulP(dest, dest, dest)
52 }
53 mulP(dest, dest, &lookup[mulStrategy[i]])
54 }
55 }
56
57 func add(dest, lhs, rhs *common.Fp2) {
58 add{{.FIELD}}(&dest.A, &lhs.A, &rhs.A)
59 add{{.FIELD}}(&dest.B, &lhs.B, &rhs.B)
60 }
61
62 func sub(dest, lhs, rhs *common.Fp2) {
63 sub{{.FIELD}}(&dest.A, &lhs.A, &rhs.A)
64 sub{{.FIELD}}(&dest.B, &lhs.B, &rhs.B)
65 }
66
67 func mul(dest, lhs, rhs *common.Fp2) {
68 var bMinA, cMinD common.Fp
69 var ac, bd common.FpX2
70 var adPlusBc common.FpX2
71 var acMinBd common.FpX2
72
73 // Let (a,b,c,d) = (lhs.a,lhs.b,rhs.a,rhs.b).
74 //
75 // (a + bi)*(c + di) = (a*c - b*d) + (a*d + b*c)i
76 //
77 // Use Karatsuba's trick: note that
78 //
79 // (b - a)*(c - d) = (b*c + a*d) - a*c - b*d
80 //
81 // so (a*d + b*c) = (b-a)*(c-d) + a*c + b*d.
82 sub{{.FIELD}}(&bMinA, &lhs.B, &lhs.A) // = (b-a)*R
83 sub{{.FIELD}}(&cMinD, &rhs.A, &rhs.B) // = (c-d)*R
84 mul{{.FIELD}}(&ac, &lhs.A, &rhs.A) // = a*c*R*R
85 mul{{.FIELD}}(&bd, &lhs.B, &rhs.B) // = b*d*R*R
86 mul{{.FIELD}}(&adPlusBc, &bMinA, &cMinD) // = (b-a)*(c-d)*R*R
87 adl{{.FIELD}}(&adPlusBc, &adPlusBc, &ac) // = ((b-a)*(c-d) + a*c)*R*R
88 adl{{.FIELD}}(&adPlusBc, &adPlusBc, &bd) // = ((b-a)*(c-d) + a*c + b*d)*R*R
89 rdc{{.FIELD}}(&dest.B, &adPlusBc) // = (a*d + b*c)*R mod p
90 sul{{.FIELD}}(&acMinBd, &ac, &bd) // = (a*c - b*d)*R*R
91 rdc{{.FIELD}}(&dest.A, &acMinBd) // = (a*c - b*d)*R mod p
92 }
93
94 // Set dest = 1/x
95 //
96 // Allowed to overlap dest with x.
97 //
98 // Returns dest to allow chaining operations.
99 func inv(dest, x *common.Fp2) {
100 var e1, e2 common.FpX2
101 var f1, f2 common.Fp
102
103 // We want to compute
104 //
105 // 1 1 (a - bi) (a - bi)
106 // -------- = -------- -------- = -----------
107 // (a + bi) (a + bi) (a - bi) (a^2 + b^2)
108 //
109 // Letting c = 1/(a^2 + b^2), this is
110 //
111 // 1/(a+bi) = a*c - b*ci.
112
113 mul{{.FIELD}}(&e1, &x.A, &x.A) // = a*a*R*R
114 mul{{.FIELD}}(&e2, &x.B, &x.B) // = b*b*R*R
115 adl{{.FIELD}}(&e1, &e1, &e2) // = (a^2 + b^2)*R*R
116 rdc{{.FIELD}}(&f1, &e1) // = (a^2 + b^2)*R mod p
117 // Now f1 = a^2 + b^2
118
119 mulP(&f2, &f1, &f1)
120 p34(&f2, &f2)
121 mulP(&f2, &f2, &f2)
122 mulP(&f2, &f2, &f1)
123
124 mul{{.FIELD}}(&e1, &x.A, &f2)
125 rdc{{.FIELD}}(&dest.A, &e1)
126
127 sub{{.FIELD}}(&f1, &common.Fp{}, &x.B)
128 mul{{.FIELD}}(&e1, &f1, &f2)
129 rdc{{.FIELD}}(&dest.B, &e1)
130 }
131
132 func sqr(dest, x *common.Fp2) {
133 var a2, aPlusB, aMinusB common.Fp
134 var a2MinB2, ab2 common.FpX2
135
136 a := &x.A
137 b := &x.B
138
139 // (a + bi)*(a + bi) = (a^2 - b^2) + 2abi.
140 add{{.FIELD}}(&a2, a, a) // = a*R + a*R = 2*a*R
141 add{{.FIELD}}(&aPlusB, a, b) // = a*R + b*R = (a+b)*R
142 sub{{.FIELD}}(&aMinusB, a, b) // = a*R - b*R = (a-b)*R
143 mul{{.FIELD}}(&a2MinB2, &aPlusB, &aMinusB) // = (a+b)*(a-b)*R*R = (a^2 - b^2)*R*R
144 mul{{.FIELD}}(&ab2, &a2, b) // = 2*a*b*R*R
145 rdc{{.FIELD}}(&dest.A, &a2MinB2) // = (a^2 - b^2)*R mod p
146 rdc{{.FIELD}}(&dest.B, &ab2) // = 2*a*b*R mod p
147 }
148
149 // In case choice == 1, performs following swap in constant time:
150 //
151 // xPx <-> xQx
152 // xPz <-> xQz
153 //
154 // Otherwise returns xPx, xPz, xQx, xQz unchanged
155 func cswap(xPx, xPz, xQx, xQz *common.Fp2, choice uint8) {
156 cswap{{.FIELD}}(&xPx.A, &xQx.A, choice)
157 cswap{{.FIELD}}(&xPx.B, &xQx.B, choice)
158 cswap{{.FIELD}}(&xPz.A, &xQz.A, choice)
159 cswap{{.FIELD}}(&xPz.B, &xQz.B, choice)
160 }
161
162 // In case choice == 1, performs following moves in constant time:
163 //
164 // xPx <- xQx
165 // xPz <- xQz
166 //
167 // Otherwise returns xPx, xPz, xQx, xQz unchanged
168 func cmov(xPx, xPz, xQx, xQz *common.Fp2, choice uint8) {
169 cmov{{.FIELD}}(&xPx.A, &xQx.A, choice)
170 cmov{{.FIELD}}(&xPx.B, &xQx.B, choice)
171 cmov{{.FIELD}}(&xPz.A, &xQz.A, choice)
172 cmov{{.FIELD}}(&xPz.B, &xQz.B, choice)
173 }
174
175 func isZero(x *common.Fp2) uint8 {
176 r64 := uint64(0)
177 for i := 0; i < FpWords; i++ {
178 r64 |= x.A[i] | x.B[i]
179 }
180 r := uint8(0)
181 for i := uint64(0); i < 64; i++ {
182 r |= uint8((r64 >> i) & 0x1)
183 }
184 return 1 - r
185 }
186
187 // Converts in.A and in.B to Montgomery domain and stores
188 // in 'out'
189 // out.A = in.A * R mod p
190 // out.B = in.B * R mod p
191 // Performs v = v*R^2*R^(-1) mod p, for both in.A and in.B
192 func ToMontgomery(out, in *common.Fp2) {
193 var aRR common.FpX2
194
195 // a*R*R
196 mul{{.FIELD}}(&aRR, &in.A, &{{.FIELD}}R2)
197 // a*R mod p
198 rdc{{.FIELD}}(&out.A, &aRR)
199 mul{{.FIELD}}(&aRR, &in.B, &{{.FIELD}}R2)
200 rdc{{.FIELD}}(&out.B, &aRR)
201 }
202
203 // Converts in.A and in.B from Montgomery domain and stores
204 // in 'out'
205 // out.A = in.A mod p
206 // out.B = in.B mod p
207 //
208 // After returning from the call 'in' is not modified.
209 func FromMontgomery(out, in *common.Fp2) {
210 var aR common.FpX2
211
212 // convert from montgomery domain
213 copy(aR[:], in.A[:])
214 rdc{{.FIELD}}(&out.A, &aR) // = a mod p in [0, 2p)
215 mod{{.FIELD}}(&out.A) // = a mod p in [0, p)
216 for i := range aR {
217 aR[i] = 0
218 }
219 copy(aR[:], in.B[:])
220 rdc{{.FIELD}}(&out.B, &aR)
221 mod{{.FIELD}}(&out.B)
222 }