snarkjs/src/polfield.js
src/polfield.jsRaw
1/*
2 This library do operations on polinomials where their coefficients are in field F
3
4 The polynomial P(x) = p0 + p1 * x + p2 * x^2 + p3 * x^3, ...
5 is represented by the array [ p0, p1, p2, p3, ... ]
6 */
7
8const bigInt = require("./bigInt");
9
10class PolFieldZq {
11 constructor (F) {
12 this.F = F;
13
14 const q = this.F.q;
15 let rem = q.sub(this.F.one);
16 let s = 0;
17 while (!rem.isOdd()) {
18 s ++;
19 rem = rem.shr(1);
20 }
21
22 const five = this.F.add(this.F.add(this.F.two, this.F.two), this.F.one);
23
24 this.w = new Array(s+1);
25 this.wi = new Array(s+1);
26 this.w[s] = this.F.exp(five, rem);
27 this.wi[s] = this.F.inverse(this.w[s]);
28
29 let n=s-1;
30 while (n>=0) {
31 this.w[n] = this.F.square(this.w[n+1]);
32 this.wi[n] = this.F.square(this.wi[n+1]);
33 n--;
34 }
35
36 }
37
38 add(a, b) {
39 const m = Math.max(a.length, b.length);
40 const res = new Array(m);
41 for (let i=0; i<m; i++) {
42 res[i] = this.F.add(a[i] || this.F.zero, b[i] || this.F.zero);
43 }
44 return this.reduce(res);
45 }
46
47 double(a) {
48 return this.add(a,a);
49 }
50
51 sub(a, b) {
52 const m = Math.max(a.length, b.length);
53 const res = new Array(m);
54 for (let i=0; i<m; i++) {
55 res[i] = this.F.sub(a[i] || this.F.zero, b[i] || this.F.zero);
56 }
57 return this.reduce(res);
58 }
59
60 mulScalar(a, b) {
61 if (this.F.isZero(b)) return [];
62 if (this.F.equals(b, this.F.one)) return a;
63 const res = new Array(a.length);
64 for (let i=0; i<a.length; i++) {
65 res[i] = this.F.mul(a[i], b);
66 }
67 return res;
68 }
69
70
71
72 mul(a, b) {
73 if (a.length == 0) return [];
74 if (b.length == 0) return [];
75 if (a.length == 1) return this.mulScalar(b, a[0]);
76 if (b.length == 1) return this.mulScalar(a, b[0]);
77
78 if (b.length > a.length) {
79 [b, a] = [a, b];
80 }
81
82 if (b.length < log2(a.length)) {
83 return this.mulNormal(a,b);
84 } else {
85 return this.mulFFT(a,b);
86 }
87 }
88
89 mulNormal(a, b) {
90 let res = [];
91 b = this.affine(b);
92 for (let i=0; i<b.length; i++) {
93 res = this.add(res, this.scaleX(this.mulScalar(a, b[i]), i) );
94 }
95 return res;
96 }
97
98 mulFFT(a,b) {
99 const longestN = Math.max(a.length, b.length);
100 const bitsResult = log2(longestN-1)+2;
101 const m = 1 << bitsResult;
102 const ea = this.extend(a,m);
103 const eb = this.extend(b,m);
104
105 const ta = this._fft(ea, bitsResult, 0, 1, false);
106 const tb = this._fft(eb, bitsResult, 0, 1, false);
107
108 const tres = new Array(m);
109
110 for (let i=0; i<m; i++) {
111 tres[i] = this.F.mul(ta[i], tb[i]);
112 }
113
114 const res = this._fft(tres, bitsResult, 0, 1, true);
115
116 const twoinvm = this.F.inverse( this.F.mulScalar(this.F.one, m) );
117 const resn = new Array(m);
118 for (let i=0; i<m; i++) {
119 resn[i] = this.F.mul(res[(m-i)%m], twoinvm);
120 }
121
122 return this.reduce(this.affine(resn));
123 }
124
125
126
127 square(a) {
128 return this.mul(a,a);
129 }
130
131 scaleX(p, n) {
132 if (n==0) {
133 return p;
134 } else if (n>0) {
135 const z = new Array(n).fill(this.F.zero);
136 return z.concat(p);
137 } else {
138 if (-n >= p.length) return [];
139 return p.slice(-n);
140 }
141 }
142
143 eval(p, x) {
144 let v = this.F.zero;
145 let ix = this.F.one;
146 for (let i=0; i<p.length; i++) {
147 v = this.F.add(v, this.F.mul(p[i], ix));
148 ix = this.F.mul(ix, x);
149 }
150 return v;
151 }
152
153 lagrange(points) {
154 let sum = [];
155 for (let i=0; i<points.length; i++) {
156 let mpol = [this.F.one];
157 for (let j=0;j<points.length;j++) {
158 if (i!=j) {
159 mpol = this.mul(mpol, [this.F.neg(points[j][0]), this.F.one]);
160 }
161 }
162 const factor =
163 this.F.mul(
164 this.F.inverse(this.eval(mpol, points[i][0])),
165 points[i][1]);
166 mpol = this.mulScalar(mpol, factor);
167 sum = this.add(sum, mpol);
168 }
169 return sum;
170 }
171
172 _fft(pall, bits, offset, step) {
173
174 const n = 1 << bits;
175 if (n==1) {
176 return [ pall[offset] ];
177 }
178
179 const ndiv2 = n >> 1;
180 const p1 = this._fft(pall, bits-1, offset, step*2);
181 const p2 = this._fft(pall, bits-1, offset+step, step*2);
182
183 const out = new Array(n);
184
185 let m= this.F.one;
186 for (let i=0; i<ndiv2; i++) {
187 out[i] = this.F.add(p1[i], this.F.mul(m, p2[i]));
188 out[i+ndiv2] = this.F.sub(p1[i], this.F.mul(m, p2[i]));
189 m = this.F.mul(m, this.w[bits]);
190 }
191
192 return out;
193 }
194
195 extend(p, e) {
196 if (e == p.length) return p;
197 const z = new Array(e-p.length).fill(this.F.zero);
198
199 return p.concat(z);
200 }
201
202 reduce(p) {
203 if (p.length == 0) return p;
204 if (! this.F.isZero(p[p.length-1]) ) return p;
205 let i=p.length-1;
206 while( i>0 && this.F.isZero(p[i]) ) i--;
207 return p.slice(0, i+1);
208 }
209
210 affine(p) {
211 for (let i=0; i<p.length; i++) {
212 p[i] = this.F.affine(p[i]);
213 }
214 return p;
215 }
216
217 equals(a, b) {
218 const pa = this.reduce(this.affine(a));
219 const pb = this.reduce(this.affine(b));
220
221 if (pa.length != pb.length) return false;
222 for (let i=0; i<pb.length; i++) {
223 if (!this.F.equals(pa[i], pb[i])) return false;
224 }
225
226 return true;
227 }
228
229 _next2Power(v) {
230 v--;
231 v |= v >> 1;
232 v |= v >> 2;
233 v |= v >> 4;
234 v |= v >> 8;
235 v |= v >> 16;
236 v++;
237 return v;
238 }
239
240 toString(p) {
241 const ap = this.affine(p);
242 let S = "";
243 for (let i=ap.length-1; i>=0; i--) {
244 if (!this.F.isZero(p[i])) {
245 if (S!="") S += " + ";
246 S = S + p[i].toString(10);
247 if (i>0) {
248 S = S + "x";
249 if (i>1) {
250 S = S + "^" +i;
251 }
252 }
253 }
254 }
255 return S;
256 }
257
258
259 _reciprocal(p, bits) {
260 const k = 1 << bits;
261 if (k==1) {
262 return [ this.F.inverse(p[0]) ];
263 }
264 const np = this.scaleX(p, -k/2);
265 const q = this._reciprocal(np, bits-1);
266 const a = this.scaleX(this.double(q), 3*k/2-2);
267 const b = this.mul( this.square(q), p);
268
269 return this.scaleX(this.sub(a,b), -(k-2));
270 }
271
272 // divides x^m / v
273 _div2(m, v) {
274 const kbits = log2(v.length-1)+1;
275 const k = 1 << kbits;
276
277 const scaleV = k - v.length;
278
279 // rec = x^(k - 2) / v* x^scaleV =>
280 // rec = x^(k-2-scaleV)/ v
281 //
282 // res = x^m/v = x^(m + (2*k-2 - scaleV) - (2*k-2 - scaleV)) /v =>
283 // res = rec * x^(m - (2*k-2 - scaleV)) =>
284 // res = rec * x^(m - 2*k + 2 + scaleV)
285
286 const rec = this._reciprocal(this.scaleX(v, scaleV), kbits);
287 const res = this.scaleX(rec, m - 2*k + 2 + scaleV);
288
289 return res;
290 }
291
292 div(_u, _v) {
293 if (_u.length < _v.length) return [];
294 const kbits = log2(_v.length-1)+1;
295 const k = 1 << kbits;
296
297 const u = this.scaleX(_u, k-_v.length);
298 const v = this.scaleX(_v, k-_v.length);
299
300 const n = v.length-1;
301 let m = u.length-1;
302
303 const s = this._reciprocal(v, kbits);
304 let t;
305 if (m>2*n) {
306 t = this.sub(this.scaleX([this.F.one], 2*n), this.mul(s, v));
307 }
308
309 let q = [];
310 let rem = u;
311 let us, ut;
312 let finish = false;
313
314 while (!finish) {
315 us = this.mul(rem, s);
316 q = this.add(q, this.scaleX(us, -2*n));
317
318 if ( m > 2*n ) {
319 ut = this.mul(rem, t);
320 rem = this.scaleX(ut, -2*n);
321 m = rem.length-1;
322 } else {
323 finish = true;
324 }
325 }
326
327 return q;
328 }
329}
330
331function log2( V )
332{
333 return( ( ( V & 0xFFFF0000 ) !== 0 ? ( V &= 0xFFFF0000, 16 ) : 0 ) | ( ( V & 0xFF00FF00 ) !== 0 ? ( V &= 0xFF00FF00, 8 ) : 0 ) | ( ( V & 0xF0F0F0F0 ) !== 0 ? ( V &= 0xF0F0F0F0, 4 ) : 0 ) | ( ( V & 0xCCCCCCCC ) !== 0 ? ( V &= 0xCCCCCCCC, 2 ) : 0 ) | ( ( V & 0xAAAAAAAA ) !== 0 ) );
334}
335
336module.exports = PolFieldZq;