1 package fourq
2
3 import (
4 "crypto/rand"
5 "math/big"
6 "testing"
7
8 "github.com/cloudflare/circl/internal/test"
9 )
10
11 type (
12 tFqAdd = func(z, x, y *Fq)
13 tFqSub = func(z, x, y *Fq)
14 tFqMul = func(z, x, y *Fq)
15 tFqSqr = func(z, x *Fq)
16 )
17
18 func TestFqOne(t *testing.T) {
19 x := &Fq{}
20 x.setOne()
21 got0, got1 := x.toBigInt()
22 want0, want1 := big.NewInt(1), big.NewInt(0)
23 if got0.Cmp(want0) != 0 {
24 test.ReportError(t, got0, want0, x)
25 }
26 if got1.Cmp(want1) != 0 {
27 test.ReportError(t, got1, want1, x)
28 }
29 }
30
31 func TestFqSign(t *testing.T) {
32 testTimes := 1 << 9
33 x := &Fq{}
34 P := getModulus()
35 var P1div2 big.Int
36 P1div2.Add(P, big.NewInt(1)).Rsh(&P1div2, 1)
37
38
39 x.setBigInt(big.NewInt(0), big.NewInt(0))
40 got := fqSgn(x)
41 want := 0
42 if got != want {
43 test.ReportError(t, got, want, x)
44 }
45
46
47 x.setBigInt(P, P)
48 got = fqSgn(x)
49 want = 0
50 if got != want {
51 test.ReportError(t, got, want, x)
52 }
53
54
55 x.setBigInt(&P1div2, &P1div2)
56 got = fqSgn(x)
57 want = -1
58 if got != want {
59 test.ReportError(t, got, want, x)
60 }
61
62
63 for i := 0; i < testTimes; i++ {
64 bigX1, _ := rand.Int(rand.Reader, &P1div2)
65 x.setBigInt(P, bigX1)
66 got = fqSgn(x)
67 want = 1
68 if got != want {
69 test.ReportError(t, got, want, x)
70 }
71 }
72
73 for i := 0; i < testTimes; i++ {
74 bigX0, _ := rand.Int(rand.Reader, &P1div2)
75 bigX1, _ := rand.Int(rand.Reader, &P1div2)
76 x.setBigInt(bigX0, bigX1)
77 got = fqSgn(x)
78 want = 1
79 if got != want {
80 test.ReportError(t, got, want, x)
81 }
82 }
83
84 for i := 0; i < testTimes; i++ {
85 bigX1, _ := rand.Int(rand.Reader, &P1div2)
86 bigX1.Add(bigX1, &P1div2)
87 x.setBigInt(P, bigX1)
88 got = fqSgn(x)
89 want = -1
90 if got != want {
91 test.ReportError(t, got, want, x)
92 }
93 }
94
95 for i := 0; i < testTimes; i++ {
96 bigX0, _ := rand.Int(rand.Reader, &P1div2)
97 bigX1, _ := rand.Int(rand.Reader, &P1div2)
98 bigX0.Add(bigX0, &P1div2)
99 bigX1.Add(bigX1, &P1div2)
100 x.setBigInt(bigX0, bigX1)
101 got = fqSgn(x)
102 want = -1
103 if got != want {
104 test.ReportError(t, got, want, x)
105 }
106 }
107 }
108
109 func TestFqIsZero(t *testing.T) {
110 x := &Fq{}
111 P := getModulus()
112
113 x.setBigInt(big.NewInt(0), big.NewInt(0))
114 got := x.isZero()
115 want := true
116 if got != want {
117 test.ReportError(t, got, want, x)
118 }
119
120
121 x.setBigInt(P, P)
122 got = x.isZero()
123 want = true
124 if got != want {
125 test.ReportError(t, got, want, x)
126 }
127
128
129 bigX0, _ := rand.Int(rand.Reader, P)
130 bigX1, _ := rand.Int(rand.Reader, P)
131 x.setBigInt(bigX0, bigX1)
132 got = x.isZero()
133 want = false
134 if got != want {
135 test.ReportError(t, got, want, x)
136 }
137 }
138
139 func TestFqNeg(t *testing.T) {
140 testTimes := 1 << 9
141 x, z := &Fq{}, &Fq{}
142 P := getModulus()
143 for i := 0; i < testTimes; i++ {
144 bigX0, _ := rand.Int(rand.Reader, P)
145 bigX1, _ := rand.Int(rand.Reader, P)
146
147 x.setBigInt(bigX0, bigX1)
148 fqNeg(z, x)
149 got0, got1 := z.toBigInt()
150
151 want0 := bigX0.Neg(bigX0)
152 want1 := bigX1.Neg(bigX1)
153 want0 = want0.Mod(want0, P)
154 want1 = want1.Mod(want1, P)
155 if got0.Cmp(want0) != 0 {
156 test.ReportError(t, got0, want0, x)
157 }
158 if got1.Cmp(want1) != 0 {
159 test.ReportError(t, got1, want1, x)
160 }
161 }
162 }
163
164 func testFqAdd(t *testing.T, f tFqAdd) {
165 testTimes := 1 << 9
166 x, y, z := &Fq{}, &Fq{}, &Fq{}
167 P := getModulus()
168 for i := 0; i < testTimes; i++ {
169 bigX0, _ := rand.Int(rand.Reader, P)
170 bigX1, _ := rand.Int(rand.Reader, P)
171 bigY0, _ := rand.Int(rand.Reader, P)
172 bigY1, _ := rand.Int(rand.Reader, P)
173
174 x.setBigInt(bigX0, bigX1)
175 y.setBigInt(bigY0, bigY1)
176 f(z, x, y)
177 got0, got1 := z.toBigInt()
178
179 want0 := bigX0.Add(bigX0, bigY0)
180 want1 := bigX1.Add(bigX1, bigY1)
181 want0 = want0.Mod(want0, P)
182 want1 = want1.Mod(want1, P)
183
184 if got0.Cmp(want0) != 0 {
185 test.ReportError(t, got0, want0, x, y)
186 }
187 if got1.Cmp(want1) != 0 {
188 test.ReportError(t, got1, want1, x, y)
189 }
190 }
191 }
192
193 func testFqSub(t *testing.T, f tFqSub) {
194 testTimes := 1 << 9
195 x, y, z := &Fq{}, &Fq{}, &Fq{}
196 P := getModulus()
197 for i := 0; i < testTimes; i++ {
198 bigX0, _ := rand.Int(rand.Reader, P)
199 bigX1, _ := rand.Int(rand.Reader, P)
200 bigY0, _ := rand.Int(rand.Reader, P)
201 bigY1, _ := rand.Int(rand.Reader, P)
202
203 x.setBigInt(bigX0, bigX1)
204 y.setBigInt(bigY0, bigY1)
205 f(z, x, y)
206 got0, got1 := z.toBigInt()
207
208 want0 := bigX0.Sub(bigX0, bigY0)
209 want1 := bigX1.Sub(bigX1, bigY1)
210 want0 = want0.Mod(want0, P)
211 want1 = want1.Mod(want1, P)
212
213 if got0.Cmp(want0) != 0 {
214 test.ReportError(t, got0, want0, x, y)
215 }
216 if got1.Cmp(want1) != 0 {
217 test.ReportError(t, got1, want1, x, y)
218 }
219 }
220 }
221
222 func testFqMul(t *testing.T, f tFqMul) {
223 testTimes := 1 << 9
224 x, y, z := &Fq{}, &Fq{}, &Fq{}
225 P := getModulus()
226 for i := 0; i < testTimes; i++ {
227 bigX0, _ := rand.Int(rand.Reader, P)
228 bigX1, _ := rand.Int(rand.Reader, P)
229 bigY0, _ := rand.Int(rand.Reader, P)
230 bigY1, _ := rand.Int(rand.Reader, P)
231
232 x.setBigInt(bigX0, bigX1)
233 y.setBigInt(bigY0, bigY1)
234 f(z, x, y)
235 got0, got1 := z.toBigInt()
236
237 x0y0 := new(big.Int).Mul(bigX0, bigY0)
238 x0y1 := new(big.Int).Mul(bigX0, bigY1)
239 x1y0 := new(big.Int).Mul(bigX1, bigY0)
240 x1y1 := new(big.Int).Mul(bigX1, bigY1)
241 want0 := x0y0.Sub(x0y0, x1y1)
242 want1 := x1y0.Add(x1y0, x0y1)
243 want0 = want0.Mod(want0, P)
244 want1 = want1.Mod(want1, P)
245
246 if got0.Cmp(want0) != 0 {
247 test.ReportError(t, got0, want0, x, y)
248 }
249 if got1.Cmp(want1) != 0 {
250 test.ReportError(t, got1, want1, x, y)
251 }
252 }
253 }
254
255 func testFqSqr(t *testing.T, f tFqSqr) {
256 testTimes := 1 << 9
257 x, z := &Fq{}, &Fq{}
258 P := getModulus()
259 for i := 0; i < testTimes; i++ {
260 bigX0, _ := rand.Int(rand.Reader, P)
261 bigX1, _ := rand.Int(rand.Reader, P)
262
263 x.setBigInt(bigX0, bigX1)
264 f(z, x)
265 got0, got1 := z.toBigInt()
266
267 x0x0 := new(big.Int).Mul(bigX0, bigX0)
268 x0x1 := new(big.Int).Mul(bigX0, bigX1)
269 x1x1 := new(big.Int).Mul(bigX1, bigX1)
270 want0 := x0x0.Sub(x0x0, x1x1)
271 want1 := x0x1.Lsh(x0x1, 1)
272 want0 = want0.Mod(want0, P)
273 want1 = want1.Mod(want1, P)
274
275 if got0.Cmp(want0) != 0 {
276 test.ReportError(t, got0, want0, x)
277 }
278 if got1.Cmp(want1) != 0 {
279 test.ReportError(t, got1, want1, x)
280 }
281 }
282 }
283
284 func TestFqInv(t *testing.T) {
285 testTimes := 1 << 9
286 x, z := &Fq{}, &Fq{}
287 P := getModulus()
288 for i := 0; i < testTimes; i++ {
289 bigX0, _ := rand.Int(rand.Reader, P)
290 bigX1, _ := rand.Int(rand.Reader, P)
291
292 x.setBigInt(bigX0, bigX1)
293 fqInv(z, x)
294 got0, got1 := z.toBigInt()
295
296 x0x0 := new(big.Int).Mul(bigX0, bigX0)
297 x1x1 := new(big.Int).Mul(bigX1, bigX1)
298 inv := x0x0.Add(x0x0, x1x1)
299 inv.ModInverse(inv, P)
300 want0 := bigX0.Mul(bigX0, inv)
301 want1 := bigX1.Mul(bigX1, inv).Neg(bigX1)
302 want0 = want0.Mod(want0, P)
303 want1 = want1.Mod(want1, P)
304
305 if got0.Cmp(want0) != 0 {
306 test.ReportError(t, got0, want0, x)
307 }
308 if got1.Cmp(want1) != 0 {
309 test.ReportError(t, got1, want1, x)
310 }
311 }
312 }
313
314 func TestFqGeneric(t *testing.T) {
315 t.Run("Add", func(t *testing.T) { testFqAdd(t, fqAddGeneric) })
316 t.Run("Sub", func(t *testing.T) { testFqSub(t, fqSubGeneric) })
317 t.Run("Mul", func(t *testing.T) { testFqMul(t, fqMulGeneric) })
318 t.Run("Sqr", func(t *testing.T) { testFqSqr(t, fqSqrGeneric) })
319 }
320
321 func TestFqNative(t *testing.T) {
322 t.Run("Add", func(t *testing.T) { testFqAdd(t, fqAdd) })
323 t.Run("Sub", func(t *testing.T) { testFqSub(t, fqSub) })
324 t.Run("Mul", func(t *testing.T) { testFqMul(t, fqMul) })
325 t.Run("Sqr", func(t *testing.T) { testFqSqr(t, fqSqr) })
326 }
327
328 func BenchmarkFq(b *testing.B) {
329 x, y, z := &Fq{}, &Fq{}, &Fq{}
330
331 b.Run("Add", func(b *testing.B) {
332 for i := 0; i < b.N; i++ {
333 fqAdd(z, x, y)
334 }
335 })
336 b.Run("Sub", func(b *testing.B) {
337 for i := 0; i < b.N; i++ {
338 fqSub(z, x, y)
339 }
340 })
341 b.Run("Mul", func(b *testing.B) {
342 for i := 0; i < b.N; i++ {
343 fqMul(z, x, y)
344 }
345 })
346 b.Run("Sqr", func(b *testing.B) {
347 for i := 0; i < b.N; i++ {
348 fqSqr(z, x)
349 }
350 })
351 b.Run("Inv", func(b *testing.B) {
352 for i := 0; i < b.N; i++ {
353 fqInv(z, x)
354 }
355 })
356 b.Run("Sqrt", func(b *testing.B) {
357 for i := 0; i < b.N; i++ {
358 fqSqrt(z, x, y, 1)
359 }
360 })
361 }
362
View as plain text