/**
 * Crypt.Barrett, a class for performing Barrett modular reduction computations in
 * JavaScript.
 *
 * Requires BigInt.js.
 *
 * Copyright 2004-2005 David Shapiro.
 *
 * You may use, re-use, abuse, copy, and modify this code to your liking, but
 * please keep this header.
 *
 * Thanks!
 * 
 * @author Dave Shapiro <dave AT ohdave DOT com>
 */ 
if (typeof Crypt == "undefined") var Crypt = {};

Crypt.Barrett = function() {this.initialize.apply(this, arguments);};
Crypt.Barrett.prototype = {
    initialize: function(m) {
        this.modulus = Crypt.BigInt.copy(m);
        this.k = Crypt.BigInt.highIndex(this.modulus) + 1;
        var b2k = new (Crypt.BigInt.construct)();
         _proxy_jslib_assign('', b2k.digits, (2 * this.k), '=', ( 1)); // b2k = b^(2k)
        this.mu = Crypt.BigInt.divide(b2k, this.modulus);
        this.bkplus1 = new (Crypt.BigInt.construct)();
         _proxy_jslib_assign('', this.bkplus1.digits, (this.k + 1), '=', ( 1)); // bkplus1 = b^(k+1)
    },
    modulo: function(x) {
        var q1 = Crypt.BigInt.divideByRadixPower(x, this.k - 1);
        var q2 = Crypt.BigInt.multiply(q1, this.mu);
        var q3 = Crypt.BigInt.divideByRadixPower(q2, this.k + 1);
        var r1 = Crypt.BigInt.moduloByRadixPower(x, this.k + 1);
        var r2term = Crypt.BigInt.multiply(q3, this.modulus);
        var r2 = Crypt.BigInt.moduloByRadixPower(r2term, this.k + 1);
        var r = Crypt.BigInt.subtract(r1, r2);
        if (r.isNeg) {
            r = Crypt.BigInt.add(r, this.bkplus1);
        }
        var rgtem = Crypt.BigInt.compare(r, this.modulus) >= 0;
        while (rgtem) {
            r = Crypt.BigInt.subtract(r, this.modulus);
            rgtem = Crypt.BigInt.compare(r, this.modulus) >= 0;
        }
        return r;
    },
    multiplyMod: function(x, y) {
        /*
         * x = this.modulo(x);
         * y = this.modulo(y);
         */
        var xy = Crypt.BigInt.multiply(x, y);
        return this.modulo(xy);
    },
    powMod: function(x, y) {
        var result = new (Crypt.BigInt.construct)();
        result.digits[0] = 1;
        var a = x;
        var k = y;
        while (true) {
            if ((k.digits[0] & 1) != 0) result = this.multiplyMod(result, a);
            k = Crypt.BigInt.shiftRight(k, 1);
            if (k.digits[0] == 0 && Crypt.BigInt.highIndex(k) == 0) break;
            a = this.multiplyMod(a, a);
        }
        return result;
    }
};
 ;
_proxy_jslib_flush_write_buffers() ;