| /* |
| Licensed to the Apache Software Foundation (ASF) under one |
| or more contributor license agreements. See the NOTICE file |
| distributed with this work for additional information |
| regarding copyright ownership. The ASF licenses this file |
| to you under the Apache License, Version 2.0 (the |
| "License"); you may not use this file except in compliance |
| with the License. You may obtain a copy of the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, |
| software distributed under the License is distributed on an |
| "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| KIND, either express or implied. See the License for the |
| specific language governing permissions and limitations |
| under the License. |
| */ |
| |
| /* Finite Field arithmetic Fp^8 functions */ |
| |
| /* FP8 elements are of the form a+ib, where i is sqrt(sqrt(-1+sqrt(-1))) */ |
| |
| var FP8 = function(ctx) { |
| "use strict"; |
| |
| /** |
| * Creates an instance of FP8 |
| * |
| * @constructor |
| * @this {FP4} |
| * @param c FP8 / FP4 instance |
| * @param d FP4 instance |
| */ |
| var FP8 = function(c, d) { |
| if (c instanceof FP8) { |
| this.a = new ctx.FP4(c.a); |
| this.b = new ctx.FP4(c.b); |
| } else { |
| this.a = new ctx.FP4(c); |
| this.b = new ctx.FP4(d); |
| } |
| }; |
| |
| FP8.prototype = { |
| |
| /** |
| * Reduces all components of possibly unreduced FP8 mod Modulus |
| * |
| * @this {FP8} |
| */ |
| reduce: function() { |
| this.a.reduce(); |
| this.b.reduce(); |
| }, |
| |
| /** |
| * Normalises the components of an FP8 |
| * |
| * @this {FP8} |
| */ |
| norm: function() { |
| this.a.norm(); |
| this.b.norm(); |
| }, |
| |
| /** |
| * Tests for FP8 equal to zero |
| * |
| * @this {FP8} |
| */ |
| iszilch: function() { |
| return (this.a.iszilch() && this.b.iszilch()); |
| }, |
| |
| /** |
| * Tests for FP8 equal to unity |
| * |
| * @this {FP8} |
| */ |
| isunity: function() { |
| var one = new ctx.FP4(1); |
| return (this.a.equals(one) && this.b.iszilch()); |
| }, |
| |
| /** |
| * Conditional copy of FP8 number |
| * |
| * @this {FP8} |
| * @param g FP8 instance |
| * @param d copy depends on this value |
| */ |
| cmove: function(g, d) { |
| this.a.cmove(g.a, d); |
| this.b.cmove(g.b, d); |
| }, |
| |
| /** |
| * test is w real? That is in a+ib test b is zero |
| * |
| * @this {FP8} |
| */ |
| isreal: function() { |
| return this.b.iszilch(); |
| }, |
| |
| /** |
| * extract real part a |
| * |
| * @this {FP8} |
| */ |
| real: function() { |
| return this.a; |
| }, |
| |
| /** |
| * extract a from this |
| * |
| * @this {FP8} |
| */ |
| geta: function() { |
| return this.a; |
| }, |
| |
| /** |
| * extract b from this |
| * |
| * @this {FP8} |
| */ |
| getb: function() { |
| return this.b; |
| }, |
| |
| /** |
| * Tests for equality of two FP8s |
| * |
| * @this {FP8} |
| * @param x FP8 instance to compare |
| */ |
| equals: function(x) { |
| return (this.a.equals(x.a) && this.b.equals(x.b)); |
| }, |
| |
| /** |
| * Copy FP8 to another FP8 |
| * |
| * @this {FP8} |
| * @param x FP8 instance to be copied |
| */ |
| copy: function(x) { |
| this.a.copy(x.a); |
| this.b.copy(x.b); |
| }, |
| |
| /** |
| * Set FP8 to zero |
| * |
| * @this {FP8} |
| */ |
| zero: function() { |
| this.a.zero(); |
| this.b.zero(); |
| }, |
| |
| /** |
| * Set FP8 to unity |
| * |
| * @this {FP8} |
| * @param x FP8 instance to be set to one |
| */ |
| one: function() { |
| this.a.one(); |
| this.b.zero(); |
| }, |
| |
| /** |
| * Set FP8 from two FP4 values |
| * |
| * @this {FP8} |
| * @param c FP4 instance |
| * @param d FP4 instance |
| */ |
| set: function(c, d) { |
| this.a.copy(c); |
| this.b.copy(d); |
| }, |
| |
| /** |
| * Set FP8 from one FP4 value |
| * |
| * @this {FP8} |
| * @param c FP4 instance |
| */ |
| seta: function(c) { |
| this.a.copy(c); |
| this.b.zero(); |
| }, |
| |
| /** |
| * Negation of FP8 |
| * |
| * @this {FP8} |
| */ |
| neg: function() { |
| this.norm(); |
| var m = new ctx.FP4(this.a), |
| t = new ctx.FP4(0); |
| |
| m.add(this.b); |
| m.neg(); |
| t.copy(m); |
| t.add(this.b); |
| this.b.copy(m); |
| this.b.add(this.a); |
| this.a.copy(t); |
| this.norm(); |
| }, |
| |
| /** |
| * Conjugation of FP8 |
| * |
| * @this {FP8} |
| */ |
| conj: function() { |
| this.b.neg(); |
| this.norm(); |
| }, |
| |
| /** |
| * Negative conjugation of FP8 |
| * |
| * @this {FP8} |
| */ |
| nconj: function() { |
| this.a.neg(); |
| this.norm(); |
| }, |
| |
| /** |
| * addition of two FP8s |
| * |
| * @this {FP8} |
| * @param x FP8 instance |
| */ |
| add: function(x) { |
| this.a.add(x.a); |
| this.b.add(x.b); |
| }, |
| |
| /** |
| * subtraction of two FP8s |
| * |
| * @this {FP8} |
| * @param x FP8 instance |
| */ |
| sub: function(x) { |
| var m = new FP8(x); |
| m.neg(); |
| this.add(m); |
| }, |
| |
| rsub: function(x) { |
| this.neg(); |
| this.add(x); |
| }, |
| |
| /** |
| * Multiplication of an FP8 by an FP8 |
| * |
| * @this {FP8} |
| * @param s FP8 instance |
| */ |
| pmul: function(s) { |
| this.a.mul(s); |
| this.b.mul(s); |
| }, |
| |
| /** |
| * Multiplication of an FP8 by a small integer |
| * |
| * @this {FP8} |
| * @param s integer |
| */ |
| imul: function(c) { |
| this.a.imul(c); |
| this.b.imul(c); |
| }, |
| |
| /** |
| * Fast Squaring of an FP8 |
| * |
| * @this {FP8} |
| */ |
| sqr: function() { |
| var t1 = new ctx.FP4(this.a), |
| t2 = new ctx.FP4(this.b), |
| t3 = new ctx.FP4(this.a); |
| |
| t3.mul(this.b); |
| t1.add(this.b); |
| t1.norm(); |
| t2.times_i(); |
| |
| t2.add(this.a); |
| t2.norm(); |
| this.a.copy(t1); |
| |
| this.a.mul(t2); |
| |
| t2.copy(t3); |
| t2.times_i(); |
| t2.add(t3); |
| |
| t2.neg(); |
| |
| this.a.add(t2); |
| |
| this.b.copy(t3); |
| this.b.add(t3); |
| |
| this.norm(); |
| }, |
| |
| /** |
| * Full unconditional Multiplication of two FP8s |
| * |
| * @this {FP8} |
| * @param y FP8 instance, the multiplier |
| */ |
| mul: function(y) { |
| var t1 = new ctx.FP4(this.a), |
| t2 = new ctx.FP4(this.b), |
| t3 = new ctx.FP4(0), |
| t4 = new ctx.FP4(this.b); |
| |
| t1.mul(y.a); |
| t2.mul(y.b); |
| t3.copy(y.b); |
| t3.add(y.a); |
| t4.add(this.a); |
| |
| t3.norm(); |
| t4.norm(); |
| |
| t4.mul(t3); |
| |
| t3.copy(t1); |
| t3.neg(); |
| t4.add(t3); |
| |
| t3.copy(t2); |
| t3.neg(); |
| this.b.copy(t4); |
| this.b.add(t3); |
| |
| t2.times_i(); |
| this.a.copy(t2); |
| this.a.add(t1); |
| |
| this.norm(); |
| }, |
| |
| /** |
| * convert to hex string |
| * |
| * @this {FP8} |
| */ |
| toString: function() { |
| return ("[" + this.a.toString() + "," + this.b.toString() + "]"); |
| }, |
| |
| /** |
| * Inverting an FP8 |
| * |
| * @this {FP8} |
| */ |
| inverse: function() { |
| this.norm(); |
| |
| var t1 = new ctx.FP4(this.a), |
| t2 = new ctx.FP4(this.b); |
| |
| t1.sqr(); |
| t2.sqr(); |
| t2.times_i(); |
| t2.norm(); // ?? |
| t1.sub(t2); |
| t1.inverse(); |
| this.a.mul(t1); |
| t1.neg(); |
| t1.norm(); |
| this.b.mul(t1); |
| }, |
| |
| /** |
| * multiplies an FP8 instance by irreducible polynomial sqrt(1+sqrt(-1)) |
| * |
| * @this {FP8} |
| */ |
| times_i: function() { |
| var s = new ctx.FP4(this.b), |
| t = new ctx.FP4(this.a); |
| |
| s.times_i(); |
| this.b.copy(t); |
| |
| this.a.copy(s); |
| this.norm(); |
| }, |
| |
| /** |
| * multiplies an FP8 instance by irreducible polynomial (1+sqrt(-1)) |
| * |
| * @this {FP8} |
| */ |
| times_i2: function() { |
| this.a.times_i(); |
| this.b.times_i(); |
| }, |
| |
| /** |
| * Raises an FP8 to the power of the internal modulus p, using the Frobenius |
| * |
| * @this {FP8} |
| * @param f Modulus |
| */ |
| frob: function(f) { |
| var ff=new ctx.FP2(f); ff.sqr(); ff.mul_ip(); ff.norm(); |
| this.a.frob(ff); |
| this.b.frob(ff); |
| this.b.pmul(f); |
| this.b.times_i(); |
| }, |
| |
| /** |
| * Raises an FP8 to the power of a BIG |
| * |
| * @this {FP8} |
| * @param e BIG instance exponent |
| */ |
| pow: function(e) { |
| var w = new FP8(this), |
| z = new ctx.BIG(e), |
| r = new FP8(1), |
| bt; |
| w.norm(); |
| z.norm(); |
| for (;;) { |
| bt = z.parity(); |
| z.fshr(1); |
| |
| if (bt === 1) { |
| r.mul(w); |
| } |
| |
| if (z.iszilch()) { |
| break; |
| } |
| |
| w.sqr(); |
| } |
| r.reduce(); |
| |
| return r; |
| }, |
| |
| /** |
| * Calculates the XTR addition function r=w*x-conj(x)*y+z |
| * |
| * @this {FP8} |
| * @param w FP8 instance |
| * @param y FP8 instance |
| * @param z FP8 instance |
| */ |
| xtr_A: function(w, y, z) { |
| var r = new FP8(w), |
| t = new FP8(w); |
| |
| r.sub(y); |
| r.norm(); |
| r.pmul(this.a); |
| t.add(y); |
| t.norm(); |
| t.pmul(this.b); |
| t.times_i(); |
| |
| this.copy(r); |
| this.add(t); |
| this.add(z); |
| |
| this.reduce(); |
| }, |
| |
| /** |
| * Calculates the XTR doubling function r=x^2-2*conj(x) |
| * |
| * @this {FP8} |
| */ |
| xtr_D: function() { |
| var w = new FP8(this); //w.copy(this); |
| this.sqr(); |
| w.conj(); |
| w.add(w); |
| this.sub(w); |
| this.reduce(); |
| }, |
| |
| /** |
| * Calculates FP8 trace of an FP8 raised to the power of a BIG number |
| * |
| * @this {FP8} |
| * @param n Big number |
| */ |
| xtr_pow: function(n) { |
| var sf = new FP8(this); |
| sf.norm(); |
| var a = new FP8(3), |
| b = new FP8(sf), |
| c = new FP8(b), |
| t = new FP8(0), |
| r = new FP8(0), |
| par, v, nb, i; |
| |
| c.xtr_D(); |
| |
| |
| par = n.parity(); |
| v = new ctx.BIG(n); |
| v.norm(); |
| v.fshr(1); |
| |
| if (par === 0) { |
| v.dec(1); |
| v.norm(); |
| } |
| |
| nb = v.nbits(); |
| for (i = nb - 1; i >= 0; i--) { |
| if (v.bit(i) != 1) { |
| t.copy(b); |
| sf.conj(); |
| c.conj(); |
| b.xtr_A(a, sf, c); |
| sf.conj(); |
| c.copy(t); |
| c.xtr_D(); |
| a.xtr_D(); |
| } else { |
| t.copy(a); |
| t.conj(); |
| a.copy(b); |
| a.xtr_D(); |
| b.xtr_A(c, sf, t); |
| c.xtr_D(); |
| } |
| } |
| |
| if (par === 0) { |
| r.copy(c); |
| } else { |
| r.copy(b); |
| } |
| r.reduce(); |
| |
| return r; |
| }, |
| |
| /** |
| * Calculates FP8 trace of c^a.d^b, where c and d are derived from FP8 traces of FP8s |
| * |
| * @this {FP8} |
| */ |
| xtr_pow2: function(ck, ckml, ckm2l, a, b) { |
| |
| var e = new ctx.BIG(a), |
| d = new ctx.BIG(b), |
| w = new ctx.BIG(0), |
| cu = new FP8(ck), |
| cv = new FP8(this), |
| cumv = new FP8(ckml), |
| cum2v = new FP8(ckm2l), |
| r = new FP8(0), |
| t = new FP8(0), |
| f2 = 0, |
| i; |
| |
| e.norm(); |
| d.norm(); |
| |
| while (d.parity() === 0 && e.parity() === 0) { |
| d.fshr(1); |
| e.fshr(1); |
| f2++; |
| } |
| |
| while (ctx.BIG.comp(d, e) !== 0) { |
| if (ctx.BIG.comp(d, e) > 0) { |
| w.copy(e); |
| w.imul(4); |
| w.norm(); |
| |
| if (ctx.BIG.comp(d, w) <= 0) { |
| w.copy(d); |
| d.copy(e); |
| e.rsub(w); |
| e.norm(); |
| |
| t.copy(cv); |
| t.xtr_A(cu, cumv, cum2v); |
| cum2v.copy(cumv); |
| cum2v.conj(); |
| cumv.copy(cv); |
| cv.copy(cu); |
| cu.copy(t); |
| |
| } else if (d.parity() === 0) { |
| d.fshr(1); |
| r.copy(cum2v); |
| r.conj(); |
| t.copy(cumv); |
| t.xtr_A(cu, cv, r); |
| cum2v.copy(cumv); |
| cum2v.xtr_D(); |
| cumv.copy(t); |
| cu.xtr_D(); |
| } else if (e.parity() == 1) { |
| d.sub(e); |
| d.norm(); |
| d.fshr(1); |
| t.copy(cv); |
| t.xtr_A(cu, cumv, cum2v); |
| cu.xtr_D(); |
| cum2v.copy(cv); |
| cum2v.xtr_D(); |
| cum2v.conj(); |
| cv.copy(t); |
| } else { |
| w.copy(d); |
| d.copy(e); |
| d.fshr(1); |
| e.copy(w); |
| t.copy(cumv); |
| t.xtr_D(); |
| cumv.copy(cum2v); |
| cumv.conj(); |
| cum2v.copy(t); |
| cum2v.conj(); |
| t.copy(cv); |
| t.xtr_D(); |
| cv.copy(cu); |
| cu.copy(t); |
| } |
| } |
| if (ctx.BIG.comp(d, e) < 0) { |
| w.copy(d); |
| w.imul(4); |
| w.norm(); |
| |
| if (ctx.BIG.comp(e, w) <= 0) { |
| e.sub(d); |
| e.norm(); |
| t.copy(cv); |
| t.xtr_A(cu, cumv, cum2v); |
| cum2v.copy(cumv); |
| cumv.copy(cu); |
| cu.copy(t); |
| } else if (e.parity() === 0) { |
| w.copy(d); |
| d.copy(e); |
| d.fshr(1); |
| e.copy(w); |
| t.copy(cumv); |
| t.xtr_D(); |
| cumv.copy(cum2v); |
| cumv.conj(); |
| cum2v.copy(t); |
| cum2v.conj(); |
| t.copy(cv); |
| t.xtr_D(); |
| cv.copy(cu); |
| cu.copy(t); |
| } else if (d.parity() == 1) { |
| w.copy(e); |
| e.copy(d); |
| w.sub(d); |
| w.norm(); |
| d.copy(w); |
| d.fshr(1); |
| t.copy(cv); |
| t.xtr_A(cu, cumv, cum2v); |
| cumv.conj(); |
| cum2v.copy(cu); |
| cum2v.xtr_D(); |
| cum2v.conj(); |
| cu.copy(cv); |
| cu.xtr_D(); |
| cv.copy(t); |
| } else { |
| d.fshr(1); |
| r.copy(cum2v); |
| r.conj(); |
| t.copy(cumv); |
| t.xtr_A(cu, cv, r); |
| cum2v.copy(cumv); |
| cum2v.xtr_D(); |
| cumv.copy(t); |
| cu.xtr_D(); |
| } |
| } |
| } |
| r.copy(cv); |
| r.xtr_A(cu, cumv, cum2v); |
| for (i = 0; i < f2; i++) { |
| r.xtr_D(); |
| } |
| r = r.xtr_pow(d); |
| return r; |
| }, |
| |
| /* New stuff for ecp4.js */ |
| |
| /** |
| * Divide an FP8 by 2 |
| * |
| * @this {FP8} |
| */ |
| div2: function() { |
| this.a.div2(); |
| this.b.div2(); |
| }, |
| |
| /** |
| * Divide FP8 number by QNR |
| * |
| * @this {FP8} |
| */ |
| div_i: function() { |
| var u=new ctx.FP4(this.a), |
| v=new ctx.FP4(this.b); |
| u.div_i(); |
| this.a.copy(v); |
| this.b.copy(u); |
| }, |
| |
| /** |
| * Divide an FP8 by QNR twice |
| * |
| * @this {FP8} |
| */ |
| div_i2: function() { |
| this.a.div_i(); |
| this.b.div_i(); |
| }, |
| |
| /** |
| * Divide an FP8 by QNR/2 |
| * |
| * @this {FP8} |
| */ |
| div_2i: function() { |
| var u=new ctx.FP4(this.a), |
| v=new ctx.FP4(this.b); |
| u.div_2i(); |
| v.add(v); v.norm(); |
| this.a.copy(v); |
| this.b.copy(u); |
| }, |
| |
| /** |
| * Multiplication of an FP8 by an FP2 |
| * |
| * @this {FP8} |
| * @param s FP2 multiplier |
| */ |
| qmul: function(s) { |
| this.a.pmul(s); |
| this.b.pmul(s); |
| }, |
| |
| /** |
| * Multiplication of an FP8 by an FP |
| * |
| * @this {FP8} |
| * @param s FP multiplier |
| */ |
| tmul: function(s) { |
| this.a.qmul(s); |
| this.b.qmul(s); |
| }, |
| |
| /** |
| * Calculate square root of an FP8 |
| * |
| * @this {FP8} |
| */ |
| sqrt: function() { |
| if (this.iszilch()) { |
| return true; |
| } |
| var wa=new ctx.FP4(this.a), |
| ws=new ctx.FP4(this.b), |
| wt=new ctx.FP4(this.a); |
| if (ws.iszilch()) { |
| if (wt.sqrt()) { |
| this.a.copy(wt); |
| this.b.zero(); |
| } else { |
| wt.div_i(); |
| wt.sqrt(); |
| this.b.copy(wt); |
| this.a.zero(); |
| } |
| return true; |
| } |
| |
| ws.sqr(); |
| wa.sqr(); |
| ws.times_i(); |
| ws.norm(); |
| wa.sub(ws); |
| |
| ws.copy(wa); |
| if (!ws.sqrt()) { |
| return false; |
| } |
| |
| wa.copy(wt); wa.add(ws); wa.norm(); wa.div2(); |
| |
| if (!wa.sqrt()) { |
| wa.copy(wt); wa.sub(ws); wa.norm(); wa.div2(); |
| if (!wa.sqrt()) { |
| return false; |
| } |
| } |
| wt.copy(this.b); |
| ws.copy(wa); ws.add(wa); |
| ws.inverse(); |
| |
| wt.mul(ws); |
| this.a.copy(wa); |
| this.b.copy(wt); |
| |
| return true; |
| } |
| |
| }; |
| |
| return FP8; |
| }; |
| |
| if (typeof module !== "undefined" && typeof module.exports !== "undefined") { |
| module.exports = { |
| FP8: FP8 |
| }; |
| } |