poly.go raw
1 package gnarlring
2
3 import "git.smesh.lol/gnarl-hamadryad/crypto"
4
5 const (
6 N = crypto.GnarlN // 27
7 Q = crypto.GnarlP // 271
8 bitsPerCoeff = 9 // ceil(log2(271))
9 PolyBytes = 31 // ceil(27*9/8)
10 )
11
12 // Poly27 is a polynomial in Z_271[x]/(x^27+1). Stored as 27 uint16
13 // coefficients in [0, 271). Can be in coefficient form or NTT form.
14 type Poly27 struct {
15 Coeffs [N]uint16
16 isNTT bool
17 }
18
19 // NewPoly27 returns the zero polynomial in coefficient form.
20 func NewPoly27() *Poly27 {
21 return &Poly27{}
22 }
23
24 // Clone returns a deep copy.
25 func (p *Poly27) Clone() *Poly27 {
26 c := &Poly27{isNTT: p.isNTT}
27 c.Coeffs = p.Coeffs
28 return c
29 }
30
31 // Set copies src into p.
32 func (p *Poly27) Set(src *Poly27) {
33 p.Coeffs = src.Coeffs
34 p.isNTT = src.isNTT
35 }
36
37 // Zero sets all coefficients to zero.
38 func (p *Poly27) Zero() {
39 p.Coeffs = [N]uint16{}
40 p.isNTT = false
41 }
42
43 // IsNTT reports whether the polynomial is in NTT form.
44 func (p *Poly27) IsNTT() bool { return p.isNTT }
45
46 // --- Coefficient arithmetic (all mod 271) ---
47
48 // Add returns a + b (coefficient-wise mod 271). a and b must be in the same form.
49 func Add(a, b *Poly27) *Poly27 {
50 c := &Poly27{isNTT: a.isNTT}
51 for i := range a.Coeffs {
52 c.Coeffs[i] = addMod(a.Coeffs[i], b.Coeffs[i])
53 }
54 return c
55 }
56
57 // Sub returns a - b (coefficient-wise mod 271).
58 func Sub(a, b *Poly27) *Poly27 {
59 c := &Poly27{isNTT: a.isNTT}
60 for i := range a.Coeffs {
61 c.Coeffs[i] = subMod(a.Coeffs[i], b.Coeffs[i])
62 }
63 return c
64 }
65
66 // Neg returns -a (coefficient-wise mod 271).
67 func Neg(a *Poly27) *Poly27 {
68 c := &Poly27{isNTT: a.isNTT}
69 for i, v := range a.Coeffs {
70 if v != 0 {
71 c.Coeffs[i] = Q - v
72 }
73 }
74 return c
75 }
76
77 // ScalarMul returns s * a (coefficient-wise mod 271).
78 func ScalarMul(a *Poly27, s uint16) *Poly27 {
79 c := &Poly27{isNTT: a.isNTT}
80 ss := uint32(s % Q)
81 for i, v := range a.Coeffs {
82 c.Coeffs[i] = crypto.Mod271(uint32(v) * ss)
83 }
84 return c
85 }
86
87 func addMod(a, b uint16) uint16 {
88 s := uint32(a) + uint32(b)
89 if s >= Q {
90 s -= Q
91 }
92 return uint16(s)
93 }
94
95 func subMod(a, b uint16) uint16 {
96 if a >= b {
97 return a - b
98 }
99 return Q - b + a
100 }
101
102 // --- NTT operations ---
103
104 // NTT computes the forward NTT in-place. Delegates to crypto.NTT27.
105 func (p *Poly27) NTT() {
106 if p.isNTT {
107 return
108 }
109 crypto.NTT27(&p.Coeffs)
110 p.isNTT = true
111 }
112
113 // INTT computes the inverse NTT in-place. Delegates to crypto.INTT27.
114 func (p *Poly27) INTT() {
115 if !p.isNTT {
116 return
117 }
118 crypto.INTT27(&p.Coeffs)
119 p.isNTT = false
120 }
121
122 // --- Multiplication ---
123
124 // MulPointwise returns a · b pointwise in the NTT domain. Both must be in NTT form.
125 func MulPointwise(a, b *Poly27) *Poly27 {
126 c := &Poly27{isNTT: true}
127 for i := range a.Coeffs {
128 c.Coeffs[i] = crypto.Mod271(uint32(a.Coeffs[i]) * uint32(b.Coeffs[i]))
129 }
130 return c
131 }
132
133 // Mul returns a * b in the ring Z_271[x]/(x^27+1). Uses NTT pipeline: converts
134 // both inputs to NTT, multiplies pointwise, converts back. Returns coefficient form.
135 // Inputs are unmodified.
136 func Mul(a, b *Poly27) *Poly27 {
137 ca := a.Clone()
138 cb := b.Clone()
139 ca.NTT()
140 cb.NTT()
141 c := MulPointwise(ca, cb)
142 c.INTT()
143 return c
144 }
145
146 // --- Ring inversion ---
147
148 // Inverse returns a^{-1} in the ring Z_271[x]/(x^27+1). Uses NTT domain
149 // pointwise inversion via Fermat's little theorem. Returns nil if any
150 // NTT slot is zero (a is not invertible). a must be in coefficient form.
151 func Inverse(a *Poly27) *Poly27 {
152 c := a.Clone()
153 c.NTT()
154 for i, v := range c.Coeffs {
155 if v == 0 {
156 return nil
157 }
158 c.Coeffs[i] = crypto.InvMod271(v)
159 }
160 c.INTT()
161 return c
162 }
163
164 // --- Norm computation ---
165
166 // Norm returns the centered infinity norm: max absolute coefficient value
167 // when coefficients are represented as signed integers centered at Q/2.
168 func Norm(a *Poly27) uint16 {
169 var m uint16
170 half := uint16(Q / 2)
171 for _, v := range a.Coeffs {
172 var abs uint16
173 if v > half {
174 abs = Q - v
175 } else {
176 abs = v
177 }
178 if abs > m {
179 m = abs
180 }
181 }
182 return m
183 }
184
185 // NormSq returns the squared Euclidean norm (sum of squared centered
186 // coefficients as integers).
187 func NormSq(a *Poly27) uint64 {
188 var sum uint64
189 half := uint64(Q / 2)
190 for _, v := range a.Coeffs {
191 vc := uint64(v)
192 var abs uint64
193 if vc > half {
194 abs = uint64(Q) - vc
195 } else {
196 abs = vc
197 }
198 sum += abs * abs
199 }
200 return sum
201 }
202
203 // Dot returns the Euclidean dot product of a and b, using centered
204 // (signed) coefficient values. The result is a signed integer whose
205 // magnitude is bounded by n · Q².
206 func Dot(a, b *Poly27) int64 {
207 var sum int64
208 half := int64(Q / 2)
209 for i := range a.Coeffs {
210 ai := int64(a.Coeffs[i])
211 bi := int64(b.Coeffs[i])
212 if ai > half {
213 ai -= int64(Q)
214 }
215 if bi > half {
216 bi -= int64(Q)
217 }
218 sum += ai * bi
219 }
220 return sum
221 }
222
223 // --- Comparison ---
224
225 // Equal reports whether two polynomials have identical coefficients.
226 func Equal(a, b *Poly27) bool {
227 return a.Coeffs == b.Coeffs && a.isNTT == b.isNTT
228 }
229
230 // IsZero reports whether all coefficients are zero.
231 func IsZero(a *Poly27) bool {
232 for _, v := range a.Coeffs {
233 if v != 0 {
234 return false
235 }
236 }
237 return true
238 }
239
240 // --- Serialization ---
241
242 // Serialize packs polynomial coefficients at the given bit width using LE
243 // bitwise packing. If signed is true, coefficients are stored in two's
244 // complement (caller must ensure |centered_coeff| < 2^(bitsPerCoeff-1)).
245 func Serialize(a *Poly27, bitsPerCoeff int, signed bool) []byte {
246 totalBits := bitsPerCoeff * N
247 out := make([]byte, (totalBits+7)/8)
248
249 mask := uint32((1 << bitsPerCoeff) - 1)
250 bitPos := 0
251
252 for _, c := range a.Coeffs {
253 var v uint32
254 if signed {
255 half := uint16(Q / 2)
256 if c > half {
257 abs := uint32(Q - c)
258 v = ((^abs) + 1) & mask
259 } else {
260 v = uint32(c) & mask
261 }
262 } else {
263 v = uint32(c) & mask
264 }
265 for b := 0; b < bitsPerCoeff; b++ {
266 if v&(1<<uint(b)) != 0 {
267 out[bitPos/8] |= 1 << uint(bitPos%8)
268 }
269 bitPos++
270 }
271 }
272 return out
273 }
274
275 // Deserialize unpacks a polynomial serialized by Serialize. Returns nil if
276 // the data buffer is too short.
277 func Deserialize(data []byte, bitsPerCoeff int, signed bool) *Poly27 {
278 totalBits := bitsPerCoeff * N
279 if len(data) < (totalBits+7)/8 {
280 return nil
281 }
282
283 p := NewPoly27()
284 mask := uint32((1 << bitsPerCoeff) - 1)
285 var signBit uint32
286 if signed {
287 signBit = 1 << (bitsPerCoeff - 1)
288 }
289 bitPos := 0
290
291 for i := 0; i < N; i++ {
292 var v uint32
293 for b := 0; b < bitsPerCoeff; b++ {
294 if bitPos/8 < len(data) && data[bitPos/8]&(1<<uint(bitPos%8)) != 0 {
295 v |= 1 << uint(b)
296 }
297 bitPos++
298 }
299 v &= mask
300
301 if signed && v >= signBit {
302 abs := ((^v) + 1) & mask
303 p.Coeffs[i] = Q - uint16(abs)
304 if p.Coeffs[i] >= Q {
305 p.Coeffs[i] = 0
306 }
307 } else {
308 p.Coeffs[i] = uint16(v)
309 }
310 }
311 return p
312 }
313
314 // MarshalBinary serializes at 9 bits/coeff unsigned. Returns exactly
315 // PolyBytes (31) bytes.
316 func (p *Poly27) MarshalBinary() []byte {
317 return Serialize(p, bitsPerCoeff, false)
318 }
319
320 // UnmarshalBinary deserializes a polynomial encoded by MarshalBinary.
321 // Returns an error if the data is too short.
322 func UnmarshalBinary(data []byte) (*Poly27, error) {
323 p := Deserialize(data, bitsPerCoeff, false)
324 if p == nil {
325 return nil, errShortData
326 }
327 return p, nil
328 }
329
330 // errShortData is a sentinel for deserialization failures.
331 var errShortData = errBytes("gnarlring: data too short")
332
333 type errBytes string
334
335 func (e errBytes) Error() string { return string(e) }
336