1 package common
2
3 import (
4 "crypto/rand"
5 "encoding/binary"
6 "flag"
7 "testing"
8 )
9
10 var runVeryLongTest = flag.Bool("very-long", false, "runs very long tests")
11
12 func modQ32(x int32) int16 {
13 y := int16(x % int32(Q))
14 if y < 0 {
15 y += Q
16 }
17 return y
18 }
19
20 func TestBarrettReduceFull(t *testing.T) {
21 if !*runVeryLongTest {
22 t.SkipNow()
23 }
24 for x := -1 << 15; x <= 1<<15; x++ {
25 y1 := barrettReduce(int16(x))
26 y2 := int16(x) % Q
27 if y2 < 0 {
28 y2 += Q
29 }
30 if x < 0 && int16(-x)%Q == 0 {
31 y1 -= Q
32 }
33 if y1 != y2 {
34 t.Fatalf("%d %d %d", x, y1, y2)
35 }
36 }
37 }
38
39 func randSliceUint32WithMax(length uint, max uint32) []uint32 {
40 bytes := make([]uint8, 4*length)
41 n, err := rand.Read(bytes)
42 if err != nil {
43 panic(err)
44 } else if n < len(bytes) {
45 panic("short read from RNG")
46 }
47 x := make([]uint32, length)
48 for i := range x {
49 x[i] = binary.LittleEndian.Uint32(bytes[4*i:]) % max
50 }
51 return x
52 }
53
54 func TestMontReduce(t *testing.T) {
55 size := 1000
56 max := uint32(Q) * (1 << 16)
57 mid := int32(Q) * (1 << 15)
58 r := randSliceUint32WithMax(uint(size), max)
59
60 for i := 0; i < size; i++ {
61 x := int32(r[i]) - mid
62 y := montReduce(x)
63 if modQ32(x) != modQ32(int32(y)*(1<<16)) {
64 t.Fatalf("%d", x)
65 }
66 }
67 }
68
69 func TestToMontFull(t *testing.T) {
70 if !*runVeryLongTest {
71 t.SkipNow()
72 }
73 for x := -(1 << 15); x < 1<<15; x++ {
74 y := toMont(int16(x))
75 if modQ32(int32(y)) != modQ32(int32(x*2285)) {
76 t.Fatalf("%d", x)
77 }
78 }
79 }
80
81 func TestMontReduceFull(t *testing.T) {
82 if !*runVeryLongTest {
83 t.SkipNow()
84 }
85 for x := -int32(Q) * (1 << 15); x <= int32(Q)*(1<<15); x++ {
86 y := montReduce(x)
87 if modQ32(x) != modQ32(int32(y)*(1<<16)) {
88 t.Fatalf("%d", x)
89 }
90 }
91 }
92
93 func TestCSubQFull(t *testing.T) {
94 if !*runVeryLongTest {
95 t.SkipNow()
96 }
97 for x := -29439; x < 1<<15; x++ {
98 y1 := csubq(int16(x))
99 y2 := x
100 if int16(x) >= Q {
101 y2 -= int(Q)
102 }
103 if y1 != int16(y2) {
104 t.Fatalf("%d", x)
105 }
106 }
107 }
108
View as plain text