ntt27_test.go raw
1 package crypto
2
3 import (
4 "math/rand"
5 "testing"
6 )
7
8 func TestDigitRev3(t *testing.T) {
9 // For 3 digits (n=27), digit reversal should be an involution.
10 for i := range 27 {
11 j := digitRev3(i, 3)
12 if j < 0 || j >= 27 {
13 t.Fatalf("digitRev3(%d, 3) = %d out of range", i, j)
14 }
15 k := digitRev3(j, 3)
16 if k != i {
17 t.Fatalf("digitRev3 not involution: digitRev3(%d) = %d, digitRev3(%d) = %d", i, j, j, k)
18 }
19 }
20
21 // Check specific values.
22 // 0 in base 3 = 000, reversed = 000 = 0
23 if digitRev3(0, 3) != 0 {
24 t.Fatalf("digitRev3(0, 3) = %d, want 0", digitRev3(0, 3))
25 }
26 // 1 in base 3 = 001, reversed = 100 = 9
27 if digitRev3(1, 3) != 9 {
28 t.Fatalf("digitRev3(1, 3) = %d, want 9", digitRev3(1, 3))
29 }
30 // 3 in base 3 = 010, reversed = 010 = 3
31 if digitRev3(3, 3) != 3 {
32 t.Fatalf("digitRev3(3, 3) = %d, want 3", digitRev3(3, 3))
33 }
34 }
35
36 func TestNTT27RoundTrip(t *testing.T) {
37 rng := rand.New(rand.NewSource(42))
38
39 for trial := range 10 {
40 var a [GnarlN]uint16
41 for i := range GnarlN {
42 a[i] = uint16(rng.Intn(GnarlP))
43 }
44
45 orig := a
46 ntt27(&a)
47 intt27(&a)
48
49 for i := range GnarlN {
50 if a[i] != orig[i] {
51 t.Fatalf("trial %d: round-trip failed at index %d: got %d, want %d",
52 trial, i, a[i], orig[i])
53 }
54 }
55 }
56 }
57
58 func TestNTT27Zero(t *testing.T) {
59 var a [GnarlN]uint16
60 ntt27(&a)
61 for i, v := range a {
62 if v != 0 {
63 t.Fatalf("NTT of zero polynomial: index %d = %d, want 0", i, v)
64 }
65 }
66 intt27(&a)
67 for i, v := range a {
68 if v != 0 {
69 t.Fatalf("INTT of zero: index %d = %d, want 0", i, v)
70 }
71 }
72 }
73
74 func TestNTT27Convolution(t *testing.T) {
75 // Pointwise multiply in NTT domain should equal polynomial multiplication
76 // modulo (x^27 + 1) in coefficient domain.
77 rng := rand.New(rand.NewSource(99))
78
79 var a, b [GnarlN]uint16
80 for i := range GnarlN {
81 a[i] = uint16(rng.Intn(GnarlP))
82 b[i] = uint16(rng.Intn(GnarlP))
83 }
84
85 // Schoolbook multiplication mod (x^27 + 1).
86 var expected [GnarlN]uint16
87 for i := range GnarlN {
88 for j := range GnarlN {
89 k := i + j
90 if k < GnarlN {
91 expected[k] = mod271(uint32(expected[k]) + uint32(a[i])*uint32(b[j]))
92 } else {
93 // x^27 = -1 mod (x^27 + 1), so x^(27+r) = -x^r
94 k -= GnarlN
95 expected[k] = mod271s(int(expected[k]) - int(a[i])*int(b[j]))
96 }
97 }
98 }
99
100 // NTT multiplication.
101 aNtt := a
102 bNtt := b
103 ntt27(&aNtt)
104 ntt27(&bNtt)
105
106 var cNtt [GnarlN]uint16
107 for i := range GnarlN {
108 cNtt[i] = mod271(uint32(aNtt[i]) * uint32(bNtt[i]))
109 }
110 intt27(&cNtt)
111
112 for i := range GnarlN {
113 if cNtt[i] != expected[i] {
114 t.Fatalf("convolution mismatch at index %d: NTT gives %d, schoolbook gives %d",
115 i, cNtt[i], expected[i])
116 }
117 }
118 }
119
120 func TestNTT27Negacyclic(t *testing.T) {
121 // x^27 ≡ -1 mod (x^27 + 1).
122 // Represent x^27 as polynomial: coefficient 0 at index 27, which wraps to
123 // -1 * x^0. So the polynomial [p-1, 0, 0, ...] should be the product of
124 // [0, 1, 0, ...] raised to the 27th power.
125 //
126 // Simpler test: multiply [0,1,0,...,0] (which is x) by itself 27 times
127 // and check we get [-1, 0, ..., 0].
128 //
129 // Actually, just multiply x^26 * x = x^27. Start with x, multiply by x
130 // in NTT domain 26 times.
131
132 // x = [0, 1, 0, ..., 0]
133 var x [GnarlN]uint16
134 x[1] = 1
135
136 // x in NTT domain.
137 xNtt := x
138 ntt27(&xNtt)
139
140 // x^27 in NTT domain = pointwise x^27.
141 var result [GnarlN]uint16
142 for i := range GnarlN {
143 result[i] = powMod271(int(xNtt[i]), 27)
144 }
145 intt27(&result)
146
147 // Should be [-1, 0, 0, ..., 0] = [270, 0, 0, ..., 0].
148 if result[0] != uint16(GnarlP-1) {
149 t.Fatalf("x^27 coefficient 0: got %d, want %d", result[0], GnarlP-1)
150 }
151 for i := 1; i < GnarlN; i++ {
152 if result[i] != 0 {
153 t.Fatalf("x^27 coefficient %d: got %d, want 0", i, result[i])
154 }
155 }
156 }
157
158 func TestNTT27PsiPowers(t *testing.T) {
159 // Verify psi^54 = 1 and psi^27 = p-1 = -1.
160 if psiPows27[0] != 1 {
161 t.Fatalf("psi^0 = %d, want 1", psiPows27[0])
162 }
163 // psi^27 should be p-1 (since psi is a 54th root, psi^27 = psi^(54/2) = -1).
164 if psiPows27[27] != uint16(GnarlP-1) {
165 t.Fatalf("psi^27 = %d, want %d", psiPows27[27], GnarlP-1)
166 }
167
168 // Verify invN27.
169 prod := mod271(uint32(invN27) * GnarlN)
170 if prod != 1 {
171 t.Fatalf("invN27 * 27 mod 271 = %d, want 1", prod)
172 }
173 }
174
175 func BenchmarkNTT27(b *testing.B) {
176 var a [GnarlN]uint16
177 for i := range GnarlN {
178 a[i] = uint16(i * 10 % GnarlP)
179 }
180 b.ResetTimer()
181 for i := 0; i < b.N; i++ {
182 ntt27(&a)
183 }
184 }
185
186 func BenchmarkINTT27(b *testing.B) {
187 var a [GnarlN]uint16
188 for i := range GnarlN {
189 a[i] = uint16(i * 10 % GnarlP)
190 }
191 b.ResetTimer()
192 for i := 0; i < b.N; i++ {
193 intt27(&a)
194 }
195 }
196
197 func BenchmarkMod271(b *testing.B) {
198 x := uint32(50000)
199 for i := 0; i < b.N; i++ {
200 _ = mod271(x)
201 x = uint32(mod271(x))*270 + 1
202 }
203 }
204
205 func BenchmarkGnarlCompress(b *testing.B) {
206 var block [gnarlInputBytes]byte
207 for i := range block {
208 block[i] = byte(i * 37)
209 }
210 b.ResetTimer()
211 for i := 0; i < b.N; i++ {
212 gnarlCompress(&block)
213 }
214 }
215
216 func TestNTT27Linearity(t *testing.T) {
217 // NTT should be linear: NTT(a + b) = NTT(a) + NTT(b).
218 rng := rand.New(rand.NewSource(777))
219
220 var a, b, sum [GnarlN]uint16
221 for i := range GnarlN {
222 a[i] = uint16(rng.Intn(GnarlP))
223 b[i] = uint16(rng.Intn(GnarlP))
224 sum[i] = mod271(uint32(a[i]) + uint32(b[i]))
225 }
226
227 ntt27(&a)
228 ntt27(&b)
229 ntt27(&sum)
230
231 for i := range GnarlN {
232 expected := mod271(uint32(a[i]) + uint32(b[i]))
233 if sum[i] != expected {
234 t.Fatalf("linearity failed at index %d: NTT(a+b)[%d]=%d, NTT(a)+NTT(b)=%d",
235 i, i, sum[i], expected)
236 }
237 }
238 }
239