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 tFpAdd = func(z, x, y *Fp)
13 tFpSub = func(z, x, y *Fp)
14 tFpMul = func(z, x, y *Fp)
15 tFpSqr = func(z, x *Fp)
16 tFpHlf = func(z, x *Fp)
17 tFpModp = func(z *Fp)
18 )
19
20 func getModulus() *big.Int {
21 p := big.NewInt(1)
22 return p.Lsh(p, 127).Sub(p, big.NewInt(1))
23 }
24
25 func TestFpSign(t *testing.T) {
26 const testTimes = 1 << 9
27 P := getModulus()
28 x := &Fp{}
29 var P1div2 big.Int
30 P1div2.Add(P, big.NewInt(1)).Rsh(&P1div2, 1)
31
32
33 x.setBigInt(big.NewInt(0))
34 got := fpSgn(x)
35 want := 0
36 if got != want {
37 test.ReportError(t, got, want, x)
38 }
39
40
41 x.setBigInt(P)
42 got = fpSgn(x)
43 want = 0
44 if got != want {
45 test.ReportError(t, got, want, x)
46 }
47
48
49 x.setBigInt(&P1div2)
50 got = fpSgn(x)
51 want = -1
52 if got != want {
53 test.ReportError(t, got, want, x)
54 }
55
56
57 for i := 0; i < testTimes; i++ {
58 bigX, _ := rand.Int(rand.Reader, &P1div2)
59 x.setBigInt(bigX)
60 got = fpSgn(x)
61 want = 1
62 if got != want {
63 test.ReportError(t, got, want, x)
64 }
65 }
66
67 for i := 0; i < testTimes; i++ {
68 bigX, _ := rand.Int(rand.Reader, &P1div2)
69 bigX.Add(bigX, &P1div2)
70 x.setBigInt(bigX)
71 got = fpSgn(x)
72 want = -1
73 if got != want {
74 test.ReportError(t, got, want, x)
75 }
76 }
77 }
78
79 func TestFpIsZero(t *testing.T) {
80 P := getModulus()
81 x := &Fp{}
82
83 x.setBigInt(big.NewInt(0))
84 got := x.isZero()
85 want := true
86 if got != want {
87 test.ReportError(t, got, want, x)
88 }
89
90
91 x.setBigInt(P)
92 got = x.isZero()
93 want = true
94 if got != want {
95 test.ReportError(t, got, want, x)
96 }
97
98
99 _, _ = rand.Read(x[:])
100 got = x.isZero()
101 want = false
102 if got != want {
103 test.ReportError(t, got, want, x)
104 }
105 }
106
107 func testFpModp(t *testing.T, f tFpModp) {
108 const testTimes = 1 << 9
109 P := getModulus()
110 x := &Fp{}
111 var bigX big.Int
112
113 bigX.Set(P)
114 x.setBigInt(&bigX)
115 f(x)
116 got := x.toBigInt()
117 want := big.NewInt(0)
118 if got.Cmp(want) != 0 {
119 test.ReportError(t, got, want, x)
120 }
121
122
123 bigX.Add(P, big.NewInt(1))
124 x.setBigInt(&bigX)
125 f(x)
126 got = x.toBigInt()
127 want = big.NewInt(1)
128 if got.Cmp(want) != 0 {
129 test.ReportError(t, got, want, x)
130 }
131
132 for i := 0; i < testTimes; i++ {
133 _, _ = rand.Read(x[:])
134
135 bigX := x.toBigInt()
136
137 fpMod(x)
138 got := x.toBigInt()
139
140 want := bigX.Mod(bigX, P)
141 if got.Cmp(want) != 0 {
142 test.ReportError(t, got, want, x)
143 }
144 }
145 }
146
147 func TestFpNeg(t *testing.T) {
148 const testTimes = 1 << 9
149 P := getModulus()
150 x, z := &Fp{}, &Fp{}
151 for i := 0; i < testTimes; i++ {
152 bigX, _ := rand.Int(rand.Reader, P)
153
154 x.setBigInt(bigX)
155 fpNeg(z, x)
156 got := z.toBigInt()
157
158 want := bigX.Neg(bigX)
159 want = want.Mod(want, P)
160 if got.Cmp(want) != 0 {
161 test.ReportError(t, got, want, x)
162 }
163 }
164 }
165
166 func testFpHlf(t *testing.T, f tFpHlf) {
167 const testTimes = 1 << 9
168 P := getModulus()
169 x, z := &Fp{}, &Fp{}
170 invTwo := big.NewInt(2)
171 invTwo.ModInverse(invTwo, P)
172 for i := 0; i < testTimes; i++ {
173 bigX, _ := rand.Int(rand.Reader, P)
174
175 x.setBigInt(bigX)
176 f(z, x)
177 got := z.toBigInt()
178
179 want := bigX.Mul(bigX, invTwo)
180 want = want.Mod(want, P)
181 if got.Cmp(want) != 0 {
182 test.ReportError(t, got, want, x)
183 }
184 }
185 }
186
187 func testFpAdd(t *testing.T, f tFpAdd) {
188 const testTimes = 1 << 9
189 P := getModulus()
190 x, y, z := &Fp{}, &Fp{}, &Fp{}
191 for i := 0; i < testTimes; i++ {
192 bigX, _ := rand.Int(rand.Reader, P)
193 bigY, _ := rand.Int(rand.Reader, P)
194
195 x.setBigInt(bigX)
196 y.setBigInt(bigY)
197 f(z, x, y)
198 got := z.toBigInt()
199
200 want := bigX.Add(bigX, bigY)
201 want = want.Mod(want, P)
202 if got.Cmp(want) != 0 {
203 test.ReportError(t, got, want, x, y)
204 }
205 }
206 }
207
208 func testFpSub(t *testing.T, f tFpSub) {
209 const testTimes = 1 << 9
210 P := getModulus()
211 x, y, z := &Fp{}, &Fp{}, &Fp{}
212 for i := 0; i < testTimes; i++ {
213 bigX, _ := rand.Int(rand.Reader, P)
214 bigY, _ := rand.Int(rand.Reader, P)
215
216 x.setBigInt(bigX)
217 y.setBigInt(bigY)
218 f(z, x, y)
219 got := z.toBigInt()
220
221 want := bigX.Sub(bigX, bigY)
222 want = want.Mod(want, P)
223 if got.Cmp(want) != 0 {
224 test.ReportError(t, got, want, x, y)
225 }
226 }
227 }
228
229 func testFpMul(t *testing.T, f tFpMul) {
230 const testTimes = 1 << 9
231 P := getModulus()
232 x, y, z := &Fp{}, &Fp{}, &Fp{}
233 for i := 0; i < testTimes; i++ {
234 bigX, _ := rand.Int(rand.Reader, P)
235 bigY, _ := rand.Int(rand.Reader, P)
236
237 x.setBigInt(bigX)
238 y.setBigInt(bigY)
239 f(z, x, y)
240 got := z.toBigInt()
241
242 want := bigX.Mul(bigX, bigY)
243 want = want.Mod(want, P)
244 if got.Cmp(want) != 0 {
245 test.ReportError(t, got, want, x, y)
246 }
247 }
248 }
249
250 func testFpSqr(t *testing.T, f tFpSqr) {
251 const testTimes = 1 << 9
252 P := getModulus()
253 x, z := &Fp{}, &Fp{}
254 for i := 0; i < testTimes; i++ {
255 bigX, _ := rand.Int(rand.Reader, P)
256
257 x.setBigInt(bigX)
258 f(z, x)
259 got := z.toBigInt()
260
261 want := bigX.Mul(bigX, bigX)
262 want = want.Mod(want, P)
263
264 if got.Cmp(want) != 0 {
265 test.ReportError(t, got, want, x)
266 }
267 }
268 }
269
270 func TestFpInv(t *testing.T) {
271 const testTimes = 1 << 9
272 P := getModulus()
273 x, z := &Fp{}, &Fp{}
274 for i := 0; i < testTimes; i++ {
275 bigX, _ := rand.Int(rand.Reader, P)
276
277 x.setBigInt(bigX)
278 fpInv(z, x)
279 got := z.toBigInt()
280
281 want := bigX.ModInverse(bigX, P)
282 if got.Cmp(want) != 0 {
283 test.ReportError(t, got, want, x)
284 }
285 }
286 }
287
288 func TestFpGeneric(t *testing.T) {
289 t.Run("Add", func(t *testing.T) { testFpAdd(t, fpAddGeneric) })
290 t.Run("Sub", func(t *testing.T) { testFpSub(t, fpSubGeneric) })
291 t.Run("Mul", func(t *testing.T) { testFpMul(t, fpMulGeneric) })
292 t.Run("Sqr", func(t *testing.T) { testFpSqr(t, fpSqrGeneric) })
293 t.Run("Hlf", func(t *testing.T) { testFpHlf(t, fpHlfGeneric) })
294 t.Run("Modp", func(t *testing.T) { testFpModp(t, fpModGeneric) })
295 }
296
297 func TestFpNative(t *testing.T) {
298 t.Run("Add", func(t *testing.T) { testFpAdd(t, fpAdd) })
299 t.Run("Sub", func(t *testing.T) { testFpSub(t, fpSub) })
300 t.Run("Mul", func(t *testing.T) { testFpMul(t, fpMul) })
301 t.Run("Sqr", func(t *testing.T) { testFpSqr(t, fpSqr) })
302 t.Run("Hlf", func(t *testing.T) { testFpHlf(t, fpHlf) })
303 t.Run("Modp", func(t *testing.T) { testFpModp(t, fpMod) })
304 }
305
306 func BenchmarkFp(b *testing.B) {
307 x, y, z := &Fp{}, &Fp{}, &Fp{}
308 p := getModulus()
309 n, _ := rand.Int(rand.Reader, p)
310 x.setBigInt(n)
311 n, _ = rand.Int(rand.Reader, p)
312 y.setBigInt(n)
313
314 b.Run("Add", func(b *testing.B) {
315 for i := 0; i < b.N; i++ {
316 fpAdd(z, x, y)
317 }
318 })
319 b.Run("Sub", func(b *testing.B) {
320 for i := 0; i < b.N; i++ {
321 fpSub(z, x, y)
322 }
323 })
324 b.Run("Mul", func(b *testing.B) {
325 for i := 0; i < b.N; i++ {
326 fpMul(z, x, y)
327 }
328 })
329 b.Run("Sqr", func(b *testing.B) {
330 for i := 0; i < b.N; i++ {
331 fpSqr(z, x)
332 }
333 })
334 b.Run("Inv", func(b *testing.B) {
335 for i := 0; i < b.N; i++ {
336 fpInv(z, x)
337 }
338 })
339 }
340
View as plain text