src/ff.js

/*
    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.
*/

/* AMCL FF number class */

var FF = function(ctx) {
    "use strict";

    /**
      * Creates an instance of FF.
      *
      * @constructor
      * @this {FF}
      */
    var FF = function(n) {
        this.v = new Array(n);
        this.length = n;
        for (var i = 0; i < n; i++) {
            this.v[i] = new ctx.BIG(0);
        }
    };

    FF.FFLEN = ctx.config["@ML"];
    FF.P_MBITS = ctx.BIG.MODBYTES * 8;
    FF.P_OMASK = ((-1) << (FF.P_MBITS % ctx.BIG.BASEBITS));
    FF.P_FEXCESS = (1 << (ctx.BIG.BASEBITS * ctx.BIG.NLEN - FF.P_MBITS - 1));
    FF.P_TBITS = (FF.P_MBITS % ctx.BIG.BASEBITS);
    FF.FF_BITS = (ctx.BIG.BIGBITS * FF.FFLEN);
    FF.HFLEN = (FF.FFLEN / 2); /* Useful for half-size RSA private key operations */

    FF.prototype = {
        /* set to zero */

        P_EXCESS: function() {
            return ((this.v[this.length - 1].get(ctx.BIG.NLEN - 1) & FF.P_OMASK) >> (FF.P_TBITS)) + 1;
        },

        zero: function() {
            for (var i = 0; i < this.length; i++) {
                this.v[i].zero();
            }

            return this;
        },

        getlen: function() {
            return this.length;
        },

	/**
         * set to integer 
         *
         * @this {FF}
         * @param m  Integer value to be set to
         */
        set: function(m) {
            this.zero();
            this.v[0].set(0, (m & ctx.BIG.BMASK));
            this.v[0].set(1, (m >> ctx.BIG.BASEBITS));
        },

	/**
         * copy from FF b 
         *
         * @this {FF}
         * @param b  FF element to copy from
         */
        copy: function(b) {
            for (var i = 0; i < this.length; i++) {
                this.v[i].copy(b.v[i]);
            }
        },
	
	/**
         * copy from FF b 
         *
         * @this {FF}
         * @param b  FF element to copy from
         */
        rcopy: function(b) {
            for (var i = 0; i < this.length; i++) {
                this.v[i].rcopy(b[i]);
            }
        },
	
	/**
         * x=y<<n 
         *
         * @this {FF}
         */
        dsucopy: function(b) {
            for (var i = 0; i < b.length; i++) {
                this.v[b.length + i].copy(b.v[i]);
                this.v[i].zero();
            }
        },
	
	/**
         * x=y
         *
         * @this {FF}
         */
        dscopy: function(b) {
            for (var i = 0; i < b.length; i++) {
                this.v[i].copy(b.v[i]);
                this.v[b.length + i].zero();
            }
        },

	/**
         * x=y>>n 
         *
         * @this {FF}
         */
        sducopy: function(b) {
            for (var i = 0; i < this.length; i++) {
                this.v[i].copy(b.v[this.length + i]);
            }
        },
	
        one: function() {
            this.v[0].one();
            for (var i = 1; i < this.length; i++) {
                this.v[i].zero();
            }
        },
	
	/**
         * test equals 0
         *
         * @this {FF}
         */
        iszilch: function() {
            for (var i = 0; i < this.length; i++) {
                if (!this.v[i].iszilch()) {
                    return false;
                }
            }

            return true;
        },
	
	/**
         * shift right by BIGBITS-bit words
         *
         * @this {FF}
         */
        shrw: function(n) {
            for (var i = 0; i < n; i++) {
                this.v[i].copy(this.v[i + n]);
                this.v[i + n].zero();
            }
        },

	/**
         * shift left by BIGBITS-bit words
         *
         * @this {FF}
         */
        shlw: function(n) {
            for (var i = 0; i < n; i++) {
                this.v[n + i].copy(this.v[i]);
                this.v[i].zero();
            }
        },
	
	/**
         * extract last bit
         *
         * @this {FF}
         */
        parity: function() {
            return this.v[0].parity();
        },

        lastbits: function(m) {
            return this.v[0].lastbits(m);
        },

	/**
         * recursive add
         *
         * @this {FF}
         */
        radd: function(vp, x, xp, y, yp, n) {
            for (var i = 0; i < n; i++) {
                this.v[vp + i].copy(x.v[xp + i]);
                this.v[vp + i].add(y.v[yp + i]);
            }
        },

	/**
         * recursive inc
         *
         * @this {FF}
         */
        rinc: function(vp, y, yp, n) {
            for (var i = 0; i < n; i++) {
                this.v[vp + i].add(y.v[yp + i]);
            }
        },

	/**
         * recursive sub
         *
         * @this {FF}
         */
        rsub: function(vp, x, xp, y, yp, n) {
            for (var i = 0; i < n; i++) {
                this.v[vp + i].copy(x.v[xp + i]);
                this.v[vp + i].sub(y.v[yp + i]);
            }
        },

	/**
         * recursive dec
         *
         * @this {FF}
         */
        rdec: function(vp, y, yp, n) {
            for (var i = 0; i < n; i++) {
                this.v[vp + i].sub(y.v[yp + i]);
            }
        },

	/**
         * simple add
         *
         * @this {FF}
         */
        add: function(b) {
            for (var i = 0; i < this.length; i++) {
                this.v[i].add(b.v[i]);
            }
        },

	/**
         * simple sub
         *
         * @this {FF}
         */
        sub: function(b) {
            for (var i = 0; i < this.length; i++) {
                this.v[i].sub(b.v[i]);
            }
        },

	/**
         * reverse sub 
         *
         * @this {FF}
         */
        revsub: function(b) {
            for (var i = 0; i < this.length; i++) {
                this.v[i].rsub(b.v[i]);
            }
        },

	/**
         * increment/decrement by a small integer
         *
         * @this {FF}
         */
        inc: function(m) {
            this.v[0].inc(m);
            this.norm();
        },

        dec: function(m) {
            this.v[0].dec(m);
            this.norm();
        },

	/**
         * normalise - but hold any overflow in top part unless n<0 
         *
         * @this {FF}
         */
        rnorm: function(vp, n) {
            var trunc = false,
                i, carry;

            if (n < 0) { /* -v n signals to do truncation */
                n = -n;
                trunc = true;
            }

            for (i = 0; i < n - 1; i++) {
                carry = this.v[vp + i].norm();
                this.v[vp + i].xortop(carry << FF.P_TBITS);
                this.v[vp + i + 1].inc(carry);
            }
            carry = this.v[vp + n - 1].norm();

            if (trunc) {
                this.v[vp + n - 1].xortop(carry << FF.P_TBITS);
            }

            return this;
        },

        norm: function() {
            this.rnorm(0, this.length);
        },

	/**
         * shift left by one bit 
         *
         * @this {FF}
         */
        shl: function() {
            var delay_carry = 0,
                i, carry;

            for (i = 0; i < this.length - 1; i++) {
                carry = this.v[i].fshl(1);
                this.v[i].inc(delay_carry);
                this.v[i].xortop(carry << FF.P_TBITS);
                delay_carry = carry;
            }

            this.v[this.length - 1].fshl(1);
            this.v[this.length - 1].inc(delay_carry);
        },

	/**
         * shift right by one bit
         *
         * @this {FF}
         */
        shr: function() {
            var i, carry;

            for (i = this.length - 1; i > 0; i--) {
                carry = this.v[i].fshr(1);
                this.v[i - 1].ortop(carry << FF.P_TBITS);
            }

            this.v[0].fshr(1);
        },

	/**
         * Convert to Hex String 
         *
         * @this {FF}
         */
        toString: function() {
            var s = "",
                i;

            this.norm();

            for (i = this.length - 1; i >= 0; i--) {
                s += this.v[i].toString();
            }

            return s;
        },
	
	/**
         * Convert FFs to/from byte arrays
         *
         * @this {FF}
         */
        toBytes: function(b) {
            var i;

            for (i = 0; i < this.length; i++) {
                this.v[i].tobytearray(b, (this.length - i - 1) * ctx.BIG.MODBYTES);
            }
        },

	/**
         * z=x*y, t is workspace
         *
         * @this {FF}
         */
        karmul: function(vp, x, xp, y, yp, t, tp, n) {
            var nd2, d;

            if (n === 1) {
                x.v[xp].norm();
                y.v[yp].norm();
                d = ctx.BIG.mul(x.v[xp], y.v[yp]);
                this.v[vp + 1] = d.split(8 * ctx.BIG.MODBYTES);
                this.v[vp].copy(d);

                return;
            }

            nd2 = n / 2;
            this.radd(vp, x, xp, x, xp + nd2, nd2);
            this.rnorm(vp, nd2); /* Important - required for 32-bit build */
            this.radd(vp + nd2, y, yp, y, yp + nd2, nd2);
            this.rnorm(vp + nd2, nd2); /* Important - required for 32-bit build */
            t.karmul(tp, this, vp, this, vp + nd2, t, tp + n, nd2);
            this.karmul(vp, x, xp, y, yp, t, tp + n, nd2);
            this.karmul(vp + n, x, xp + nd2, y, yp + nd2, t, tp + n, nd2);
            t.rdec(tp, this, vp, n);
            t.rdec(tp, this, vp + n, n);
            this.rinc(vp + nd2, t, tp, n);
            this.rnorm(vp, 2 * n);
        },

        karsqr: function(vp, x, xp, t, tp, n) {
            var nd2, d;

            if (n === 1) {
                x.v[xp].norm();
                d = ctx.BIG.sqr(x.v[xp]);
                this.v[vp + 1].copy(d.split(8 * ctx.BIG.MODBYTES));
                this.v[vp].copy(d);

                return;
            }

            nd2 = n / 2;
            this.karsqr(vp, x, xp, t, tp + n, nd2);
            this.karsqr(vp + n, x, xp + nd2, t, tp + n, nd2);
            t.karmul(tp, x, xp, x, xp + nd2, t, tp + n, nd2);
            this.rinc(vp + nd2, t, tp, n);
            this.rinc(vp + nd2, t, tp, n);
            this.rnorm(vp + nd2, n);
        },

        karmul_lower: function(vp, x, xp, y, yp, t, tp, n) { /* Calculates Least Significant bottom half of x*y */
            var nd2;

            if (n === 1) { /* only calculate bottom half of product */
                this.v[vp].copy(ctx.BIG.smul(x.v[xp], y.v[yp]));

                return;
            }

            nd2 = n / 2;

            this.karmul(vp, x, xp, y, yp, t, tp + n, nd2);
            t.karmul_lower(tp, x, xp + nd2, y, yp, t, tp + n, nd2);
            this.rinc(vp + nd2, t, tp, nd2);
            t.karmul_lower(tp, x, xp, y, yp + nd2, t, tp + n, nd2);

            this.rinc(vp + nd2, t, tp, nd2);
            this.rnorm(vp + nd2, -nd2); /* truncate it */
        },

        karmul_upper: function(x, y, t, n) { /* Calculates Most Significant upper half of x*y, given lower part */
            var nd2;

            nd2 = n / 2;
            this.radd(n, x, 0, x, nd2, nd2);
            this.radd(n + nd2, y, 0, y, nd2, nd2);
            this.rnorm(n, nd2);
            this.rnorm(n + nd2, nd2);

            t.karmul(0, this, n + nd2, this, n, t, n, nd2); /* t = (a0+a1)(b0+b1) */
            this.karmul(n, x, nd2, y, nd2, t, n, nd2); /* z[n]= a1*b1 */
            /* z[0-nd2]=l(a0b0) z[nd2-n]= h(a0b0)+l(t)-l(a0b0)-l(a1b1) */
            t.rdec(0, this, n, n); /* t=t-a1b1  */
            this.rinc(nd2, this, 0, nd2); /* z[nd2-n]+=l(a0b0) = h(a0b0)+l(t)-l(a1b1)  */
            this.rdec(nd2, t, 0, nd2); /* z[nd2-n]=h(a0b0)+l(t)-l(a1b1)-l(t-a1b1)=h(a0b0) */
            this.rnorm(0, -n); /* a0b0 now in z - truncate it */
            t.rdec(0, this, 0, n); /* (a0+a1)(b0+b1) - a0b0 */
            this.rinc(nd2, t, 0, n);

            this.rnorm(nd2, n);
        },

	/**
         * return low part of product this*y
         *
         * @this {FF}
         */
        lmul: function(y) {
            var n = this.length,
                t = new FF(2 * n),
                x = new FF(n);

            x.copy(this);
            this.karmul_lower(0, x, 0, y, 0, t, 0, n);
        },

	/**
         * Set b=b mod c
         *
         * @this {FF}
         */
        mod: function(c) {
            var k = 0;

            this.norm();
            if (FF.comp(this, c) < 0) {
                return;
            }

            do {
                c.shl();
                k++;
            } while (FF.comp(this, c) >= 0);

            while (k > 0) {
                c.shr();

                if (FF.comp(this, c) >= 0) {
                    this.sub(c);
                    this.norm();
                }

                k--;
            }
        },

	/**
         * return this mod modulus
         *
         * @this {FF}
         * @param N Mmodulus
         * @param ND Montgomery Constant
         * @return this mod N
         */
        reduce: function(N, ND) { /* fast karatsuba Montgomery reduction */
            var n = N.length,
                t = new FF(2 * n),
                r = new FF(n),
                m = new FF(n);

            r.sducopy(this);
            m.karmul_lower(0, this, 0, ND, 0, t, 0, n);
            this.karmul_upper(N, m, t, n);
            m.sducopy(this);

            r.add(N);
            r.sub(m);
            r.norm();

            return r;
        },

        /* Set r=this mod b */
        /* this is of length - 2*n */
        /* r,b is of length - n */
	
	/**
         * Reduces a double-length FF with respect to a given modulus
         *
         * @this {FF}
         * @param b Mmodulus
         * @return this mod N
         */	
        dmod: function(b) {
            var n = b.length,
                m = new FF(2 * n),
                x = new FF(2 * n),
                r = new FF(n),
                k;

            x.copy(this);
            x.norm();
            m.dsucopy(b);
            k = ctx.BIG.BIGBITS * n;

            while (FF.comp(x, m) >= 0) {
                x.sub(m);
                x.norm();
            }

            while (k > 0) {
                m.shr();

                if (FF.comp(x, m) >= 0) {
                    x.sub(m);
                    x.norm();
                }

                k--;
            }

            r.copy(x);
            r.mod(b);

            return r;
        },

	/**
         * Set return=1/this mod p. Binary method - a<p on entry
         *
         * @this {FF}
         */	
        invmodp: function(p) {
            var n = p.length,
                u = new FF(n),
                v = new FF(n),
                x1 = new FF(n),
                x2 = new FF(n),
                t = new FF(n),
                one = new FF(n);

            one.one();
            u.copy(this);
            v.copy(p);
            x1.copy(one);
            x2.zero();

            // reduce n in here as well!
            while (FF.comp(u, one) !== 0 && FF.comp(v, one) !== 0) {
                while (u.parity() === 0) {
                    u.shr();
                    if (x1.parity() !== 0) {
                        x1.add(p);
                        x1.norm();
                    }
                    x1.shr();
                }

                while (v.parity() === 0) {
                    v.shr();
                    if (x2.parity() !== 0) {
                        x2.add(p);
                        x2.norm();
                    }
                    x2.shr();
                }

                if (FF.comp(u, v) >= 0) {
                    u.sub(v);
                    u.norm();

                    if (FF.comp(x1, x2) >= 0) {
                        x1.sub(x2);
                    } else {
                        t.copy(p);
                        t.sub(x2);
                        x1.add(t);
                    }

                    x1.norm();
                } else {
                    v.sub(u);
                    v.norm();

                    if (FF.comp(x2, x1) >= 0) {
                        x2.sub(x1);
                    } else {
                        t.copy(p);
                        t.sub(x1);
                        x2.add(t);
                    }

                    x2.norm();
                }
            }

            if (FF.comp(u, one) === 0) {
                this.copy(x1);
            } else {
                this.copy(x2);
            }
        },

	/**
         * nresidue mod m 
         *
         * @this {FF}
         */	
        nres: function(m) {
            var n = m.length,
                d;

            if (n === 1) {
                d = new ctx.DBIG(0);
                d.hcopy(this.v[0]);
                d.shl(ctx.BIG.NLEN * ctx.BIG.BASEBITS);
                this.v[0].copy(d.mod(m.v[0]));
            } else {
                d = new FF(2 * n);
                d.dsucopy(this);
                this.copy(d.dmod(m));
            }
        },

        redc: function(m, ND) {
            var n = m.length,
                d;

            if (n === 1) {
                d = new ctx.DBIG(0);
                d.hcopy(this.v[0]);
                this.v[0].copy(ctx.BIG.monty(m.v[0], (1 << ctx.BIG.BASEBITS) - ND.v[0].w[0], d));
            } else {
                d = new FF(2 * n);
                this.mod(m);
                d.dscopy(this);
                this.copy(d.reduce(m, ND));
                this.mod(m);
            }
        },

        mod2m: function(m) {
            for (var i = m; i < this.length; i++) {
                this.v[i].zero();
            }
        },

        /** 
         * U=1/a mod 2^m - Arazi & Qi
         *
         * @this {FF}
         */	
        invmod2m: function() {
            var n = this.length,
                b = new FF(n),
                c = new FF(n),
                U = new FF(n),
                t, i;

            U.zero();
            U.v[0].copy(this.v[0]);
            U.v[0].invmod2m();

            for (i = 1; i < n; i <<= 1) {
                b.copy(this);
                b.mod2m(i);
                t = FF.mul(U, b);
                t.shrw(i);
                b.copy(t);
                c.copy(this);
                c.shrw(i);
                c.mod2m(i);
                c.lmul(U);
                c.mod2m(i);

                b.add(c);
                b.norm();
                b.lmul(U);
                b.mod2m(i);

                c.one();
                c.shlw(i);
                b.revsub(c);
                b.norm();
                b.shlw(i);
                U.add(b);
            }
            U.norm();

            return U;
        },

        random: function(rng) {
            var n = this.length,
                i;

            for (i = 0; i < n; i++) {
                this.v[i].copy(ctx.BIG.random(rng));
            }

            /* make sure top bit is 1 */
            while (this.v[n - 1].nbits() < ctx.BIG.MODBYTES * 8) {
                this.v[n - 1].copy(ctx.BIG.random(rng));
            }
        },

        /** 
         * generate random x 
         *
         * @this {FF}
         */	
        randomnum: function(p, rng) {
            var n = this.length,
                d = new FF(2 * n),
                i;

            for (i = 0; i < 2 * n; i++) {
                d.v[i].copy(ctx.BIG.random(rng));
            }

            this.copy(d.dmod(p));
        },

        /** 
         * this*=y mod p
         *
         * @this {FF}
         */	
        modmul: function(y, p, nd) {
            var ex = this.P_EXCESS(),
                ey = y.P_EXCESS(),
                n = p.length,
                d;

            if ((ex + 1) >= Math.floor((FF.P_FEXCESS - 1) / (ey + 1))) {
                this.mod(p);
            }

            if (n === 1) {
                d = ctx.BIG.mul(this.v[0], y.v[0]);
                this.v[0].copy(ctx.BIG.monty(p.v[0], (1 << ctx.BIG.BASEBITS) - nd.v[0].w[0], d));
            } else {
                d = FF.mul(this, y);
                this.copy(d.reduce(p, nd));
            }
        },

        /** 
         * this*=y mod p
         *
         * @this {FF}
         */	
        modsqr: function(p, nd) {
            var ex = this.P_EXCESS(),
                n, d;

            if ((ex + 1) >= Math.floor((FF.P_FEXCESS - 1) / (ex + 1))) {
                this.mod(p);
            }
            n = p.length;

            if (n === 1) {
                d = ctx.BIG.sqr(this.v[0]);
                this.v[0].copy(ctx.BIG.monty(p.v[0], (1 << ctx.BIG.BASEBITS) - nd.v[0].w[0], d));
            } else {
                d = FF.sqr(this);
                this.copy(d.reduce(p, nd));
            }
        },

        /** 
         * this=this^e mod p using side-channel resistant Montgomery Ladder, for large e
         *
         * @this {FF}
         * @param e exponent
         * @param p modulus
         */		
        skpow: function(e, p) {
            var n = p.length,
                R0 = new FF(n),
                R1 = new FF(n),
                ND = p.invmod2m(),
                i, b;

            this.mod(p);
            R0.one();
            R1.copy(this);
            R0.nres(p);
            R1.nres(p);

            for (i = 8 * ctx.BIG.MODBYTES * n - 1; i >= 0; i--) {
                b = e.v[Math.floor(i / ctx.BIG.BIGBITS)].bit(i % ctx.BIG.BIGBITS);

                this.copy(R0);
                this.modmul(R1, p, ND);

                FF.cswap(R0, R1, b);
                R0.modsqr(p, ND);

                R1.copy(this);
                FF.cswap(R0, R1, b);
            }

            this.copy(R0);
            this.redc(p, ND);
        },

        /** 
         * this=this^e mod p using side-channel resistant Montgomery Ladder, for short e
         *
         * @this {FF}
         * @param e exponent
         * @param p modulus
         */		
        skspow: function(e, p) {
            var n = p.length,
                R0 = new FF(n),
                R1 = new FF(n),
                ND = p.invmod2m(),
                i, b;

            this.mod(p);
            R0.one();
            R1.copy(this);
            R0.nres(p);
            R1.nres(p);

            for (i = 8 * ctx.BIG.MODBYTES - 1; i >= 0; i--) {
                b = e.bit(i);
                this.copy(R0);
                this.modmul(R1, p, ND);

                FF.cswap(R0, R1, b);
                R0.modsqr(p, ND);

                R1.copy(this);
                FF.cswap(R0, R1, b);
            }
            this.copy(R0);
            this.redc(p, ND);
        },

        /** 
         * raise to an integer power - right-to-left method
         *
         * @this {FF}
         * @param e exponent
         * @param p modulus
         */		
        power: function(e, p) {
            var n = p.length,
                f = true,
                w = new FF(n),
                ND = p.invmod2m();

            w.copy(this);
            w.nres(p);

            if (e == 2) {
                this.copy(w);
                this.modsqr(p, ND);
            } else {
                for (;;) {
                    if (e % 2 == 1) {
                        if (f) {
                            this.copy(w);
                        } else {
                            this.modmul(w, p, ND);
                        }
                        f = false;
                    }
                    e >>= 1;
                    if (e === 0) {
                        break;
                    }
                    w.modsqr(p, ND);
                }
            }

            this.redc(p, ND);
        },

        /** 
         * this=this^e mod p, faster but not side channel resistant
         *
         * @this {FF}
         * @param e exponent
         * @param p modulus
         */		
        pow: function(e, p) {
            var n = p.length,
                w = new FF(n),
                ND = p.invmod2m(),
                i, b;

            w.copy(this);
            this.one();
            this.nres(p);
            w.nres(p);

            for (i = 8 * ctx.BIG.MODBYTES * n - 1; i >= 0; i--) {
                this.modsqr(p, ND);
                b = e.v[Math.floor(i / ctx.BIG.BIGBITS)].bit(i % ctx.BIG.BIGBITS);
                if (b === 1) {
                    this.modmul(w, p, ND);
                }
            }

            this.redc(p, ND);
        },

        /** 
         * double exponentiation r=x^e.y^f mod p 
         *
         * @this {FF}
         * @param e exponent
         * @param y FF instance
         * @param f exponent
         * @param p modulus
         */		
        pow2: function(e, y, f, p) {
            var n = p.length,
                xn = new FF(n),
                yn = new FF(n),
                xy = new FF(n),
                ND = p.invmod2m(),
                i, eb, fb;

            xn.copy(this);
            yn.copy(y);
            xn.nres(p);
            yn.nres(p);
            xy.copy(xn);
            xy.modmul(yn, p, ND);
            this.one();
            this.nres(p);

            for (i = 8 * ctx.BIG.MODBYTES - 1; i >= 0; i--) {
                eb = e.bit(i);
                fb = f.bit(i);
                this.modsqr(p, ND);

                if (eb == 1) {
                    if (fb == 1) {
                        this.modmul(xy, p, ND);
                    } else {
                        this.modmul(xn, p, ND);
                    }
                } else {
                    if (fb == 1) {
                        this.modmul(yn, p, ND);
                    }
                }
            }
            this.redc(p, ND);
        },

        /** 
         * Test if an FF has factor in common with integer s
         *
         * @this {FF}
         * @param s integerexponent
         * @return true or false
         */		
        cfactor: function(s) {
            var n = this.length,
                x = new FF(n),
                y = new FF(n),
                r, g;

            y.set(s);

            x.copy(this);
            x.norm();

            do {
                x.sub(y);
                x.norm();
                while (!x.iszilch() && x.parity() === 0) {
                    x.shr();
                }
            } while (FF.comp(x, y) > 0);

            g = x.v[0].get(0);
            r = FF.igcd(s, g);
            if (r > 1) {
                return true;
            }

            return false;
        }
    };

    /** 
      * compare a and b - must be normalised, and of same length
      *
      * @this {FF}
      * @param a FF number
      * @param b FF number
      * @return zero of error codetrue or false
      */		
    FF.comp = function(a, b) {
        var i, j;

        for (i = a.length - 1; i >= 0; i--) {
            j = ctx.BIG.comp(a.v[i], b.v[i]);
            if (j !== 0) {
                return j;
            }
        }

        return 0;
    };

    FF.fromBytes = function(x, b) {
        var i;

        for (i = 0; i < x.length; i++) {
            x.v[i] = ctx.BIG.frombytearray(b, (x.length - i - 1) * ctx.BIG.MODBYTES);
        }
    };

    /** 
      * in-place swapping using xor - side channel resistant - lengths must be the same
      *
      * @this {FF}
      */		
    FF.cswap = function(a, b, d) {
        var i;

        for (i = 0; i < a.length; i++) {
            a.v[i].cswap(b.v[i], d);
        }
    };

    /** 
      * z=x*y. Assumes x and y are of same length.
      *
      * @this {FF}
      */		
    FF.mul = function(x, y) {
        var n = x.length,
            z = new FF(2 * n),
            t = new FF(2 * n);

        z.karmul(0, x, 0, y, 0, t, 0, n);

        return z;
    };

    /** 
      * z=x^2
      *
      * @this {FF}
      */		
    FF.sqr = function(x) {
        var n = x.length,
            z = new FF(2 * n),
            t = new FF(2 * n);

        z.karsqr(0, x, 0, t, 0, n);

        return z;
    };

    FF.igcd = function(x, y) { /* integer GCD, returns GCD of x and y */
        var r;

        if (y === 0) {
            return x;
        }

        while ((r = x % y) !== 0) {
            x = y;
            y = r;
        }

        return y;
    };

    /** 
      * Miller-Rabin test for primality.
      *
      * @this {FF}
      * @param p FF instance to be tested
      * @param rmg an instance of a Cryptographically Secure Random Number Generator
      */		
    FF.prime = function(p, rng) {
        var n = p.length,
            s = 0,
            loop,
            d = new FF(n),
            x = new FF(n),
            unity = new FF(n),
            nm1 = new FF(n),
            sf = 4849845, /* 3*5*.. *19 */
            i, j;

        p.norm();

        if (p.cfactor(sf)) {
            return false;
        }

        unity.one();
        nm1.copy(p);
        nm1.sub(unity);
        nm1.norm();
        d.copy(nm1);

        while (d.parity() === 0) {
            d.shr();
            s++;
        }

        if (s === 0) {
            return false;
        }

        for (i = 0; i < 10; i++) {
            x.randomnum(p, rng);
            x.pow(d, p);

            if (FF.comp(x, unity) === 0 || FF.comp(x, nm1) === 0) {
                continue;
            }

            loop = false;

            for (j = 1; j < s; j++) {
                x.power(2, p);

                if (FF.comp(x, unity) === 0) {
                    return false;
                }

                if (FF.comp(x, nm1) === 0) {
                    loop = true;
                    break;
                }
            }
            if (loop) {
                continue;
            }

            return false;
        }

        return true;
    };

    return FF;
};


if (typeof module !== "undefined" && typeof module.exports !== "undefined") {
    module.exports = {
        FF: FF
    };
}