1/*
  2    Copyright 2018 0kims association
  3
  4    This file is part of zksnark javascript library.
  5
  6    zksnark javascript library is free software: you can redistribute it and/or modify
  7    it under the terms of the GNU General Public License as published by
  8    the Free Software Foundation, either version 3 of the License, or
  9    (at your option) 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
 13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 14    GNU General Public License for more details.
 15
 16    You should have received a copy of the GNU General Public License
 17    along with zksnark javascript library.  If not, see <https://www.gnu.org/licenses/>.
 18*/
 19const chai = require("chai");
 20
 21const bigInt = require("../src/bigint.js");
 22const PolField = require("../src/polfield.js");
 23const ZqField = require("../src/zqfield");
 24
 25const assert = chai.assert;
 26
 27const r  = bigInt("21888242871839275222246405745257275088548364400416034343698204186575808495617");
 28
 29describe("Polynomial field", () => {
 30    it("Should compute a multiplication", () => {
 31        const PF = new PolField(new ZqField(r));
 32
 33        const a = [bigInt(1), bigInt(2), bigInt(3)];
 34        const b = [bigInt(1), bigInt(2), bigInt(3)];
 35        const res = PF.mul(a,b);
 36
 37        assert(PF.equals(res, [bigInt(1), bigInt(4), bigInt(10), bigInt(12), bigInt(9)]));
 38    });
 39    it("Should compute a multiplication 2", () => {
 40        const PF = new PolField(new ZqField(r));
 41
 42        const a = [bigInt(5), bigInt(1)];
 43        const b = [bigInt(-5), bigInt(1)];
 44        const res = PF.mul(a,b);
 45
 46        assert(PF.equals(res, [bigInt(-25), bigInt(0), bigInt(1)]));
 47    });
 48    it("Should compute an addition", () => {
 49        const PF = new PolField(new ZqField(r));
 50
 51        const a = [bigInt(5), bigInt(1)];
 52        const b = [bigInt(-5), bigInt(1)];
 53        const res = PF.add(a,b);
 54
 55        assert(PF.equals(res, [bigInt(0), bigInt(2)]));
 56    });
 57    it("Should compute a substraction", () => {
 58        const PF = new PolField(new ZqField(r));
 59
 60        const a = [bigInt(5), bigInt(3), bigInt(4)];
 61        const b = [bigInt(5), bigInt(1)];
 62        const res = PF.sub(a,b);
 63
 64        assert(PF.equals(res, [bigInt(0), bigInt(2), bigInt(4)]));
 65    });
 66    it("Should compute reciprocal", () => {
 67        const PF = new PolField(new ZqField(r));
 68
 69        const a = [bigInt(4), bigInt(1), bigInt(-3), bigInt(-1), bigInt(2),bigInt(1), bigInt(-1), bigInt(1)];
 70        const res = PF._reciprocal(a, 3, 0);
 71
 72        assert(PF.equals(res, [bigInt(12), bigInt(15), bigInt(3), bigInt(-4), bigInt(-3), bigInt(0), bigInt(1), bigInt(1)]));
 73    });
 74    it("Should div2", () => {
 75        const PF = new PolField(new ZqField(r));
 76
 77        // x^6
 78        const a = [bigInt(0), bigInt(0), bigInt(0), bigInt(0), bigInt(0),bigInt(0), bigInt(1)];
 79        // x^5
 80        const b = [bigInt(0), bigInt(0), bigInt(0), bigInt(0), bigInt(0), bigInt(1)];
 81
 82        const res = PF._div2(6, b);
 83        assert(PF.equals(res, [bigInt(0), bigInt(1)]));
 84
 85        const res2 = PF.div(a,b);
 86        assert(PF.equals(res2, [bigInt(0), bigInt(1)]));
 87    });
 88    it("Should div", () => {
 89        const PF = new PolField(new ZqField(r));
 90
 91        const a = [bigInt(1), bigInt(2), bigInt(3), bigInt(4), bigInt(5),bigInt(6), bigInt(7)];
 92        const b = [bigInt(8), bigInt(9), bigInt(10), bigInt(11), bigInt(12), bigInt(13)];
 93
 94        const c = PF.mul(a,b);
 95        const d = PF.div(c,b);
 96
 97        assert(PF.equals(a, d));
 98    });
 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 create lagrange polynomial minmal", () => {
132        const PF = new PolField(new ZqField(r));
133
134        const points=[];
135        points.push([bigInt(1), bigInt(1)]);
136        points.push([bigInt(2), bigInt(2)]);
137        points.push([bigInt(3), bigInt(5)]);
138
139        const p=PF.lagrange(points);
140
141        for (let i=0; i<points.length; i++) {
142            const v = PF.eval(p, points[i][0]);
143            assert(PF.F.equals(v, points[i][1]));
144        }
145    });
146    it("Should create lagrange polynomial", () => {
147        const PF = new PolField(new ZqField(r));
148
149        const points=[];
150        points.push([bigInt(1), bigInt(2)]);
151        points.push([bigInt(2), bigInt(-2)]);
152        points.push([bigInt(3), bigInt(0)]);
153        points.push([bigInt(4), bigInt(453345)]);
154
155        const p=PF.lagrange(points);
156
157        for (let i=0; i<points.length; i++) {
158            const v = PF.eval(p, points[i][0]);
159            assert(PF.F.equals(v, points[i][1]));
160        }
161    });
162    it("Should test ruffini", () => {
163        const PF = new PolField(new ZqField(r));
164        const a = [bigInt(1), bigInt(2), bigInt(3), bigInt(4), bigInt(5),bigInt(6), bigInt(7)];
165
166        const b = PF.mul(a, [bigInt(-7), bigInt(1)]);
167        const c = PF.ruffini(b, bigInt(7));
168
169        assert(PF.equals(a, c));
170    });
171
172});