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 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});