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