poly_test.go raw
1 package gnarlring
2
3 import (
4 "testing"
5
6 "git.smesh.lol/gnarl-hamadryad/crypto"
7 )
8
9 func TestPoly27New(t *testing.T) {
10 p := NewPoly27()
11 if !IsZero(p) {
12 t.Fatal("NewPoly27 should be zero")
13 }
14 if p.isNTT {
15 t.Fatal("NewPoly27 should be coefficient form")
16 }
17 }
18
19 func TestPoly27Clone(t *testing.T) {
20 p := NewPoly27()
21 p.Coeffs[0] = 42
22 p.isNTT = true
23
24 c := p.Clone()
25 if !Equal(p, c) {
26 t.Fatal("Clone not equal")
27 }
28 c.Coeffs[0] = 99
29 if p.Coeffs[0] != 42 {
30 t.Fatal("Clone shares backing array")
31 }
32 }
33
34 func TestAddSub(t *testing.T) {
35 a := NewPoly27()
36 b := NewPoly27()
37 a.Coeffs[0] = 100
38 b.Coeffs[0] = 200
39
40 sum := Add(a, b)
41 if sum.Coeffs[0] != 29 { // 100+200=300 ≡ 29 mod 271
42 t.Fatalf("Add: got %d, want 29", sum.Coeffs[0])
43 }
44
45 diff := Sub(b, a)
46 if diff.Coeffs[0] != 100 {
47 t.Fatalf("Sub: got %d, want 100", diff.Coeffs[0])
48 }
49 }
50
51 func TestNeg(t *testing.T) {
52 a := NewPoly27()
53 a.Coeffs[0] = 42
54
55 n := Neg(a)
56 if n.Coeffs[0] != Q-42 {
57 t.Fatalf("Neg: got %d, want %d", n.Coeffs[0], Q-42)
58 }
59
60 z := NewPoly27()
61 nz := Neg(z)
62 if nz.Coeffs[0] != 0 {
63 t.Fatal("Neg of zero should be zero")
64 }
65 }
66
67 func TestScalarMul(t *testing.T) {
68 a := NewPoly27()
69 a.Coeffs[0] = 50
70
71 s := ScalarMul(a, 10)
72 if s.Coeffs[0] != crypto.Mod271(500) {
73 t.Fatalf("ScalarMul: got %d, want %d", s.Coeffs[0], crypto.Mod271(500))
74 }
75 }
76
77 func TestNTTINTTRoundTrip(t *testing.T) {
78 p := NewPoly27()
79 for i := range N {
80 p.Coeffs[i] = uint16(i * 10 % Q)
81 }
82 orig := p.Clone()
83
84 p.NTT()
85 if !p.isNTT {
86 t.Fatal("NTT did not set isNTT")
87 }
88
89 p.INTT()
90 if p.isNTT {
91 t.Fatal("INTT did not clear isNTT")
92 }
93
94 if !Equal(p, orig) {
95 t.Fatal("NTT/INTT round-trip failed")
96 }
97 }
98
99 func TestNTTIdempotent(t *testing.T) {
100 p := NewPoly27()
101 p.Coeffs[0] = 1
102 p.NTT()
103 c := p.Clone()
104 p.NTT() // should be no-op
105 if !Equal(p, c) {
106 t.Fatal("NTT not idempotent")
107 }
108 }
109
110 func TestMulViaNTTvsSchoolbook(t *testing.T) {
111 a := NewPoly27()
112 b := NewPoly27()
113 for i := range N {
114 a.Coeffs[i] = uint16(i + 1)
115 b.Coeffs[i] = uint16(N - i)
116 }
117
118 result := Mul(a, b)
119
120 // Schoolbook multiplication mod (x^27 + 1).
121 var expected [N]uint16
122 for i := 0; i < N; i++ {
123 for j := 0; j < N; j++ {
124 k := i + j
125 if k < N {
126 expected[k] = addMod(expected[k], crypto.Mod271(uint32(a.Coeffs[i])*uint32(b.Coeffs[j])))
127 } else {
128 // x^27 = -1, so x^k = -x^{k-27}
129 k -= N
130 prod := crypto.Mod271(uint32(a.Coeffs[i]) * uint32(b.Coeffs[j]))
131 expected[k] = subMod(expected[k], prod)
132 }
133 }
134 }
135
136 for i, v := range result.Coeffs {
137 if v != expected[i] {
138 t.Fatalf("mul mismatch at %d: got %d, want %d", i, v, expected[i])
139 }
140 }
141 }
142
143 func TestInverse(t *testing.T) {
144 // 1^{-1} = 1.
145 a := NewPoly27()
146 a.Coeffs[0] = 1
147 inv := Inverse(a)
148 if inv == nil {
149 t.Fatal("Inverse(1) returned nil")
150 }
151 prod := Mul(a, inv)
152 if prod.Coeffs[0] != 1 {
153 t.Fatalf("1 * 1^{-1}[0] = %d, want 1", prod.Coeffs[0])
154 }
155 for i := 1; i < N; i++ {
156 if prod.Coeffs[i] != 0 {
157 t.Fatalf("1 * 1^{-1}[%d] = %d, want 0", i, prod.Coeffs[i])
158 }
159 }
160
161 // Random invertible polynomial: non-zero constant.
162 a2 := NewPoly27()
163 a2.Coeffs[0] = 42
164 inv2 := Inverse(a2)
165 if inv2 == nil {
166 t.Fatal("Inverse(42) returned nil (constant in NTT domain should be [42,...,42])")
167 }
168 prod2 := Mul(a2, inv2)
169 if prod2.Coeffs[0] != 1 {
170 t.Fatalf("42 * 42^{-1}[0] = %d, want 1", prod2.Coeffs[0])
171 }
172
173 // Complex polynomial: sparse with known non-zero NTT values.
174 // f(x) = 1 + 2x + 3x^2. After NTT, each slot is f(-psi^(2j+1)).
175 a3 := NewPoly27()
176 a3.Coeffs[0] = 1
177 a3.Coeffs[1] = 2
178 a3.Coeffs[2] = 3
179 inv3 := Inverse(a3)
180 if inv3 == nil {
181 t.Fatal("Inverse(1+2x+3x^2) returned nil")
182 }
183 prod3 := Mul(a3, inv3)
184 if prod3.Coeffs[0] != 1 {
185 t.Fatalf("round-trip failed for 1+2x+3x^2: got %d", prod3.Coeffs[0])
186 }
187 }
188
189 func TestInverseNonInvertible(t *testing.T) {
190 // Zero polynomial is not invertible.
191 z := NewPoly27()
192 if Inverse(z) != nil {
193 t.Fatal("zero should not be invertible")
194 }
195
196 // A polynomial with a zero in the NTT domain is not invertible.
197 // x + 1 has x=-1 as a root... but we need to check.
198 // Simpler: any polynomial where all coefficients are Q is zero = not invertible.
199 qAll := NewPoly27()
200 for i := range N {
201 qAll.Coeffs[i] = Q // same as 0 mod Q
202 }
203 if Inverse(qAll) != nil {
204 t.Fatal("Q-vector should not be invertible")
205 }
206 }
207
208 func TestNorm(t *testing.T) {
209 // 200 > 135: centered value = 200-271 = -71, abs = 71.
210 p := NewPoly27()
211 p.Coeffs[0] = 200
212 if Norm(p) != 71 {
213 t.Fatalf("Norm of 200 = %d, want 71", Norm(p))
214 }
215
216 // 42 ≤ 135: centered value = 42, abs = 42.
217 p.Coeffs[0] = 42
218 if Norm(p) != 42 {
219 t.Fatalf("Norm of 42 = %d, want 42", Norm(p))
220 }
221
222 // Q-5 = 266 > 135: centered value = -5, abs = 5.
223 p.Coeffs[0] = Q - 5
224 if Norm(p) != 5 {
225 t.Fatalf("Norm of Q-5 = %d, want 5", Norm(p))
226 }
227 }
228
229 func TestNormSq(t *testing.T) {
230 p := NewPoly27()
231 p.Coeffs[0] = 3
232 p.Coeffs[1] = 4
233
234 nsq := NormSq(p)
235 if nsq != 25 { // 3² + 4² = 25
236 t.Fatalf("NormSq = %d, want 25", nsq)
237 }
238 }
239
240 func TestDot(t *testing.T) {
241 a := NewPoly27()
242 b := NewPoly27()
243 a.Coeffs[0] = 3
244 a.Coeffs[1] = 4
245 b.Coeffs[0] = 5
246 b.Coeffs[1] = 6
247
248 d := Dot(a, b)
249 if d != 39 { // 3*5 + 4*6 = 39
250 t.Fatalf("Dot = %d, want 39", d)
251 }
252 }
253
254 func TestIsZero(t *testing.T) {
255 z := NewPoly27()
256 if !IsZero(z) {
257 t.Fatal("zero not detected")
258 }
259 z.Coeffs[0] = 1
260 if IsZero(z) {
261 t.Fatal("non-zero detected as zero")
262 }
263 }
264
265 func TestMarshalUnmarshalRoundTrip(t *testing.T) {
266 a := NewPoly27()
267 for i := range N {
268 a.Coeffs[i] = uint16((i*37 + 1) % Q)
269 }
270
271 data := a.MarshalBinary()
272 if len(data) != PolyBytes {
273 t.Fatalf("MarshalBinary len = %d, want %d", len(data), PolyBytes)
274 }
275
276 b, err := UnmarshalBinary(data)
277 if err != nil {
278 t.Fatal(err)
279 }
280 if !Equal(a, b) {
281 t.Fatal("marshal round-trip failed")
282 }
283 }
284
285 func TestUnmarshalBinaryShort(t *testing.T) {
286 _, err := UnmarshalBinary([]byte{0, 0})
287 if err == nil {
288 t.Fatal("expected error for short data")
289 }
290 }
291
292 func TestSerializeDeserialize(t *testing.T) {
293 a := NewPoly27()
294 for i := range N {
295 a.Coeffs[i] = uint16((i * 13) % Q)
296 }
297
298 // 9-bit unsigned.
299 data := Serialize(a, 9, false)
300 b := Deserialize(data, 9, false)
301 if b == nil || !Equal(a, b) {
302 t.Fatal("9-bit unsigned round-trip failed")
303 }
304
305 // 8-bit signed (only works if coefficients are in range).
306 a2 := NewPoly27()
307 for i := range N {
308 a2.Coeffs[i] = uint16(i % 60) // < 128, fits in signed 8-bit
309 }
310 data2 := Serialize(a2, 8, true)
311 b2 := Deserialize(data2, 8, true)
312 if b2 == nil {
313 t.Fatal("8-bit signed Deserialize returned nil")
314 }
315 for i := range N {
316 if b2.Coeffs[i] != a2.Coeffs[i] {
317 t.Fatalf("8-bit signed mismatch at %d: got %d, want %d", i, b2.Coeffs[i], a2.Coeffs[i])
318 }
319 }
320
321 // Signed negative test: Q-1 is centered as -1 → abs=1.
322 a3 := NewPoly27()
323 a3.Coeffs[0] = Q - 1 // centered = -1
324 data3 := Serialize(a3, 8, true)
325 b3 := Deserialize(data3, 8, true)
326 if b3 == nil || b3.Coeffs[0] != Q-1 {
327 t.Fatalf("signed negative round-trip: got %d, want %d", b3.Coeffs[0], Q-1)
328 }
329 }
330
331 func TestSerializeDeserializeShort(t *testing.T) {
332 b := Deserialize([]byte{0}, 9, false)
333 if b != nil {
334 t.Fatal("expected nil for short data")
335 }
336 }
337