snarkjs/test/pols.js
test/pols.jsRaw
1/*
2 Copyright 2018 0kims association.
3
4 This file is part of zksnark JavaScript library.
5
6 zksnark JavaScript library is a free software: you can redistribute it and/or
7 modify it under the terms of the GNU General Public License as published by the
8 Free Software Foundation, either version 3 of the License, or (at your option)
9 any later version.
10
11 zksnark JavaScript library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 more details.
15
16 You should have received a copy of the GNU General Public License along with
17 zksnark JavaScript library. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20const chai = require("chai");
21
22const bigInt = require("../src/bigint.js");
23const PolField = require("../src/polfield.js");
24const ZqField = require("../src/zqfield");
25
26const assert = chai.assert;
27
28const r = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
29
30describe("Polynomial field", () => {
31 it("Should compute a multiplication", () => {
32 const PF = new PolField(new ZqField(r));
33
34 const a = [bigInt(1), bigInt(2), bigInt(3)];
35 const b = [bigInt(1), bigInt(2), bigInt(3)];
36 const res = PF.mul(a,b);
37
38 assert(PF.equals(res, [bigInt(1), bigInt(4), bigInt(10), bigInt(12), bigInt(9)]));
39 });
40 it("Should compute a multiplication 2", () => {
41 const PF = new PolField(new ZqField(r));
42
43 const a = [bigInt(5), bigInt(1)];
44 const b = [bigInt(-5), bigInt(1)];
45 const res = PF.mul(a,b);
46
47 assert(PF.equals(res, [bigInt(-25), bigInt(0), bigInt(1)]));
48 });
49 it("Should compute an addition", () => {
50 const PF = new PolField(new ZqField(r));
51
52 const a = [bigInt(5), bigInt(1)];
53 const b = [bigInt(-5), bigInt(1)];
54 const res = PF.add(a,b);
55
56 assert(PF.equals(res, [bigInt(0), bigInt(2)]));
57 });
58 it("Should compute a substraction", () => {
59 const PF = new PolField(new ZqField(r));
60
61 const a = [bigInt(5), bigInt(3), bigInt(4)];
62 const b = [bigInt(5), bigInt(1)];
63 const res = PF.sub(a,b);
64
65 assert(PF.equals(res, [bigInt(0), bigInt(2), bigInt(4)]));
66 });
67 it("Should compute reciprocal", () => {
68 const PF = new PolField(new ZqField(r));
69
70 const a = [bigInt(4), bigInt(1), bigInt(-3), bigInt(-1), bigInt(2),bigInt(1), bigInt(-1), bigInt(1)];
71 const res = PF._reciprocal(a, 3, 0);
72
73 assert(PF.equals(res, [bigInt(12), bigInt(15), bigInt(3), bigInt(-4), bigInt(-3), bigInt(0), bigInt(1), bigInt(1)]));
74 });
75 it("Should div2", () => {
76 const PF = new PolField(new ZqField(r));
77
78 // x^6
79 const a = [bigInt(0), bigInt(0), bigInt(0), bigInt(0), bigInt(0),bigInt(0), bigInt(1)];
80 // x^5
81 const b = [bigInt(0), bigInt(0), bigInt(0), bigInt(0), bigInt(0), bigInt(1)];
82
83 const res = PF._div2(6, b);
84 assert(PF.equals(res, [bigInt(0), bigInt(1)]));
85
86 const res2 = PF.div(a,b);
87 assert(PF.equals(res2, [bigInt(0), bigInt(1)]));
88 });
89 it("Should div", () => {
90 const PF = new PolField(new ZqField(r));
91
92 const a = [bigInt(1), bigInt(2), bigInt(3), bigInt(4), bigInt(5),bigInt(6), bigInt(7)];
93 const b = [bigInt(8), bigInt(9), bigInt(10), bigInt(11), bigInt(12), bigInt(13)];
94
95 const c = PF.mul(a,b);
96 const d = PF.div(c,b);
97
98 assert(PF.equals(a, d));
99 });
100 it("Should div big/small", () => {
101 const PF = new PolField(new ZqField(r));
102
103 const a = [bigInt(1), bigInt(2), bigInt(3), bigInt(4), bigInt(5),bigInt(6), bigInt(7)];
104 const b = [bigInt(8), bigInt(9)];
105
106 const c = PF.mul(a,b);
107 const d = PF.div(c,b);
108
109 assert(PF.equals(a, d));
110 });
111 it("Should div random big", () => {
112 const PF = new PolField(new ZqField(r));
113
114 const a = [];
115 const b = [];
116 for (let i=0; i<1000; i++) a.push(bigInt(Math.floor(Math.random()*100000) -500000));
117 for (let i=0; i<900; i++) b.push(bigInt(Math.floor(Math.random()*100000) -500000));
118
119 const c = PF.mul(a,b);
120
121 const d = PF.div(c,b);
122
123 assert(PF.equals(a, d));
124 }).timeout(10000);
125 it("Should evaluate and zero", () => {
126 const PF = new PolField(new ZqField(r));
127 const p = [PF.F.neg(bigInt(2)), bigInt(1)];
128 const v = PF.eval(p, bigInt(2));
129 assert(PF.F.equals(v, bigInt(0)));
130 });
131 it("Should evaluate bigger number", () => {
132 const PF = new PolField(new ZqField(r));
133 const p = [bigInt(1), bigInt(2), bigInt(3)];
134 const v = PF.eval(p, bigInt(2));
135 assert(PF.F.equals(v, bigInt(17)));
136 });
137 it("Should create lagrange polynomial minmal", () => {
138 const PF = new PolField(new ZqField(r));
139
140 const points=[];
141 points.push([bigInt(1), bigInt(1)]);
142 points.push([bigInt(2), bigInt(2)]);
143 points.push([bigInt(3), bigInt(5)]);
144
145 const p=PF.lagrange(points);
146
147 for (let i=0; i<points.length; i++) {
148 const v = PF.eval(p, points[i][0]);
149 assert(PF.F.equals(v, points[i][1]));
150 }
151 });
152 it("Should create lagrange polynomial", () => {
153 const PF = new PolField(new ZqField(r));
154
155 const points=[];
156 points.push([bigInt(1), bigInt(2)]);
157 points.push([bigInt(2), bigInt(-2)]);
158 points.push([bigInt(3), bigInt(0)]);
159 points.push([bigInt(4), bigInt(453345)]);
160
161 const p=PF.lagrange(points);
162
163 for (let i=0; i<points.length; i++) {
164 const v = PF.eval(p, points[i][0]);
165 assert(PF.F.equals(v, points[i][1]));
166 }
167 });
168 it("Should test ruffini", () => {
169 const PF = new PolField(new ZqField(r));
170 const a = [bigInt(1), bigInt(2), bigInt(3), bigInt(4), bigInt(5),bigInt(6), bigInt(7)];
171
172 const b = PF.mul(a, [bigInt(-7), bigInt(1)]);
173 const c = PF.ruffini(b, bigInt(7));
174
175 assert(PF.equals(a, c));
176 });
177 it("Should test roots", () => {
178 const PF = new PolField(new ZqField(r));
179 let rt;
180
181
182 rt = PF.oneRoot(256, 16);
183 for (let i=0; i<8; i++) {
184 rt = PF.F.mul(rt, rt);
185 }
186 assert(rt.equals(PF.F.one));
187
188 rt = PF.oneRoot(256, 15);
189 for (let i=0; i<8; i++) {
190 rt = PF.F.mul(rt, rt);
191 }
192 assert(rt.equals(PF.F.one));
193
194 rt = PF.oneRoot(8, 3);
195 for (let i=0; i<3; i++) {
196 rt = PF.F.mul(rt, rt);
197 }
198 assert(rt.equals(PF.F.one));
199
200 rt = PF.oneRoot(8, 0);
201 assert(rt.equals(PF.F.one));
202
203 });
204 it("Should create a polynomial with values at roots with fft", () => {
205 const PF = new PolField(new ZqField(r));
206 const a = [bigInt(1), bigInt(2), bigInt(3), bigInt(4), bigInt(5),bigInt(6), bigInt(7)];
207
208 const p = PF.ifft(a);
209
210 for (let i=0; i<a.length; i++) {
211 const s = PF.F.affine(PF.eval(p, PF.oneRoot(8,i)));
212 assert(s.equals(a[i]));
213 }
214
215 });
216
217});