[Boost-commit] svn:boost r60945 - in sandbox/xint/boost/xint: . src

Subject: [Boost-commit] svn:boost r60945 - in sandbox/xint/boost/xint: . src
From: pbristow_at_[hidden]
Date: 2010-03-30 09:57:22

Author: pbristow
Date: 2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
New Revision: 60945
URL: http://svn.boost.org/trac/boost/changeset/60945

Log:
Initial from zip in vault
Added:
   sandbox/xint/boost/xint/src/
   sandbox/xint/boost/xint/src/bit_manipulations.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/compare.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/convert.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/data_t.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/exception_blocker.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/gcd.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/integer.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/misc.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/modular.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/monty.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/operators.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/powers.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/primes.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/primitives.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/random.cpp   (contents, props changed)
   sandbox/xint/boost/xint/src/roots.cpp   (contents, props changed)
   sandbox/xint/boost/xint/xint.hpp   (contents, props changed)
   sandbox/xint/boost/xint/xint_data_t.hpp   (contents, props changed)
   sandbox/xint/boost/xint/xint_monty.hpp   (contents, props changed)
   sandbox/xint/boost/xint/xint_test.hpp   (contents, props changed)

Added: sandbox/xint/boost/xint/src/bit_manipulations.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/bit_manipulations.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,169 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the bit-manipulation functions.
+*/
+
+#include "../xint.hpp"
+#include "../xint_data_t.hpp"
+
+namespace xint {
+
+using namespace detail;
+
+bool getbit(const integer& n, size_t bit) {
+    n._throw_if_nan();
+    size_t index=bit/bits_per_digit;
+    if (index < n._get_length()) {
+        digit_t mask=(digit_t(1) << (bit % bits_per_digit));
+        return ((n._get_digit(index) & mask) != 0);
+    } else return false;
+}
+
+void setbit(integer& n, size_t bit) {
+    n._throw_if_nan();
+    n._make_unique();
+    detail::data_t *ndata=n._get_data();
+
+    size_t index=bit/bits_per_digit;
+    if (index >= n._get_length()) ndata->realloc(index+1);
+
+    digit_t mask=(digit_t(1) << (bit % bits_per_digit));
+    ndata->digits[index] |= mask;
+    ndata->skipLeadingZeros();
+}
+
+void clearbit(integer& n, size_t bit) {
+    n._throw_if_nan();
+    size_t index=bit/bits_per_digit;
+    if (index < n._get_length()) {
+        n._make_unique();
+        digit_t mask=(digit_t(1) << (bit % bits_per_digit));
+        n._get_data()->digits[index] &= ~mask;
+        n._get_data()->skipLeadingZeros();
+    }
+}
+
+size_t lowestbit(const integer& n, size_t defaultValue) {
+    if (n.sign()==0) return defaultValue;
+
+    const detail::data_t *ndata=n._get_data();
+    const digit_t *p=ndata->digits, *pe=p+ndata->mLength;
+    while (p!=pe && *p==0) ++p;
+
+    size_t index=(p - ndata->digits);
+    size_t r=(bits_per_digit * index);
+    digit_t digit=*p;
+
+    while ((digit & 0x01)==0) {
+        digit>>=1;
+        ++r;
+    }
+
+    return r;
+}
+
+size_t highestbit(const integer& n, size_t defaultValue) {
+    if (n.sign()==0) return defaultValue;
+    return static_cast<size_t>(log2(n)-1);
+}
+
+integer bitwise_and(const integer& n1, const integer& n2) {
+    n1._throw_if_nan();
+    n2._throw_if_nan();
+
+    const detail::data_t *smaller=n1._get_data(), *larger=n2._get_data();
+    if (smaller->mLength > larger->mLength) std::swap(smaller, larger);
+
+    integer r;
+    detail::data_t *rdata=r._get_data();
+    rdata->alloc(smaller->mLength);
+
+    const digit_t *s1=smaller->digits, *s1e=s1+smaller->mLength, *s2=larger->digits;
+    digit_t *t=rdata->digits;
+
+    while (s1 < s1e) *t++ = *s1++ & *s2++;
+
+    rdata->skipLeadingZeros();
+    return r;
+}
+
+integer bitwise_or(const integer& n1, const integer& n2) {
+    n1._throw_if_nan();
+    n2._throw_if_nan();
+
+    const detail::data_t *smaller=n1._get_data(), *larger=n2._get_data();
+    if (smaller->mLength > larger->mLength) std::swap(smaller, larger);
+
+    integer r;
+    detail::data_t *rdata=r._get_data();
+    rdata->alloc(larger->mLength);
+
+    const digit_t *s1=smaller->digits, *s1e=s1+smaller->mLength;
+    const digit_t *s2=larger->digits, *s2e=s2+larger->mLength;
+    digit_t *t=rdata->digits;
+
+    while (s1<s1e) *t++ = *s1++ | *s2++;
+    while (s2<s2e) *t++ = *s2++;
+
+    rdata->skipLeadingZeros();
+    return r;
+}
+
+integer bitwise_xor(const integer& n1, const integer& n2) {
+    n1._throw_if_nan();
+    n2._throw_if_nan();
+
+    const detail::data_t *smaller=n1._get_data(), *larger=n2._get_data();
+    if (smaller->mLength > larger->mLength) std::swap(smaller, larger);
+
+    integer r;
+    detail::data_t *rdata=r._get_data();
+    rdata->alloc(larger->mLength);
+
+    const digit_t *s1=smaller->digits, *s1e=s1+smaller->mLength;
+    const digit_t *s2=larger->digits, *s2e=s2+larger->mLength;
+    digit_t *t=rdata->digits;
+
+    while (s1<s1e) *t++ = *s1++ ^ *s2++;
+    while (s2<s2e) *t++ = *s2++;
+
+    rdata->skipLeadingZeros();
+    return r;
+}
+
+integer shift(const integer& n, int byBits) {
+    if (byBits > 0) return shift_left(n, byBits);
+    else return shift_right(n, -byBits);
+}
+
+integer shift_left(const integer& _n, size_t byBits) {
+    _n._throw_if_nan();
+
+    if (byBits==0) return _n;
+
+    integer n(_n);
+    n._make_unique();
+    n._get_data()->shift_left(byBits);
+    return n;
+}
+
+integer shift_right(const integer& _n, size_t byBits) {
+    _n._throw_if_nan();
+
+    if (byBits==0) return _n;
+
+    integer n(_n);
+    n._make_unique();
+    n._get_data()->shift_right(byBits);
+    return n;
+}
+
+} // namespace detail

Added: sandbox/xint/boost/xint/src/compare.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/compare.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,60 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the definition for the compare function, and the
+    comparison operators that use it.
+*/
+
+#include "../xint.hpp"
+#include "../xint_data_t.hpp"
+
+namespace xint {
+
+int compare(const integer &b1, const integer &b2, bool ignoresign) {
+    b1._throw_if_nan();
+    b2._throw_if_nan();
+
+    if (!ignoresign) {
+        int sign1=b1.sign(), sign2=b2.sign();
+        if (sign1==0 && sign2==0) return 0;
+        if (sign1==0) return -sign2;
+        if (sign2==0) return sign1;
+
+        if (sign1 != sign2) return sign1;
+        if (sign1 < 0) return compare(-b2, -b1, ignoresign);
+    }
+
+    const detail::data_t *b1data=b1._get_data();
+    const detail::data_t *b2data=b2._get_data();
+
+    int answer=0;
+    if (b1data->mLength != b2data->mLength) {
+        answer=((b1data->mLength < b2data->mLength) ? -1 : 1);
+    } else {
+        for (int x = b1data->mLength - 1; x >= 0; --x) {
+            if (b1data->digits[x] != b2data->digits[x]) {
+                answer=((b1data->digits[x] < b2data->digits[x]) ? -1 : 1);
+                break;
+            }
+        }
+    }
+
+    return answer;
+}
+
+} // namespace xint
+
+bool operator!(const xint::integer &num1) { return num1.sign()==0; }
+bool operator==(const xint::integer &num1, const xint::integer &num2) { return xint::compare(num1, num2)==0; }
+bool operator!=(const xint::integer& num1, const xint::integer& num2) { return xint::compare(num1, num2)!=0; }
+bool operator<(const xint::integer& num1, const xint::integer& num2) { return xint::compare(num1, num2)<0; }
+bool operator>(const xint::integer& num1, const xint::integer& num2) { return xint::compare(num1, num2)>0; }
+bool operator<=(const xint::integer& num1, const xint::integer& num2) { return xint::compare(num1, num2)<=0; }
+bool operator>=(const xint::integer& num1, const xint::integer& num2) { return xint::compare(num1, num2)>=0; }

Added: sandbox/xint/boost/xint/src/convert.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/convert.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,192 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the conversion functions. Note that the to<T> function is
+    not here, because it's a template function and must be defined in a header
+    file.
+
+    TODO: the to_string function could be made more efficient by using only
+    doubledigit_t-sized pieces of the integer at a time, and dividing the whole
+    thing by the total of the divisions done to get the digits. Same with the
+    from_string function.
+*/
+
+#include "../xint.hpp"
+#include "../xint_data_t.hpp"
+
+#include <vector>
+#include <algorithm>
+#include <sstream>
+
+namespace xint {
+
+using namespace detail;
+
+namespace {
+
+char nToChar(int n, bool upperCase) {
+    if (n < 10) return char(n+'0');
+    else if (upperCase) return char((n - 10) + 'A');
+    else return char((n - 10) + 'a');
+}
+
+} // namespace
+
+std::string to_string(const integer& n, size_t base, bool upperCase) {
+    if (n.nan()) return detail::nan_text;
+    if (base<2 || base>36) {
+        if (exceptions_allowed()) throw invalid_base();
+        else return std::string();
+    }
+
+    if (n.sign()==0) return "0";
+
+    std::ostringstream out;
+    if (base==16) {
+        // Special no-division version, primarily for debugging division
+        const data_t *ndata=n._get_data();
+        const digit_t *firstDigit=ndata->digits,
+            *lastDigit=firstDigit + ndata->mLength - 1;
+
+        const int bitsPerDigit=4;
+        const digit_t mask=(doubledigit_t(1) << bitsPerDigit)-1;
+
+        // Suppress any leading zeros
+        const digit_t *d=lastDigit;
+        int digitShift=(bits_per_digit - bitsPerDigit);
+        while (digitShift >= 0 && ((*d >> digitShift) & mask) == 0)
+            digitShift -= bitsPerDigit;
+
+        do {
+            while (digitShift >= 0) {
+                out << nToChar((*d >> digitShift) & mask, upperCase);
+                digitShift -= bitsPerDigit;
+            }
+
+            digitShift=(bits_per_digit - bitsPerDigit);
+        } while (d-- != firstDigit);
+
+        std::string r(n.sign() < 0 ? std::string("-")+out.str() : out.str());
+        return r;
+    } else {
+        const integer shift=base;
+        std::pair<integer, integer> a=std::make_pair(n, integer::zero());
+        a.first._set_negative(false);
+
+        integer r;
+        while (a.first.sign()!=0) {
+            a=divide_r(a.first, shift);
+            out << nToChar(a.second._get_digit(0), upperCase);
+        }
+
+        if (n.sign() < 0) out << '-';
+
+        std::string rval=out.str();
+        std::reverse(rval.begin(), rval.end());
+        return rval;
+    }
+}
+
+integer from_string(const std::string& str, size_t base) {
+    if (str==detail::nan_text) return integer(not_a_number());
+
+    bool negate=false;
+    const char *c=str.c_str();
+    if (*c=='+') ++c;
+    else if (*c=='-') { negate=true; ++c; }
+
+    if (base==autobase) {
+        if (*c=='0') {
+            ++c;
+            if (*c=='x' || *c=='X') {
+                ++c;
+                base=16;
+            } else base=8;
+        } else base=10;
+    }
+
+    if (base<2 || base>36) {
+        if (exceptions_allowed()) throw invalid_base();
+        else return integer(not_a_number());
+    }
+
+    if (*c==0) {
+        if (exceptions_allowed()) throw invalid_digit("No valid digits");
+        else return integer(not_a_number());
+    }
+
+    const integer shift(base);
+
+    integer r;
+    while (*c) {
+        unsigned int digit;
+        if (*c>='0' && *c<='9') digit=*c-'0';
+        else if (*c>='A' && *c<='Z') digit=*c-'A'+10;
+        else if (*c>='a' && *c<='z') digit=*c-'a'+10;
+        else {
+            if (exceptions_allowed()) throw invalid_digit("encountered non-alphanumeric character in string");
+            else return integer(not_a_number());
+        }
+
+        if (digit >= base) {
+            if (exceptions_allowed()) throw invalid_digit("encountered digit greater than base allows");
+            else return integer(not_a_number());
+        }
+
+        r = (r * shift) + digit;
+        ++c;
+    }
+    r._set_negative(negate);
+    return r;
+}
+
+integer from_binary(const std::string& str) {
+    const size_t bytesPerDigit=sizeof(digit_t);
+    const size_t bitsPerByte=std::numeric_limits<unsigned char>::digits;
+
+    integer r;
+    detail::data_t *rdata=r._get_data();
+    rdata->alloc((str.length() + bytesPerDigit - 1)/bytesPerDigit);
+    digit_t *p=rdata->digits;
+
+    unsigned char *s=(unsigned char *)str.data(), *se=s+str.length();
+    while (s<se) {
+        digit_t d=0;
+        for (size_t i=0; i<bytesPerDigit && s<se; ++i)
+            d |= (digit_t(*s++) << (i * bitsPerByte));
+        *p++=d;
+    }
+    rdata->skipLeadingZeros();
+    return r;
+}
+
+std::string to_binary(const integer& n) {
+    n._throw_if_nan();
+
+    const size_t bytesPerDigit=sizeof(digit_t);
+    const size_t bitsPerByte=std::numeric_limits<unsigned char>::digits;
+    std::vector<unsigned char> temp;
+    temp.reserve(n._get_length() * bytesPerDigit);
+
+    const detail::data_t *ndata=n._get_data();
+    const digit_t *p=ndata->digits, *pe=p+n._get_length();
+    while (p != pe) {
+        digit_t d(*p++);
+        for (size_t i=0; i<bytesPerDigit; ++i) {
+            temp.push_back((unsigned char)(d));
+            d >>= bitsPerByte;
+        }
+    }
+    while (!temp.empty() && temp.back()==0) temp.pop_back();
+    char *c=(char*)&temp[0];
+    return std::string(c, c+temp.size());
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/src/data_t.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/data_t.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,312 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the definitions for data_t member functions.
+*/
+
+#include "../xint.hpp"
+#include "../xint_data_t.hpp"
+
+#include <cassert>
+
+namespace xint {
+namespace detail {
+
+data_t::data_t(digit_t initial1, digit_t initial2, digit_t initial3) {
+    mLength=1;
+    mAllocated=QuickDigits::count;
+    digits=mQuickDigits;
+    digits[0]=initial1;
+    digits[1]=initial2;
+    digits[2]=initial3;
+    mCopies=0;
+    mIsNegative=false;
+}
+
+data_t::data_t(data_t *c) {
+    mLength=c->mLength;
+    if (c->digits == c->mQuickDigits) {
+        digits=mQuickDigits;
+        mAllocated=QuickDigits::count;
+    } else {
+        try {
+            mAllocated=mLength;
+            #ifdef XINT_SECURE
+                digits=new digit_t[mAllocated];
+            #else
+                mStorage.resize(mAllocated, 0);
+                digits=&mStorage[0];
+            #endif
+        } catch (std::bad_alloc&) {
+            throw std::overflow_error("Out of memory allocating xint::integer");
+        }
+    }
+    memcpy(digits, c->digits, mLength*sizeof(digit_t));
+
+    mCopies=0;
+    mIsNegative=c->mIsNegative;
+}
+
+#ifdef XINT_SECURE
+data_t::~data_t() {
+    zero(mQuickDigits, QuickDigits::count);
+    if (digits != mQuickDigits) {
+        zero(digits, mAllocated);
+        delete[] digits;
+    }
+}
+#endif
+
+void data_t::skipLeadingZeros() {
+    digit_t *d=digits+mLength-1;
+    while (d>digits && *d==0) --d;
+    mLength=int((d-digits)+1);
+    if (mLength==1 && digits[0]==0) mIsNegative=false; // Zero isn't negative
+}
+
+void data_t::quickset(digit_t d1, digit_t d2, digit_t d3) {
+    assert(mCopies==1);
+
+    mLength=3;
+    digits[0]=d1;
+    digits[1]=d2;
+    digits[2]=d3;
+    mIsNegative=false;
+    skipLeadingZeros();
+}
+
+void data_t::alloc(int newcount, bool copydigits) {
+    if (digits==mQuickDigits && newcount<=QuickDigits::count) {
+        if (!copydigits) zero(digits, QuickDigits::count);
+        else zero(digits+mLength, (newcount-mLength));
+        mLength=newcount;
+    } else if (newcount < mAllocated) {
+        if (copydigits) {
+            if (newcount>mLength) zero(digits+mLength, newcount-mLength);
+            mLength=newcount;
+        } else {
+            mLength=newcount;
+            zero(digits, mLength);
+        }
+    } else {
+        #ifdef XINT_SECURE
+            int e=newcount;
+            newcount=1;
+            while (newcount < e) newcount <<= 1;
+        #endif
+
+        if (digits==mQuickDigits && copydigits) {
+            try {
+                #ifdef XINT_SECURE
+                    digits=new digit_t[newcount];
+                #else
+                    mStorage.resize(newcount);
+                    digits=&mStorage[0];
+                #endif
+            } catch (std::bad_alloc&) {
+                digits=mQuickDigits; // Might allow for recovery in some cases
+                throw std::overflow_error("Out of memory allocating xint::integer");
+            }
+
+            memcpy(digits, mQuickDigits, mLength*sizeof(digit_t));
+            zero(digits+mLength, newcount-mLength);
+        } else {
+            #ifdef XINT_SECURE
+                digit_t *newDigits=0;
+                try {
+                    newDigits=new digit_t[newcount];
+                } catch (std::bad_alloc&) {
+                    throw std::overflow_error("Out of memory allocating xint::integer");
+                }
+
+                if (copydigits) {
+                    memcpy(newDigits, digits, mLength*sizeof(digit_t));
+                    zero(newDigits+mLength, newcount-mLength);
+                } else zero(newDigits, newcount);
+
+                if (digits!=mQuickDigits) {
+                    zero(digits, mAllocated);
+                    delete[] digits;
+                }
+                digits=newDigits;
+            #else
+                try {
+                    mStorage.resize(newcount);
+                } catch (std::bad_alloc&) {
+                    throw std::overflow_error("Out of memory allocating xint::integer");
+                }
+                digits=&mStorage[0];
+                if (!copydigits) zero(digits, newcount);
+            #endif
+        }
+        mLength=mAllocated=newcount;
+    }
+}
+
+void data_t::copy(const data_t *c, int extraDigits) {
+    alloc(c->mLength+extraDigits);
+
+    mLength=c->mLength;
+    if (c->mLength==1) *digits = *c->digits;
+    else memcpy(digits, c->digits, mLength*sizeof(digit_t));
+
+    mIsNegative=c->mIsNegative;
+
+    // Deliberately doesn't call skipLeadingZeros().
+}
+
+void data_t::zero(digit_t *p, size_t count) {
+    digit_t *pe=p+count;
+    while (p<pe) *p++=0;
+}
+
+void data_t::invert() {
+    assert(mCopies==1);
+
+    mIsNegative=!mIsNegative;
+
+    digit_t *d=digits, *e=d+mLength;
+    while (d<e) {
+        *d=static_cast<digit_t>(digit_overflowbit - 1 - *d);
+        ++d;
+    }
+
+    d=digits;
+    while (d<e) {
+        doubledigit_t w=(*d)+1;
+        (*d++)=static_cast<digit_t>(w);
+        if (w<digit_overflowbit) break;
+    }
+
+    skipLeadingZeros();
+}
+
+void data_t::negate() {
+    assert(mCopies==1);
+
+    // If it's zero, don't change the sign
+    if (mLength>1 || digits[0]!=0) mIsNegative=!mIsNegative;
+}
+
+void data_t::add(const data_t& addend) {
+    assert(mCopies==1);
+    assert(mLength >= addend.mLength);
+
+    // The answer to any addition problem contains, at most, one digit more
+    // than the largest addend.
+    realloc(mLength+1);
+
+    // Now add the digits, starting at the least-significant digit.
+    digit_t carry=0;
+    int x=0;
+    for (; x<addend.mLength; ++x) {
+        doubledigit_t t=doubledigit_t(digits[x])+addend.digits[x]+carry;
+        if (t>=digit_overflowbit) { carry=1; t-=digit_overflowbit; } else carry=0;
+        digits[x]=static_cast<digit_t>(t);
+    }
+
+    while (carry) {
+        doubledigit_t t=doubledigit_t(digits[x])+1;
+        if (t>=digit_overflowbit) { carry=1; t-=digit_overflowbit; } else carry=0;
+        digits[x]=static_cast<digit_t>(t);
+        ++x;
+    }
+
+    skipLeadingZeros();
+}
+
+void data_t::subtract(const data_t& subtrahend) {
+    assert(mCopies==1);
+    assert(mLength >= subtrahend.mLength);
+
+    // For subtraction, the answer will always be less than or equal to the
+    // size of the longest operand, so we've already got enough room.
+
+    // Now subtract the digits, starting at the least-significant one.
+    int borrow=0, x;
+    doubledigit_t t;
+    for (x=0; x<subtrahend.mLength; ++x) {
+        t=(digits[x]+digit_overflowbit)-subtrahend.digits[x]-borrow;
+        if (t<digit_overflowbit) borrow=1; else { borrow=0; t-=digit_overflowbit; }
+        digits[x]=static_cast<digit_t>(t);
+    }
+
+    for (; x<mLength && borrow; ++x) {
+        t=(digits[x]+digit_overflowbit)-borrow;
+        if (t<digit_overflowbit) borrow=1; else { borrow=0; t-=digit_overflowbit; }
+        digits[x]=static_cast<digit_t>(t);
+    }
+
+    if (borrow) negate();
+    skipLeadingZeros();
+}
+
+void data_t::shift_left(int byBits) {
+    assert(mCopies==1);
+    assert(byBits>0);
+
+    int bytes=byBits / bits_per_digit, bits=byBits % bits_per_digit;
+    int oldLength=mLength;
+
+    realloc(mLength+bytes+1);
+
+    if (bits != 0) {
+        // Handle both bits and bytes in one pass
+        digit_t *s=digits+oldLength-1, *t=s+bytes+1;
+
+        *t-- = *s >> (bits_per_digit - bits);
+        while (s > digits) {
+            *t = (*s-- << bits);
+            *t-- |= (*s >> (bits_per_digit - bits));
+        }
+        *t = (*s << bits);
+
+        if (bytes != 0) memset(digits, 0, sizeof(digit_t) * bytes);
+    } else if (bytes != 0) {
+        memmove(digits+bytes, digits, sizeof(digit_t) * oldLength);
+        memset(digits, 0, sizeof(digit_t) * bytes);
+    }
+    skipLeadingZeros();
+}
+
+void data_t::shift_right(int byBits) {
+    assert(mCopies==1);
+    assert(byBits>0);
+
+    int bytes=byBits / bits_per_digit, bits=byBits % bits_per_digit,
+        bits2 = bits_per_digit - bits;
+
+    if (bytes >= mLength) {
+        // Right-shift it into oblivion.
+        mLength=1;
+        *digits=0;
+    } else if (bits != 0) {
+        // Handle both bits and bytes in one pass
+        digit_t *t=digits, *s=digits+bytes, *se=digits+mLength-1;
+        while (s!=se) {
+            *t = (*s++ >> bits);
+            *t++ |= (*s << bits2);
+        }
+        *t = (*s >> bits);
+        if (bytes != 0) {
+            memset(digits+mLength-bytes, 0, sizeof(digit_t) * bytes);
+            mLength-=bytes;
+        }
+        skipLeadingZeros();
+    } else if (bytes != 0) {
+        memmove(digits, digits + bytes, sizeof(digit_t) * (mLength - bytes));
+        memset(digits + mLength - bytes, 0, sizeof(digit_t) * bytes);
+        mLength-=bytes;
+        skipLeadingZeros();
+    }
+}
+
+} // namespace detail
+} // namespace xint

Added: sandbox/xint/boost/xint/src/exception_blocker.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/exception_blocker.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,67 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file holds definitions for the exception blocker classes and functions.
+*/
+
+#include "../xint.hpp"
+
+#ifdef XINT_THREADSAFE
+    #include <boost/thread.hpp>
+#endif
+
+namespace xint {
+namespace {
+
+#ifdef XINT_THREADSAFE
+    boost::thread_specific_ptr<bool> allowed;
+
+    struct EBlockerToken: public detail::token {
+        EBlockerToken(bool newAllowState) {
+            if (allowed.get()==0) allowed.reset(new bool(true));
+            mOldState=*allowed;
+            *allowed=newAllowState;
+        }
+        ~EBlockerToken() { *allowed=mOldState; }
+
+        bool mOldState;
+    };
+#else
+    bool allowed=true;
+
+    struct EBlockerToken: public detail::token {
+        EBlockerToken(bool newAllowState): mOldState(allowed) { allowed=newAllowState; }
+        ~EBlockerToken() { allowed=mOldState; }
+
+        bool mOldState;
+    };
+#endif
+
+} // namespace
+
+bool exceptions_allowed() {
+    #ifdef XINT_THREADSAFE
+        // Defaults to true
+        return (allowed.get()==0 || *allowed==true);
+    #else
+        return allowed;
+    #endif
+}
+
+token block_exceptions() {
+    return token(new EBlockerToken(false));
+}
+
+token allow_exceptions() {
+    return token(new EBlockerToken(true));
+}
+
+} // namespace xint
+

Added: sandbox/xint/boost/xint/src/gcd.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/gcd.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,101 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the Greatest Common Denominator function.
+*/
+
+#include "../xint.hpp"
+
+namespace xint {
+
+namespace {
+
+struct gcd_core {
+    gcd_core(const integer& n, const integer& m): u1(integer::one()),
+        u2(integer::zero()), u3(n)
+    {
+        integer t1=m, t2=n-integer::one(), t3=m;
+        do {
+            do {
+                if (u3.even()) {
+                    if (u1.odd() || u2.odd()) { u1+=m; u2+=n; }
+                    u1 >>= 1;
+                    u2 >>= 1;
+                    u3 >>= 1;
+                }
+
+                if (t3.even() || u3 < t3) {
+                    // Swap the u's with the t's
+                    std::swap(u1, t1);
+                    std::swap(u2, t2);
+                    std::swap(u3, t3);
+                }
+            } while (u3.even());
+
+            while (u1 < t1 || u2 < t2) { u1+=m; u2+=n; }
+            u1-=t1; u2-=t2; u3-=t3;
+        } while (t3 > 0);
+
+        while (u1 >= m && u2 >= n) { u1-=m; u2-=n; }
+    }
+
+    integer u1, u2, u3;
+};
+
+} // namespace
+
+integer gcd(const integer& num1, const integer& num2) {
+    num1._throw_if_nan();
+    num2._throw_if_nan();
+
+    integer n(abs(num1)), m(abs(num2));
+
+    size_t k=0;
+    while (n.even() && m.even()) { ++k; n >>= 1; m >>= 1; }
+
+    gcd_core core(n, m);
+
+    if (core.u3.sign() != 0) return core.u3 << k;
+    return integer::one() << k;
+}
+
+integer lcm(const integer& num1, const integer& num2) {
+    if (num1.sign() == 0 || num2.sign() == 0) return integer::zero();
+    return abs(num1 * num2) / gcd(num1, num2);
+}
+
+integer invmod(const integer& n, const integer& m) {
+    // Calculates the modular inverse of n mod m, or (n^(-1)) mod m
+    // Defined as b, where n*b corresponds to 1 (mod m)
+    if (m < integer::one()) {
+        if (exceptions_allowed()) throw invalid_modulus();
+        else return integer(not_a_number());
+    }
+
+    if (n.sign() < 0) {
+        integer _n(n);
+        _n._set_negative(false);
+
+        integer nn=invmod(_n, m);
+        if (nn.nan()) return nn;
+
+        nn._set_negative(true);
+        return nn + m;
+    }
+
+    if (n.even() && m.even()) return integer(not_a_number()); // GCD(x,y)!=1, no inverse possible.
+
+    gcd_core core(n, m);
+
+    if (core.u3 != integer::one()) return integer(not_a_number()); // GCD(x,y)!=1, no inverse possible.
+    return core.u1;
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/src/integer.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/integer.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,222 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the definitions for the integer member functions.
+*/
+
+#include "../xint.hpp"
+#include "../xint_data_t.hpp"
+
+namespace xint {
+
+const integer *integer::cZero=0, *integer::cOne=0;
+const std::string detail::nan_text("#NaN#");
+
+integer::integer() {
+    _init();
+}
+
+integer::integer(const integer& b) {
+    if (b.nan()) data=0;
+    else _init(b);
+}
+
+integer::integer(const std::string& str, size_t base) {
+    _init(from_string(str, base));
+}
+
+integer::integer(const not_a_number&) {
+    data=0;
+}
+
+integer::~integer() {
+    _detach();
+}
+
+void integer::_init(detail::digit_t init) {
+    try {
+        data=new detail::data_t(init);
+    } catch (std::bad_alloc&) {
+        throw std::overflow_error("Out of memory allocating xint::integer");
+    }
+    _attach();
+}
+
+void integer::_init(const integer &c) {
+    #ifdef XINT_THREADSAFE
+        data=(c.data ? new data_t(c.data) : 0);
+    #else
+        data=c.data;
+    #endif
+    _attach();
+}
+
+void integer::_init(boost::uintmax_t n) {
+    static int bits=std::numeric_limits<boost::uintmax_t>::digits;
+    static int maxDigits=(bits+detail::bits_per_digit-1)/detail::bits_per_digit;
+
+    try {
+        data=new detail::data_t;
+    } catch (std::bad_alloc&) {
+        throw std::overflow_error("Out of memory allocating xint::integer");
+    }
+    _attach();
+
+    data->alloc(maxDigits);
+    for (int x=0; n != 0; ++x) {
+        data->digits[x]=detail::digit_t(n & detail::digit_mask);
+        n >>= detail::bits_per_digit;
+    }
+    data->skipLeadingZeros();
+}
+
+void integer::_attach() {
+    if (data) data->attach();
+}
+
+void integer::_detach() {
+    if (data && data->detach()) delete data;
+}
+
+void integer::_make_unique() {
+    try {
+        if (data && data->mCopies > 1) {
+            detail::data_t *newstore=new detail::data_t(data);
+            _detach();
+            data=newstore;
+            _attach();
+        }
+    } catch (std::bad_alloc&) {
+        throw std::overflow_error("Out of memory allocating xint::integer");
+    }
+}
+
+void integer::_set_negative(bool negative) {
+    if (negative != (sign() < 0)) *this=negate(*this);
+}
+
+bool integer::odd() const {
+    _throw_if_nan();
+    return ((_get_digit(0) & 0x01)==1);
+}
+
+bool integer::even() const {
+    _throw_if_nan();
+    return ((_get_digit(0) & 0x01)==0);
+}
+
+int integer::sign() const {
+    _throw_if_nan();
+    if (data->mIsNegative) return -1;
+    if (_get_length()==1 && _get_digit(0)==0) return 0;
+    return 1;
+}
+
+bool integer::nan() const {
+    return (data==0);
+}
+
+size_t integer::hex_digits() const {
+    _throw_if_nan();
+    size_t bits=log2(*this);
+    return (bits+3)/4; // Four bits per hex digit, rounded up
+}
+
+integer& integer::operator+=(const integer& addend) {
+    if ((sign() < 0) == (addend.sign() < 0)
+        && data->mLength >= addend.data->mLength)
+    {
+        // Fast in-place add
+        _make_unique();
+        data->add(addend.data);
+    } else {
+        // This works for all cases
+        *this=add(*this, addend);
+    }
+    return *this;
+}
+
+integer& integer::operator-=(const integer& subtrahend) {
+    if (sign() >= 0 && subtrahend.sign() >= 0 && *this >= subtrahend) {
+        // Fast in-place subtract
+        _make_unique();
+        data->subtract(subtrahend.data);
+    } else {
+        // This works for all cases
+        *this=subtract(*this, subtrahend);
+    }
+    return *this;
+}
+
+integer& integer::operator=(const integer &c) {
+    _detach();
+    #ifdef XINT_THREADSAFE
+        data=(c.data ? new data_t(c.data) : 0);
+    #else
+        data=c.data;
+    #endif
+    _attach();
+    return *this;
+}
+
+integer& integer::operator*=(const integer& b) { *this=multiply(*this, b); return *this; }
+integer& integer::operator/=(const integer& b) { *this=divide(*this, b); return *this; }
+integer& integer::operator%=(const integer& b) { *this=mod(*this, b); return *this; }
+
+integer& integer::operator++() { *this += one(); return *this; }
+integer& integer::operator--() { *this -= one(); return *this; }
+integer  integer::operator++(int) { integer s=*this; *this += one(); return s; }
+integer  integer::operator--(int) { integer s=*this; *this -= one(); return s; }
+
+integer  integer::operator<<(size_t shift) const { return shift_left(*this, shift); }
+integer  integer::operator>>(size_t shift) const { return shift_right(*this, shift); }
+integer& integer::operator&=(const integer& n) { *this=bitwise_and(*this, n); return *this; }
+integer& integer::operator|=(const integer& n) { *this=bitwise_or(*this, n); return *this; }
+integer& integer::operator^=(const integer& n) { *this=bitwise_xor(*this, n); return *this; }
+
+integer& integer::operator<<=(size_t shift) {
+    if (shift>0) {
+        _make_unique();
+        data->shift_left(shift);
+    }
+    return *this;
+}
+
+integer& integer::operator>>=(size_t shift) {
+    if (shift>0) {
+        _make_unique();
+        data->shift_right(shift);
+    }
+    return *this;
+}
+
+const integer& integer::zero() {
+    if (cZero==0) cZero=new integer(0);
+    return *cZero;
+}
+
+const integer& integer::one() {
+    if (cOne==0) cOne=new integer(1);
+    return *cOne;
+}
+
+detail::digit_t integer::_get_digit(size_t index) const {
+    return data->digits[index];
+}
+
+size_t integer::_get_length() const {
+    return data->mLength;
+}
+
+void integer::_throw_if_nan() const {
+    if (nan()) throw not_a_number();
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/src/misc.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/misc.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,48 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the definitions for functions that don't fall into any
+    of the other categories.
+*/
+
+#include "../xint.hpp"
+
+namespace xint {
+
+bool opt_secure_mode() {
+    #ifdef XINT_SECURE
+        return true;
+    #else
+        return false;
+    #endif
+}
+
+bool opt_thread_safe() {
+    #ifdef XINT_THREADSAFE
+        return true;
+    #else
+        return false;
+    #endif
+}
+
+size_t log2(const integer& n) {
+    n._throw_if_nan();
+
+    size_t r=detail::bits_per_digit * n._get_length();
+    detail::digit_t mask=detail::digit_hibit, d=n._get_digit(n._get_length()-1);
+    while (mask!=0) {
+        if ((mask & d)!=0) break;
+        mask>>=1;
+        --r;
+    }
+    return r;
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/src/modular.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/modular.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,75 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the basic modular math functions, except invmod, which
+    is in gcd.cpp to share gcd_core.
+*/
+
+#include "../xint.hpp"
+#include "../xint_monty.hpp"
+
+namespace xint {
+
+integer mod(const integer& n, const integer& modBy) {
+    integer r=divide_r(n, modBy).second;
+    if (r.sign() < 0) r+=abs(modBy);
+    return r;
+}
+
+integer mulmod(const integer& n, const integer& by, const integer& modulus) {
+    return mod(n * by, modulus);
+}
+
+integer sqrmod(const integer& n, const integer& modulus) {
+    return mod(sqr(n), modulus);
+}
+
+integer powmod(const integer& n, const integer& exponent, const integer&
+    modulus, bool noMontgomery)
+{
+    if (modulus < integer::one()) {
+        if (exceptions_allowed()) throw invalid_modulus();
+        else return integer(not_a_number());
+    }
+    if (exponent.sign()==0) return integer::one();
+
+    bool neg=(n.sign() < 0 && exponent.odd());
+
+    integer answer(integer::one());
+
+    // Montgomery's method is often noticeably faster, but only works if the
+    // modulus is odd.
+    if (modulus.odd() && !noMontgomery) {
+        answer=montgomeryPowerMod(abs(n) % modulus, abs(exponent), modulus);
+    } else {
+        integer p(abs(n));
+
+        int length=exponent._get_length(), lastBitCount=0;
+        detail::digit_t ee(exponent._get_digit(length-1));
+        while (ee != 0) { ee >>= 1; ++lastBitCount; }
+
+        for (int eIndex=0; eIndex < length; ++eIndex) {
+            detail::digit_t e(exponent._get_digit(eIndex));
+
+            int bitCount(eIndex == length-1 ? lastBitCount :
+                detail::bits_per_digit);
+            while (bitCount-- > 0) {
+                if (e & 0x01) answer=mulmod(answer, p, modulus);
+                p=sqrmod(p, modulus);
+                e >>= 1;
+            }
+        }
+    }
+
+    answer._set_negative(neg);
+    return answer;
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/src/monty.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/monty.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,268 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the definitions for functions based on the Montgomery
+    reduction. Used for an extra-fast powerMod.
+*/
+
+#include "../xint.hpp"
+#include "../xint_data_t.hpp"
+
+#include <vector>
+
+namespace xint {
+
+using namespace detail;
+
+digit_t inverse0(const integer& n) {
+    // Using the Dussé and Kalisk simplification
+    doubledigit_t x = 2, y = 1;
+    digit_t n0 = n._get_digit(0);
+    for (size_t i = 2; i <= bits_per_digit; ++i, x <<= 1)
+        if (x < ((n0 * y) & ((x << 1) - 1)))
+            y += x;
+    return digit_t(x - y);
+}
+
+integer montgomeryR(const integer& n) {
+    return integer::one() << (bits_per_digit * n._get_data()->mLength);
+}
+
+integer toMontgomeryForm(const integer& n, const integer& m) {
+    return (n * montgomeryR(m) % m);
+}
+
+integer fromMontgomeryForm(const integer& n, const integer& m) {
+    integer inv=invmod(montgomeryR(m), m);
+    if (inv.nan()) {
+        if (exceptions_allowed()) throw invalid_modulus("modulus has no inverse");
+        else return integer(not_a_number());
+    }
+    return (n * inv % m);
+}
+
+//integer montgomeryReduction(const integer& m, const integer& mPrime, const
+//    integer& T)
+//{
+//    // Unstated parameter b is digit_overflowbit, a power of 2
+//    // Unstated parameter n is m.data->mLength
+//    // Unstated parameter R is b^n
+//    // gcd(m, b)==1, or in other words, m must be an odd number
+//    // m'=-m^(-1) mod b (precalculated)
+//    // T is any arbitrary number greater than zero and <= m*R
+//
+//    int n=m._get_data()->mLength;
+//    doubledigit_t mprime = mPrime._get_data()->digits[0];
+//
+//    integer A(T);
+//    for (int i=0; i < n; ++i) {
+//        integer ui((A._get_data()->digits[i] * mprime) & digit_mask);
+//        ui <<= (bits_per_digit * i); // Fast-multiply by b^i
+//        A+=(ui*m);
+//    }
+//    A >>= (bits_per_digit * n); // Fast-divide by b^n
+//    if (A >= m) A -= m;
+//    return A;
+//}
+
+integer montgomeryMultiplyMod(const integer& a, const integer& b, const integer& n,
+    digit_t nPrime0)
+{
+    // Using the Dussé and Kalisk simplification
+    // Unstated parameter B is a power of two representing the number of values
+    //   that a single digit can hold, i.e. digit_overflowbit
+    // Unstated parameter L is the number of digits in the modulus, i.e.
+    //   n._get_length()
+    // Unstated parameter r is B^L
+    // nPrime0 is nPrime mod B, or digit zero of nPrime
+
+    const integer B(digit_overflowbit);
+    const int L(n._get_length()), L1(L-1);
+
+    integer t=a*b;
+    int i=0;
+
+    do {
+        digit_t mi=digit_t(doubledigit_t(t._get_digit(i))*nPrime0);
+        t += (n * mi) << (bits_per_digit * i);
+    } while (++i <= L1);
+
+    t >>= (bits_per_digit * L); // Fast divide by r
+    return (t >= n ? t - n : t);
+}
+
+namespace {
+
+// cMaxK sets the balance between memory/precalculations required and the number
+// of calculations required for an exponentiation. Increasing it can only reduce
+// the calculations by a small amount, whereas it increases the memory
+// requirements and number of precalculations by an exponential amount. 8
+// provides a good balance.
+const size_t cMaxK=8;
+typedef boost::uint_t<cMaxK>::fast kbitdigit_t; // k bits have to fit into it
+typedef std::vector<kbitdigit_t> vkbitdigit_t;
+typedef std::vector<integer> vxint_t;
+#define ddPowerOfTwo(p) (doubledigit_t(1) << p)
+
+// The splitIntoKBitDigits function assumes that cMaxK <= bits_per_digit+1,
+// it won't work properly if it isn't.
+BOOST_STATIC_ASSERT(cMaxK <= bits_per_digit+1);
+
+class TUTable {
+    public:
+    typedef std::pair<int, int> value_t;
+
+    const value_t& operator[](size_t x) const { return mTable[x]; }
+
+    static const TUTable& get() {
+        // Construct a singleton instance on demand
+        if (mPtr==0) mPtr=new TUTable;
+        return *mPtr;
+    }
+
+    private:
+    TUTable(): mTable(new value_t[ddPowerOfTwo(cMaxK)]) {
+        value_t *p=&mTable[0], *pe=p+ddPowerOfTwo(cMaxK);
+        *p++=std::make_pair(0, 0);
+        int i=1;
+        while (p!=pe) *p++=calculateValues(i++);
+    }
+    ~TUTable() { delete[] mTable; }
+
+    std::pair<int, int> calculateValues(int x) {
+        int r=0;
+        while (1) {
+            if (x & 0x01) return std::make_pair(r, x);
+            ++r;
+            x >>= 1;
+        }
+    }
+
+    static TUTable *mPtr;
+
+    value_t *mTable;
+};
+
+TUTable *TUTable::mPtr=0;
+
+int mostEfficientK(const integer& e) {
+    doubledigit_t k=cMaxK, kTarget=log2(e)-1;
+    while (k > 1 && ((k - 1) * (k << ((k - 1) << 1))
+        / (ddPowerOfTwo(k) - k - 1)) >= kTarget)
+            --k;
+    return int(k);
+}
+
+vxint_t precalculateOddPowersOfAa(const integer& a, const integer&
+    r, const integer& n, size_t k)
+{
+    integer aa=a*r%n, aSquared=a*a%n;
+
+    vxint_t rval;
+    rval.reserve(ddPowerOfTwo(k));
+    rval.push_back(integer::one());     // Anything to the zeroth power is one
+    rval.push_back(aa);                 // Anything to the first power is itself
+
+    for (doubledigit_t i=3, ie=(ddPowerOfTwo(k)); i<ie; i+=2) {
+        aa=aa*aSquared%n;
+        rval.push_back(integer::zero()); // Even powers not needed or calculated
+        rval.push_back(aa);              // Odd power
+    }
+
+    return rval;
+}
+
+vkbitdigit_t splitIntoKBitDigits(const integer& e, size_t k) {
+    size_t eBits=log2(e), eDigits=(eBits+k-1)/k, i=0, bitsInHopper=0;
+
+    vkbitdigit_t rval;
+    rval.reserve(eDigits);
+
+    doubledigit_t hopper=0, mask=(doubledigit_t(1)<<k)-1;
+    while (eDigits-- > 0) {
+        if (bitsInHopper < k && i < e._get_length()) {
+            // Add more bits to the hopper
+            hopper = hopper | (doubledigit_t(e._get_digit(i++)) << bitsInHopper);
+            bitsInHopper += bits_per_digit;
+        }
+
+        // Grab k bits off the bottom
+        if (bitsInHopper > 0) {
+            rval.push_back(kbitdigit_t(hopper & mask));
+            hopper >>= k;
+            bitsInHopper-=k;
+        } else {
+            rval.push_back(0);
+        }
+    }
+
+    return rval;
+}
+
+} // namespace
+
+integer montgomeryPowerMod(const integer& a, const integer& e, const integer& n)
+{
+    // 0 <= a < n, n is odd
+    // Returns a^e mod n
+
+    const TUTable &tuTable(TUTable::get());
+
+    if (e.sign()==0) return integer::one();
+    if (n.even()) {
+        if (exceptions_allowed()) throw invalid_modulus("montgomeryPowerMod "
+            "requires an odd modulus");
+        else return integer(not_a_number());
+    }
+
+    // Precalculate some values
+    const size_t k(mostEfficientK(e));
+    const integer r(montgomeryR(n));
+    const digit_t nPrime0(inverse0(n));
+    const vxint_t oddPowersOfAa(precalculateOddPowersOfAa(a, r, n, k));
+
+    // Slice the exponent (e) up into k-bit digits
+    vkbitdigit_t eDigits(splitIntoKBitDigits(e, k));
+
+    integer pp;
+
+    kbitdigit_t i=eDigits.back();
+    eDigits.pop_back();
+    if (i == 0) {
+        pp=r%n;
+    } else {
+        std::pair<int, int> tu=tuTable[i];
+        pp=oddPowersOfAa[tu.second];
+        while (tu.first-- > 0) pp=montgomeryMultiplyMod(pp, pp, n, nPrime0);
+    }
+
+    while (!eDigits.empty()) {
+        i=eDigits.back();
+        eDigits.pop_back();
+
+        if (i == 0) {
+            int t=int(k);
+            while (t-- > 0) pp=montgomeryMultiplyMod(pp, pp, n, nPrime0);
+        } else {
+            std::pair<int, int> tu=tuTable[i];
+
+            int s=k-tu.first;
+            while (s-- > 0) pp=montgomeryMultiplyMod(pp, pp, n, nPrime0);
+
+            pp=montgomeryMultiplyMod(pp, oddPowersOfAa[tu.second], n, nPrime0);
+
+            while (tu.first-- > 0) pp=montgomeryMultiplyMod(pp, pp, n, nPrime0);
+        }
+    }
+
+    return montgomeryMultiplyMod(pp, integer::one(), n, nPrime0);
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/src/operators.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/operators.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,25 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the definitions for the basic math operators.
+*/
+
+#include "../xint.hpp"
+
+const xint::integer& operator+(const xint::integer& a) { return a; }
+xint::integer operator-(const xint::integer& a) { return xint::negate(a); }
+xint::integer operator+(const xint::integer& num1, const xint::integer& num2) { return xint::add(num1, num2); }
+xint::integer operator-(const xint::integer& num1, const xint::integer& num2) { return xint::subtract(num1, num2); }
+xint::integer operator*(const xint::integer& num1, const xint::integer& num2) { return xint::multiply(num1, num2); }
+xint::integer operator/(const xint::integer& num1, const xint::integer& num2) { return xint::divide(num1, num2); }
+xint::integer operator%(const xint::integer& num1, const xint::integer& num2) { return xint::mod(num1, num2); }
+xint::integer operator&(const xint::integer& n1, const xint::integer& n2) { return xint::bitwise_and(n1, n2); }
+xint::integer operator|(const xint::integer& n1, const xint::integer& n2) { return xint::bitwise_or(n1, n2); }
+xint::integer operator^(const xint::integer& n1, const xint::integer& n2) { return xint::bitwise_xor(n1, n2); }

Added: sandbox/xint/boost/xint/src/powers.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/powers.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,123 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the definitions for functions related to powers of a
+    number.
+*/
+
+#include "../xint.hpp"
+#include "../xint_data_t.hpp"
+
+#include <vector>
+
+namespace xint {
+
+using namespace detail;
+
+namespace {
+
+    bool addOverflow(doubledigit_t &n1, doubledigit_t n2) {
+        doubledigit_t t=(n1>>1)+(n2>>1);
+        if ((n1&1) && (n2&1)) ++t;
+        n1+=n2;
+        if (t & doubledigit_hibit) return true;
+        return false;
+    }
+
+} // namespace
+
+integer pow2(size_t exponent) {
+    integer r;
+    setbit(r, exponent);
+    return r;
+}
+
+integer sqr(const integer& n) {
+    n._throw_if_nan();
+
+    const data_t *ndata=n._get_data();
+    std::vector<doubledigit_t> a(ndata->mLength*2+1, 0);
+    doubledigit_t *adigit=&a[0];
+
+    int i, j;
+    integer addend;
+    data_t *addenddata=addend._get_data();
+    addenddata->alloc(ndata->mLength*2+1);
+
+    digit_t *ndigitip=ndata->digits;
+    for (i=0; i<ndata->mLength; ++i, ++ndigitip) {
+        digit_t ndigiti=*ndigitip;
+        doubledigit_t t=(doubledigit_t(ndigiti) * ndigiti);
+        if (addOverflow(adigit[2*i], t)) ++addenddata->digits[2*i+2];
+
+        for (j=i+1; j<ndata->mLength; ++j) {
+            doubledigit_t t=(doubledigit_t(ndata->digits[j]) * ndigiti);
+            if (t & doubledigit_hibit) ++addenddata->digits[i+j+2];
+            t<<=1;
+            if (addOverflow(adigit[i+j], t)) ++addenddata->digits[i+j+2];
+        }
+    }
+
+    integer answer;
+    data_t *answerdata=answer._get_data();
+    answerdata->alloc(ndata->mLength*2+1);
+
+    doubledigit_t carry=0;
+    for (i=0, j=ndata->mLength*2+1; i<j; ++i) {
+        if (addOverflow(carry, adigit[i])) ++addenddata->digits[i+2];
+        answerdata->digits[i]=digit_t(carry);
+        carry>>=bits_per_digit;
+    }
+
+    answerdata->skipLeadingZeros();
+    addenddata->skipLeadingZeros();
+    answer+=addend;
+
+    return answer;
+}
+
+integer pow(const integer& n, const integer& exponent) {
+    bool neg=(n.sign() < 0 && exponent.odd());
+
+    int length=exponent._get_length(), lastBitCount=0;
+    digit_t ee(exponent._get_digit(length-1));
+    while (ee != 0) { ee >>= 1; ++lastBitCount; }
+
+    integer p(abs(n)), answer=integer::one();
+    for (int eIndex=0; eIndex < length; ++eIndex) {
+        digit_t e(exponent._get_digit(eIndex));
+
+        int bitCount(eIndex == length-1 ? lastBitCount : bits_per_digit);
+        while (bitCount-- > 0) {
+            if (e & 0x01) answer*=p;
+            p=sqr(p);
+            e >>= 1;
+        }
+    }
+
+    answer._set_negative(neg);
+    return answer;
+}
+
+integer factorial(size_t n) {
+    integer r(integer::one());
+    if (n == (std::numeric_limits<size_t>::max)()) {
+        // It's highly unlikely that the system will be able to calculate this,
+        // or that anyone might want to, but someday it will be possible. This
+        // code keeps the function from going into an infinite loop if/when that
+        // happens.
+        r=(std::numeric_limits<size_t>::max)();
+        --n;
+    }
+    for (size_t i=2; i<=n; ++i) r*=i;
+    return r;
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/src/primes.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/primes.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,113 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the definitions for functions related to prime numbers.
+*/
+
+#include "../xint.hpp"
+
+#include <vector>
+
+namespace xint {
+
+namespace {
+
+std::vector<int> sieveOfEratosthenes(int upTo) {
+    std::vector<int> sieve;
+    sieve.reserve(upTo);
+
+    // Zero and one aren't prime, by this definition.
+    sieve.push_back(0);
+    sieve.push_back(0);
+
+    for (int p=2; p<upTo; ++p) sieve.push_back(p);
+
+    std::vector<int> ret;
+
+    int *p=&sieve[0], *e=p+upTo;
+    while (p<e) {
+        if (*p==0) { ++p; continue; }
+        ret.push_back(*p);
+
+        int *p2=p+(*p);
+        while (p2<e) { *p2=0; p2+=*p; }
+
+        ++p;
+    }
+
+    return ret;
+}
+
+// The Miller-Rabin Probabilistic Test of Primality
+int isProbablePrimeBaseB(const integer& n, const integer &b, callback_t
+    callback)
+{
+    const integer nMinus1(n - integer::one());
+
+    // Find r and a satisfying: n-1=2^a * r, r odd
+    integer r=nMinus1;
+    unsigned long a=0;
+    while (r.even()) { r >>= 1; ++a; }
+
+    // We check the congruence class of b^((2^i)r) % n for each i
+    // from 0 to a - 1. If any one is correct, then n passes.
+    // Otherwise, n fails.
+    integer test=powmod(b, r, n);
+    if (test==integer::one() || test==nMinus1) return 1; // Better than 3/4 chance it's prime
+
+    while (a-->0) {
+        test=sqrmod(test, n);
+        if (test==nMinus1) return 1;
+    }
+
+    if (callback && !callback()) return -1;
+    return 0;
+}
+
+} // namespace
+
+int is_prime(const integer& n, callback_t callback) {
+    if (n < 2) {
+        if (exceptions_allowed()) throw std::invalid_argument("xint::is_prime cannot test numbers below 2");
+        else return -1;
+    }
+
+    // First we trial-divide it by the primes below 2000
+    static const std::vector<int> cLowPrimes(sieveOfEratosthenes(2000));
+    std::vector<int>::const_iterator i=cLowPrimes.begin(), ie=cLowPrimes.end();
+    for (; i!=ie; ++i) if ((n % *i)==0) return (n==*i);
+
+    // Run the number through the Miller-Rabin Probabilistic Test of Primality
+    // a few times to see if it's actually (probably) prime.
+    for (int count=0; count<5; ++count) {
+        int k=random<int>();
+        int isP=isProbablePrimeBaseB(n, abs(k), callback);
+        if (isP <= 0) return isP;
+    }
+    return 1; // Appears to be prime!
+}
+
+integer random_prime(size_t sizeInBits, callback_t callback) {
+    // Call the callback for the first time
+    if (callback && !callback()) return integer(not_a_number());
+
+    integer pe=pow2(sizeInBits+1);
+    while (1) {
+        integer p(random_by_size(sizeInBits, true, true));
+        while (p < pe) {
+            int r=is_prime(p, callback);
+            if (r < 0) return integer(not_a_number());
+            if (r == 1) return p;
+            p+=2;
+        }
+    }
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/src/primitives.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/primitives.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,283 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the definitions for math primitives.
+*/
+
+#include "../xint.hpp"
+#include "../xint_data_t.hpp"
+#include <cassert>
+
+namespace xint {
+
+using namespace detail;
+
+integer abs(const integer& n) {
+    return (n < 0 ? -n : n);
+}
+
+integer negate(const integer& _n) {
+    _n._throw_if_nan();
+
+    integer n(_n);
+    n._make_unique();
+    n._get_data()->negate();
+    return n;
+}
+
+integer add(const integer& n1, const integer& n2) {
+    if (n1.sign()==0) return n2;
+    if (n2.sign()==0) return n1;
+
+    bool swapped=false;
+    const data_t *n1data=n1._get_data(), *n2data=n2._get_data();
+    if (n1data->mLength < n2data->mLength) { swapped=true; std::swap(n1data, n2data); }
+
+    integer r;
+    data_t *rdata=r._get_data();
+    rdata->copy(n1data, 1);
+
+    if (n1.sign() != n2.sign()) {
+        int level=n2data->mLength;
+
+        integer _n2(swapped ? n1 : n2);
+        _n2._make_unique();
+        _n2._get_data()->invert();
+
+        rdata->add(_n2._get_data());
+
+        if (rdata->mLength > level) {
+            --rdata->digits[level];
+            rdata->skipLeadingZeros();
+        } else rdata->invert();
+    } else {
+        rdata->add(*n2data);
+    }
+    return r;
+}
+
+integer subtract(const integer& n1, const integer& n2) {
+    if ((n1.sign() < 0) != (n2.sign() < 0)) {
+        return add(n1, -n2);
+    } else if (n1.sign() < 0) {
+        return -subtract(-n1, -n2);
+    }
+
+    // Signs are both guaranteed positive now.
+
+    if (n1 < n2) {
+        return -subtract(n2, n1);
+    } else {
+        integer r;
+        data_t *rdata=r._get_data();
+        rdata->copy(n1._get_data());
+        rdata->subtract(*n2._get_data());
+        return r;
+    }
+}
+
+integer multiply(const integer& n, const integer& by) {
+    if (n.sign()==0 || by.sign()==0) return integer::zero();
+
+    const data_t *ndata=n._get_data(), *bydata=by._get_data();
+    if (ndata == bydata) return sqr(n);
+
+    // In multiplication, we know that the answer will be less than or equal to
+    // the sum of the lengths of the operands.
+    integer answer;
+    data_t *answerdata=answer._get_data();
+    answerdata->alloc(ndata->mLength + bydata->mLength);
+
+    // Now multiply the digits, starting at the least-significant digit.
+    const digit_t *d1 = ndata->digits, *d1e = d1 + ndata->mLength;
+    const digit_t *d2e = bydata->digits + bydata->mLength;
+    for (int digit1=0; d1<d1e; ++digit1, ++d1) {
+        const digit_t *d2=bydata->digits;
+        for (int digit2=0; d2<d2e; ++digit2, ++d2) {
+            // First multiply the two digits
+            doubledigit_t t=doubledigit_t(*d1) * *d2;
+
+            // Now add the result to the answer.
+            int carry=0;
+            digit_t *a = answerdata->digits + digit1 + digit2;
+            doubledigit_t addt=doubledigit_t(*a) + (t & digit_mask);
+            if (addt >= digit_overflowbit) carry=1;
+            *a++=static_cast<digit_t>(addt);
+
+            addt=*a + ((t >> bits_per_digit) & digit_mask) + carry;
+            if (addt >= digit_overflowbit) carry=1; else carry=0;
+            *a++=static_cast<digit_t>(addt);
+
+            while (carry) {
+                addt=*a+1;
+                *a++ = static_cast<digit_t>(addt);
+                if (addt < digit_overflowbit) break;
+            }
+        }
+    }
+
+    answer._set_negative(n.sign() != by.sign());
+    answer._get_data()->skipLeadingZeros();
+    return answer;
+}
+
+namespace {
+
+std::pair<integer, integer> divideBySingleDigit(const integer& d1, digit_t d2) {
+    const data_t *d1data=d1._get_data();
+
+    integer quotient, remainder;
+    data_t *qdata=quotient._get_data(), *rdata=remainder._get_data();
+    qdata->alloc(d1data->mLength);
+    rdata->alloc(1);
+
+    doubledigit_t a=0;
+    const doubledigit_t lomask(digit_mask);
+    const doubledigit_t himask(doubledigit_t(digit_mask) << bits_per_digit);
+
+    int m = d1data->mLength - 1;
+    const digit_t *d1p=d1data->digits+m;
+    digit_t *qp=qdata->digits+m;
+    for (int i = m; i >= 0; --i, --d1p, --qp) {
+        a = (a & ~lomask) | *d1p;
+        *qp = static_cast<digit_t>(a / d2);
+        a = (a & ~himask) | ((a % d2) << bits_per_digit);
+    }
+    rdata->digits[0] = static_cast<digit_t>((a & himask) >>
+        bits_per_digit);
+
+    qdata->skipLeadingZeros();
+    rdata->skipLeadingZeros();
+    return std::make_pair(quotient, remainder);
+}
+
+std::pair<integer, integer> subDivide(integer d1, integer d2) {
+    const data_t *ndata=d1._get_data(), *bydata=d2._get_data();
+    const digit_t *nDigits = ndata->digits, *byDigits = bydata->digits;
+    int nMSD = ndata->mLength-1, byMSD = bydata->mLength-1;
+
+    // The normalization step
+    digit_t d = static_cast<digit_t>(digit_overflowbit /
+        (doubledigit_t(byDigits[byMSD])+1));
+    if (d > 1) {
+        d1 *= d;
+        d2 *= d;
+
+        // Gotta reset these
+        ndata = d1._get_data();
+        bydata = d2._get_data();
+        nDigits = ndata->digits;
+        byDigits = bydata->digits;
+        nMSD = ndata->mLength-1;
+        byMSD = bydata->mLength-1;
+
+    }
+    assert(byDigits[byMSD] >= digit_overflowbit / 2);
+
+    // We have to figure out which digit is going to be the first one. We'll do
+    // that by cutting the least-significant digits of the dividend until it
+    // has the same number of digits as the divisor; if what remains is greater
+    // than the divisor, then we start there, otherwise that one's zero and we
+    // start on the next lower one.
+    int highestQuotientDigit=(nMSD - byMSD);
+    integer nTest(d1);
+    nTest -= integer::one();
+    nTest >>= (bits_per_digit * highestQuotientDigit);
+    if (nTest < d2) --highestQuotientDigit;
+
+    integer quotient, w;
+    data_t *qdata=quotient._get_data();
+    qdata->alloc(highestQuotientDigit + 1);
+
+    for (int j = highestQuotientDigit; j >= 0; --j) {
+        doubledigit_t q = (nDigits[nMSD] > byDigits[byMSD] ?
+            doubledigit_t(nDigits[nMSD]) / byDigits[byMSD] :
+            ((doubledigit_t(nDigits[nMSD]) << bits_per_digit) +
+            nDigits[nMSD-1]) / byDigits[byMSD]);
+
+        digit_t loopcount=0;
+        while (1) {
+            w=(d2 * q);
+            w <<= (bits_per_digit * j);
+
+            w = d1 - w;
+            if (w.sign() < 0) {
+                --q;
+
+                // Our estimate should only be off by a maximum of two, so this
+                // while loop should only run twice each time, at most.
+                assert(++loopcount <= 2);
+            } else break;
+        }
+
+        qdata->digits[j] = static_cast<digit_t>(q);
+        if (w < d2) break;
+
+        d1 = w;
+        ndata=d1._get_data();
+        nDigits = ndata->digits;
+        nMSD = ndata->mLength-1;
+    }
+
+    if (d > 1) {
+        // Denormalization step. This requires a division by a single digit_t.
+        integer remainder=divideBySingleDigit(w, d).first;
+        return std::make_pair(quotient, remainder);
+    } else {
+        return std::make_pair(quotient, w);
+    }
+}
+
+} // namespace
+
+integer divide(const integer& dividend, const integer& divisor) {
+    return divide_r(dividend, divisor).first;
+}
+
+std::pair<integer, integer> divide_r(const integer& d1, const
+    integer& d2)
+{
+    int sign1=d1.sign(), sign2=d2.sign();
+    if (sign2==0) {
+        if (exceptions_allowed()) throw divide_by_zero();
+        else return std::make_pair(integer(not_a_number()), integer(not_a_number()));
+    }
+
+    int comp=compare(d1, d2, true);
+    if (comp<0) {
+        return std::make_pair(integer::zero(), d1);
+    } else if (comp==0) {
+        return std::make_pair(sign1 != sign2 ? integer::one() : integer(-1),
+            integer::zero());
+    }
+
+    if (sign1 < 0 && sign2 < 0) {
+        std::pair<integer, integer> a=subDivide(-d1, -d2);
+        a.second._set_negative(true);
+        return a;
+    } else if (sign1 < 0) {
+        std::pair<integer, integer> a=subDivide(-d1, d2);
+        a.first._set_negative(true);
+        a.second._set_negative(true);
+        return a;
+    } else if (sign2 < 0) {
+        std::pair<integer, integer> a=subDivide(d1, -d2);
+        a.first._set_negative(true);
+        return a;
+    };
+
+    if (d2._get_data()->mLength == 1) {
+        return divideBySingleDigit(d1, d2._get_data()->digits[0]);
+    } else {
+        return subDivide(d1, d2);
+    }
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/src/random.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/random.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,235 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the random number functions.
+*/
+
+#include "../xint.hpp"
+#include "../xint_data_t.hpp"
+
+#include <vector>
+#include <sstream>
+#include <fstream>
+
+#include <boost/crc.hpp>
+#include <boost/random/mersenne_twister.hpp>
+
+#ifdef XINT_THREADSAFE
+    #include <boost/thread.hpp>
+#endif
+
+#ifdef _WIN32
+    #define STRICT
+    #define WIN32_LEAN_AND_MEAN
+    #define NOMINMAX
+    #include <windows.h>
+    #include <TCHAR.h>
+#endif
+
+namespace xint {
+
+using namespace detail;
+
+namespace {
+
+class generator_t {
+    typedef boost::mt19937 internal_generator_t;
+
+    public:
+    typedef internal_generator_t::result_type result_type;
+
+    #ifdef XINT_THREADSAFE
+        generator_t() { mLock.lock(); init(); }
+        ~generator_t() { mLock.unlock(); }
+    #else
+        generator_t() { init(); }
+    #endif
+
+    void seed_manual(const std::string& bytes);
+    bool seed_secure();
+    void seed_fallback();
+    result_type operator()();
+
+    private:
+    class SeedGenerator {
+        public:
+        SeedGenerator(const std::string& seedstring): mString(seedstring.substr(0,
+            cSeedMaximumBytes)), mNumber(0) { }
+        internal_generator_t::result_type operator()() {
+            std::ostringstream s1;
+            s1 << mNumber++ << mString;
+            std::string s2=s1.str();
+
+            boost::crc_32_type crc;
+            crc.process_bytes(s2.c_str(), s2.length());
+            return crc.checksum();
+        }
+
+        #ifdef XINT_SECURE
+            static char zero(char) { return 0; }
+
+            ~SeedGenerator() {
+                mNumber=0;
+                std::transform(mString.begin(), mString.end(), mString.begin(),
+                    zero);
+            }
+        #endif
+
+        private:
+        static const size_t cSeedMaximumBytes=4096;
+
+        std::string mString;
+        int mNumber;
+    };
+
+    void init();
+
+    static internal_generator_t *mGen;
+    static bool mSeeded;
+
+    #ifdef XINT_THREADSAFE
+        static boost::mutex mLock;
+    #endif
+};
+
+generator_t::internal_generator_t *generator_t::mGen=0;
+bool generator_t::mSeeded=false;
+
+#ifdef XINT_THREADSAFE
+    boost::mutex generator_t::mLock;
+#endif
+
+void generator_t::seed_manual(const std::string& bytes) {
+    SeedGenerator gen(bytes);
+    mGen->seed(gen);
+    mSeeded=true;
+}
+
+bool generator_t::seed_secure() {
+    const int cBitsRequested=256,
+        cBytesRequested=cBitsRequested / std::numeric_limits<char>::digits;
+    bool success=false;
+
+    #ifdef _WIN32
+        // This should work under WinXP, Vista, and Win7. No guarantees about
+        // future compatibility, but I doubt that Microsoft will get rid of it
+        // (it's too useful), and I doubt that they'll change it now that it's
+        // well-known (it would break too many programs). We could also use the
+        // rand_s function in more recent versions of Visual C++, but that
+        // causes compatibility problems with older versions of Windows.
+        typedef BOOLEAN (WINAPI *RtlGenRandomFn)(PVOID, ULONG);
+        HMODULE dll=LoadLibrary(_T("Advapi32.dll"));
+        if (dll != 0) {
+            RtlGenRandomFn RtlGenRandom=RtlGenRandomFn(GetProcAddress(dll,
+                "SystemFunction036"));
+            if (RtlGenRandom != 0) {
+                std::vector<char> buffer(cBytesRequested, '\0');
+                if (RtlGenRandom(&buffer[0], cBytesRequested)) {
+                    char *c=&buffer[0];
+                    seed_manual(std::string(c, c+cBytesRequested));
+                    success=true;
+                }
+            }
+            FreeLibrary(dll);
+        }
+    #else
+        // This should be supported under most non-Windows systems. Note that
+        // we're using /dev/urandom, not /dev/random -- /dev/random is more
+        // secure, but it can be VERY slow.
+        std::ifstream rng("/dev/urandom");
+        if (rng) {
+            std::string rstr;
+            for (int i=0; i < cBytesRequested; ++i)
+                rstr.push_back(rng.get());
+            seed_manual(rstr);
+            success=true;
+        }
+    #endif
+
+    return success;
+}
+
+void generator_t::seed_fallback() {
+    // No cryptographically-secure device available. Fall back onto the
+    // system clock. It's not much, but it's portable, fast, and will
+    // provide at least a *little* entropy.
+    std::ostringstream out;
+    out << time(0) << clock();
+    seed_manual(out.str());
+}
+
+generator_t::result_type generator_t::operator()() {
+    if (!mSeeded)
+        if (!seed_secure())
+            seed_fallback();
+    return (*mGen)();
+}
+
+void generator_t::init() {
+    if (!mGen) mGen=new internal_generator_t();
+}
+
+} // namespace
+
+bool seed_secure() {
+    generator_t gen;
+    return gen.seed_secure();
+}
+
+void seed_fallback() {
+    generator_t gen;
+    gen.seed_fallback();
+}
+
+void seed_manual(const std::string& value) {
+    generator_t gen;
+    gen.seed_manual(value);
+}
+
+// Returns a positive (unless told otherwise) integer between zero and
+// (1<<bits)-1, inclusive
+integer random_by_size(size_t bits, bool highBitOn, bool lowBitOn, bool canBeNegative) {
+    if (bits<=0) return integer::zero();
+
+    generator_t randomGenerator;
+
+    const size_t cBitsPerIteration=std::numeric_limits<generator_t::result_type>::digits;
+
+    // Grab a set of random bits, of at least the specified size
+    int iterations = (bits+cBitsPerIteration-1) / cBitsPerIteration;
+    std::vector<generator_t::result_type> v;
+    for (int i=0; i<iterations; ++i) v.push_back(randomGenerator());
+
+    const char *vptr=(const char *)&v[0], *vptr_end=vptr+(v.size() * sizeof(generator_t::result_type));
+    integer p=from_binary(std::string(vptr, vptr_end));
+
+    // Trim it to the proper length
+    int index=(bits/bits_per_digit);
+    digit_t mask=(digit_t(1) << (bits % bits_per_digit))-1;
+    if (mask==0) { mask=digit_mask; --index; }
+    p._get_data()->digits[index] &= mask;
+    for (digit_t *i=p._get_data()->digits+index+1,
+        *ie=p._get_data()->digits+p._get_data()->mLength; i<ie; ++i) *i=0;
+    p._get_data()->skipLeadingZeros();
+
+    if (highBitOn) setbit(p, bits-1);
+    if (lowBitOn) setbit(p, 0);
+    if (canBeNegative) p._set_negative(randomGenerator() & 0x01);
+
+    return p;
+}
+
+template <>
+integer random<integer>(const integer& lowest, const integer& highest) {
+    integer range(abs(highest-lowest+1));
+    return lowest+(random_by_size(log2(range)) % range);
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/src/roots.cpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/src/roots.cpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,36 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the definitions for functions related to roots of a
+    number.
+*/
+
+#include "../xint.hpp"
+
+namespace xint {
+
+integer sqrt(const integer& n) {
+    if (n.sign() <= 0) return integer::zero();
+
+    // Initial guess is half the length of n, in bits
+    integer guess;
+    setbit(guess, log2(n)/2);
+
+    // Now refine it until we're as close as integers can get
+    while (1) {
+        integer guess2=(guess + (n/guess)) >> 1;
+        if (guess == guess2) break;
+        guess=guess2;
+    }
+
+    return guess;
+}
+
+} // namespace xint

Added: sandbox/xint/boost/xint/xint.hpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/xint.hpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,471 @@
+
+/*! \brief The Extended Integer (XInt) Library
+   \details
+    A fast, portable C++ library for multi-precision integer math.
+
+    This is the main header file for the library, and the only one that
+    programs using it should need to include.
+
+\mainpage  eXtended Integer library.
+
+A C++ library that lets your program handle much, much larger integer numbers
+than the built-in int, long, or even long long types,
+and handle them using the same syntax that C and C++ use for the standard integer types.
+
+Completely portable, written entirely in modern C++,
+with many different types of operating system, compiler, and hardware in mind.
+It will compile cleanly on many operating systems without any changes,
+automatically adapting to whatever native integer sizes are available.
+
+It's fast. Speed of execution takes a back seat to portability,
+so it doesn't include things like assembly-language modules
+to wring every last CPU cycle out of it -- but it's still pretty darn fast.
+
+Features you need. Modular arithmetic. Bit manipulation functions.
+Cryptographically-secure random and prime number generation.  
+A friendly and intuitive interface. An option for thread-safe operation.
+
+*/
+//    Copyright 2010 by Chad Nelson
+
+//    Distributed under the Boost Software License, Version 1.0.
+//    See accompanying file LICENSE_1_0.txt or copy at
+//    http://www.boost.org/LICENSE_1_0.txt
+
+#ifndef BOOST_INCLUDED_XINT_H
+#define BOOST_INCLUDED_XINT_H
+
+#include <string>
+#include <limits>
+#include <memory> // for auto_ptr
+#include <cstddef> // for size_t
+#include <iostream>
+#include <stdexcept>
+#include <boost/integer.hpp>
+#include <boost/cstdint.hpp>
+#include <boost/function.hpp>
+#include <boost/static_assert.hpp>
+
+namespace xint
+{  //! xint namespace for all extended integer classes and functions.
+
+////////////////////////////////////////////////////////////////////////////////
+// The boring-but-necessary preliminary stuff
+
+namespace detail
+{ //! xint implementation details, normal users should not need to use these.
+    typedef boost::uintmax_t doubledigit_t;
+    typedef boost::uint_t<std::numeric_limits<doubledigit_t>::digits / 2>::fast
+        digit_t;
+
+    const size_t        bits_per_digit    = std::numeric_limits<digit_t>::digits;
+    const digit_t       digit_hibit       = (digit_t(1) << (bits_per_digit-1));
+    const doubledigit_t doubledigit_hibit = (doubledigit_t(1) << (bits_per_digit*2-1));
+    const doubledigit_t digit_overflowbit = (doubledigit_t(1) << bits_per_digit);
+    const digit_t       digit_mask        = digit_t(digit_overflowbit-1);
+
+    const extern std::string nan_text;
+
+    struct data_t;
+    struct token { };
+} // namespace detail
+
+typedef std::auto_ptr<detail::token> token;
+
+typedef boost::function<bool ()> callback_t;
+const callback_t no_callback;
+
+const size_t autobase=(std::numeric_limits<size_t>::max)();
+
+class not_a_number;
+
+////////////////////////////////////////////////////////////////////////////////
+// The integer class
+
+class integer
+{  //! \brief the extended integer class.
+    public:
+    integer();
+    integer(const integer& b);
+    template <typename T> integer(const T& n);
+    explicit integer(const std::string& str, size_t base=10);
+    explicit integer(const not_a_number&); //!< Constructs an extended integer with the NotANumber value;
+    ~integer();
+
+    bool odd() const; //! \returns true if extended integer is odd.
+    bool even() const; //! \returns true if extended integer is even.
+    int  sign() const; //! \returns -1 if extended integer is < 0.
+    bool nan() const; //! \returns true if extended integer is Not-a-Number.
+
+    size_t hex_digits() const;
+
+    integer& operator=(const integer &c);
+
+    integer& operator+=(const integer& b);
+    integer& operator-=(const integer& b);
+    integer& operator*=(const integer& b);
+    integer& operator/=(const integer& b);
+    integer& operator%=(const integer& b);
+
+    integer& operator++();
+    integer& operator--();
+    integer  operator++(int);
+    integer  operator--(int);
+
+    integer& operator&=(const integer& n);
+    integer& operator|=(const integer& n);
+    integer& operator^=(const integer& n);
+    integer  operator<<(size_t shift) const;
+    integer  operator>>(size_t shift) const;
+    integer& operator<<=(size_t shift);
+    integer& operator>>=(size_t shift);
+
+    static const integer& zero();
+    static const integer& one();
+
+    // These are used internally, they're probably not useful outside of the
+    // library's functions.
+    detail::data_t *_get_data()
+    {  
+      return data; //! \returns raw data representing an extended integer.
+    }
+    const detail::data_t *_get_data() const { return data; }
+    detail::digit_t _get_digit(size_t index) const;
+    size_t _get_length() const;
+    void _set_negative(bool negative);
+    void _make_unique();
+    void _throw_if_nan() const;
+
+    private: ///////////////////////////////////////////////////////////////////
+    void _init(detail::digit_t init=0);
+    void _init(const integer &c);
+    void _init(boost::uintmax_t n);
+    void _attach();
+    void _detach();
+
+    static const integer *cZero; //!< Plain integer holding zero.
+    static const integer *cOne; //!< Plain integer holding one.
+
+    detail::data_t *data; //!< raw data representing an extended integer.
+};
+
+////////////////////////////////////////////////////////////////////////////////
+// Exception-blocking and -allowing functions
+
+bool exceptions_allowed();
+token block_exceptions();
+token allow_exceptions();
+
+////////////////////////////////////////////////////////////////////////////////
+// Miscellaneous functions
+
+bool opt_secure_mode();
+bool opt_thread_safe();
+int compare(const integer &n1, const integer &n2, bool ignoresign=false);
+size_t log2(const integer& n);
+integer gcd(const integer& num1, const integer& num2);
+integer lcm(const integer& num1, const integer& num2);
+
+////////////////////////////////////////////////////////////////////////////////
+// Mathematical primitives
+
+integer abs(const integer& n);
+integer negate(const integer& n);
+integer add(const integer& n, const integer& addend);
+integer subtract(const integer& n, const integer& subtrahend);
+integer multiply(const integer& n, const integer& multiplicand);
+integer divide(const integer& dividend, const integer& divisor);
+std::pair<integer, integer> divide_r(const integer& dividend, const integer&
+    divisor);
+
+////////////////////////////////////////////////////////////////////////////////
+// Powers and roots
+
+integer sqr(const integer& n);
+integer pow(const integer& n, const integer& exponent);
+integer pow2(size_t exponent);
+integer factorial(size_t n);
+integer sqrt(const integer& n);
+
+////////////////////////////////////////////////////////////////////////////////
+// Conversion functions
+
+template <typename T> T to(const integer& n);
+std::string to_string(const integer& n, size_t base=10, bool upperCase=false);
+integer from_string(const std::string& str, size_t base=10);
+std::string to_binary(const integer& n);
+integer from_binary(const std::string& s);
+
+////////////////////////////////////////////////////////////////////////////////
+// Bit-manipulation functions
+
+bool getbit(const integer& n, size_t bit);
+void setbit(integer& n, size_t bit);
+void clearbit(integer& n, size_t bit);
+size_t lowestbit(const integer& n, size_t valueIfZero=0);
+size_t highestbit(const integer& n, size_t valueIfZero=0);
+integer bitwise_and(const integer& n1, const integer& n2);
+integer bitwise_or (const integer& n1, const integer& n2);
+integer bitwise_xor(const integer& n1, const integer& n2);
+integer shift(const integer& n, int byBits);
+integer shift_left(const integer& n, size_t byBits);
+integer shift_right(const integer& n, size_t byBits);
+
+////////////////////////////////////////////////////////////////////////////////
+// Modular math functions
+
+integer mod(const integer& n, const integer& modBy);
+integer mulmod(const integer& n, const integer& by, const integer& modulus);
+integer sqrmod(const integer& n, const integer& modulus);
+integer powmod(const integer& n, const integer& exponent, const integer&
+    modulus, bool noMontgomery=false);
+integer invmod(const integer& n, const integer& modulus);
+
+////////////////////////////////////////////////////////////////////////////////
+// Random number functions
+bool seed_secure();
+void seed_fallback();
+void seed_manual(const std::string& value);
+integer random_by_size(size_t sizeInBits, bool highBitOn=false, bool
+    lowBitOn=false, bool canBeNegative=false);
+template <typename T> T random();
+template <typename T> T random(const T& lessThanThis);
+template <typename T> T random(const T& lowest, const T& highest);
+
+////////////////////////////////////////////////////////////////////////////////
+// Prime number functions
+
+int is_prime(const integer& n, callback_t callback=no_callback);
+integer random_prime(size_t sizeInBits, callback_t callback=no_callback);
+
+} // namespace xint
+
+////////////////////////////////////////////////////////////////////////////////
+// Global operators for the integer class
+
+bool operator!(const xint::integer& n1);
+bool operator<(const xint::integer& n1, const xint::integer& n2);
+bool operator>(const xint::integer& n1, const xint::integer& n2);
+bool operator<=(const xint::integer& n1, const xint::integer& n2);
+bool operator>=(const xint::integer& n1, const xint::integer& n2);
+bool operator==(const xint::integer& n1, const xint::integer& n2);
+bool operator!=(const xint::integer& n1, const xint::integer& n2);
+
+const xint::integer& operator+(const xint::integer& a);
+xint::integer operator-(const xint::integer& a);
+xint::integer operator+(const xint::integer& n1, const xint::integer& n2);
+xint::integer operator-(const xint::integer& n1, const xint::integer& n2);
+xint::integer operator*(const xint::integer& n1, const xint::integer& n2);
+xint::integer operator/(const xint::integer& n1, const xint::integer& n2);
+xint::integer operator%(const xint::integer& n1, const xint::integer& n2);
+xint::integer operator&(const xint::integer& n1, const xint::integer& n2);
+xint::integer operator|(const xint::integer& n1, const xint::integer& n2);
+xint::integer operator^(const xint::integer& n1, const xint::integer& n2);
+
+namespace xint {
+
+////////////////////////////////////////////////////////////////////////////////
+// Exception classes
+
+class invalid_base: public std::invalid_argument {
+    public:
+    invalid_base(const std::string& what="invalid base"): invalid_argument(what)
+        { }
+};
+
+class invalid_digit: public std::range_error {
+    public:
+    invalid_digit(const std::string& what="invalid digit"): range_error(what)
+        { }
+};
+
+class invalid_modulus: public std::invalid_argument {
+    public:
+    invalid_modulus(const std::string& what="invalid modulus"):
+        invalid_argument(what) { }
+};
+
+class divide_by_zero: public std::invalid_argument {
+    public:
+    divide_by_zero(const std::string& what="divide by zero error"):
+        invalid_argument(what) { }
+};
+
+class too_big: public std::range_error {
+    public:
+    too_big(const std::string& what="value out of range for requested "
+        "conversion"): range_error(what) { }
+};
+
+class not_a_number: public std::runtime_error {
+    public:
+    not_a_number(const std::string& what="attempted to use a Not-a-Number"):
+        runtime_error(what) { }
+};
+
+////////////////////////////////////////////////////////////////////////////////
+// Template function definitions
+
+template <typename T>
+integer::integer(const T& n) {
+    if (std::numeric_limits<T>::is_signed) {
+        if (n >= 0) {
+            if (static_cast<T>(n & detail::digit_mask) == n)
+                _init(detail::digit_t(n));
+            else _init(boost::uintmax_t(n));
+        } else if (n == (std::numeric_limits<T>::min)()) {
+            // Have to treat the minimum number carefully, because -n is not
+            // what you'd think it is.
+            _init(boost::uintmax_t(-(n+1)));
+            _set_negative(true);
+            --(*this);
+        } else {
+            _init(boost::uintmax_t(-n));
+            _set_negative(true);
+        }
+    } else {
+        if (static_cast<T>(n & detail::digit_mask) == n)
+            _init(detail::digit_t(n));
+        else _init(boost::uintmax_t(n));
+    }
+}
+
+template <typename T>
+T to(const integer& n) {
+    n._throw_if_nan();
+    if (n < (std::numeric_limits<T>::min)()
+        || n > (std::numeric_limits<T>::max)())
+            throw too_big("value out of range for requested conversion");
+
+    T rval=0;
+    int len=n._get_length();
+    for (int x=0; x<len; ++x)
+        rval=static_cast<T>((rval * detail::digit_overflowbit)
+            + n._get_digit(len-x-1));
+    if (n.sign() < 0) rval *= -1;
+    return rval;
+}
+
+template <typename T>
+T random() {
+    return random((std::numeric_limits<T>::min)(),
+        (std::numeric_limits<T>::max)());
+}
+
+template <typename T>
+T random(const T& lessThanThis) {
+    return random(0, lessThanThis-1);
+}
+
+template <typename T>
+T random(const T& lowest, const T& highest) {
+    integer range(integer(highest)-lowest+1);
+    return to<T>(lowest+(random_by_size(std::numeric_limits<T>::digits+1)
+        % range));
+}
+
+// Customization for random integer within a range
+template <>
+integer random<integer>(const integer& lowest, const integer& highest);
+
+template <typename charT, typename traits>
+inline std::basic_ostream<charT,traits>& operator<<(std::basic_ostream<charT,
+    traits>& out, const xint::integer& n)
+{
+    if (n.nan()) {
+        out << detail::nan_text;
+    } else {
+        int base=((out.flags() & std::ios::hex) ? 16
+            : (out.flags() & std::ios::oct) ? 8
+            : 10);
+        bool upperCase=(out.flags() & std::ios::uppercase ? true : false);
+
+        if (out.flags() & std::ios::showbase) {
+            if (n.sign() < 0) out << "-";
+
+            if (base==16 && upperCase) out << "0X";
+            else if (base==16) out << "0x";
+            else if (base==8) out << "0";
+
+            out << xint::to_string(abs(n), base, upperCase);
+        } else {
+            out << xint::to_string(n, base, upperCase);
+        }
+    }
+    return out;
+}
+
+template <typename charT, typename traits>
+inline std::basic_istream<charT,traits>& operator>>(std::basic_istream<charT,
+    traits>& in, xint::integer& n)
+{
+    int hex=(in.flags() & std::ios::hex) ? 1 : 0;
+    int dec=(in.flags() & std::ios::dec) ? 1 : 0;
+    int oct=(in.flags() & std::ios::oct) ? 1 : 0;
+    int count=hex+dec+oct;
+
+    size_t base=autobase;
+    if (count==1) {
+        if (hex) base=16;
+        else if (oct) base=8;
+        else base=10;
+    } else if (count>1) base=10;
+    // else auto-base
+
+    std::string s;
+    if (in.peek()=='+') {
+        in.ignore();
+    } else if (in.peek()=='-') {
+        in.ignore();
+        s.push_back('-');
+    }
+
+    if (base==autobase) {
+        if (in.peek()=='0') {
+            in.ignore();
+            int c=in.peek();
+            if (c=='x' || c=='X') {
+                in.ignore();
+                base=16;
+            } else base=8;
+        } else base=10;
+    }
+
+    if (in.peek()=='#') {
+        // Must be either #NaN# or an error
+        char buffer[6];
+        std::streamsize size=in.readsome(buffer, 5);
+        buffer[size]=0;
+        std::string str(buffer);
+
+        if (str==detail::nan_text) n=integer(not_a_number());
+        else in.setstate(std::ios::failbit);
+    } else {
+        while (in) {
+            int c=in.peek();
+            if ((base==8 && (c>='0' && c<='7')) ||
+                (base==10 && (c>='0' && c<='9')) ||
+                (base==16 && ((c>='0' && c<='9') || (c>='a' && c<='f') ||
+                    (c>='A' && c<='F'))))
+            {
+                in.ignore();
+                s.push_back(char(c));
+            } else break;
+        }
+
+        token allow=allow_exceptions();
+        try {
+            xint::integer testValue=xint::from_string(s, base);
+            n=testValue;
+        } catch (xint::invalid_digit&) {
+            // Catch invalid strings
+            in.setstate(std::ios::failbit);
+        }
+    }
+
+    return in;
+}
+
+} // namespace xint
+
+#endif // BOOST_INCLUDED_XINT_H

Added: sandbox/xint/boost/xint/xint_data_t.hpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/xint_data_t.hpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,85 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file contains the declaration for the xint data structure. It should
+    only be used by the library itself.
+
+    The data for an integer is stored in a separate struct so it can be shared
+    between different copies of an identical number.
+
+    The digits are stored low-digit-first.
+
+    Define XINT_SECURE to zero all memory before releasing it.
+*/
+
+#ifndef BOOST_INCLUDED_XINT_DATA_T_H
+#define BOOST_INCLUDED_XINT_DATA_T_H
+
+#if !defined(XINT_SECURE)
+    #include <vector>
+#endif
+
+namespace xint {
+namespace detail {
+
+struct data_t {
+    struct QuickDigits {
+        // We want at least enough QuickDigits to hold two ints.
+        static const int intbits=std::numeric_limits<unsigned int>::digits;
+        static const int suggested=(2*intbits/bits_per_digit);
+        static const int minimum=3;
+        static const int count=(suggested < minimum ? minimum : suggested);
+    };
+
+    int mLength, mAllocated;
+    digit_t *digits, mQuickDigits[QuickDigits::count];
+
+    #if !defined(XINT_SECURE)
+        std::vector<digit_t> mStorage;
+    #endif
+
+    int mCopies;
+    bool mIsNegative;
+
+    public:
+    data_t(digit_t initial1=0, digit_t initial2=0, digit_t initial3=0);
+    data_t(data_t *c);
+
+    #if defined(XINT_SECURE)
+        ~data_t();
+    #endif
+
+    void attach() { ++mCopies; }
+    bool detach() { return (--mCopies==0); }
+    void alloc(int digits, bool copydigits=false);
+    void realloc(int newdigits) { alloc(newdigits, true); }
+    void skipLeadingZeros();
+    void copy(const data_t *c, int extraDigits=0);
+    void zero(digit_t *p, size_t count);
+
+    void quickset(digit_t d1, digit_t d2=0, digit_t d3=0);
+
+    void invert();
+    void negate();
+
+    // These primitives ignore the signs of the parameters, and their results
+    // are calculated in place.
+    void add(const data_t& addend);
+    void subtract(const data_t& subtrahend);
+
+    // These are also calculated in place, for maximum speed.
+    void shift_left(int byBits);
+    void shift_right(int byBits);
+};
+
+} // namespace detail
+} // namespace xint
+
+#endif // BOOST_INCLUDED_XINT_DATA_T_H

Added: sandbox/xint/boost/xint/xint_monty.hpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/xint_monty.hpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,30 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This file declares the functions that use the Montgomery Reduction. They are
+    used internally to speed up the powmod function for odd modulii.
+*/
+
+#ifndef BOOST_INCLUDED_XINT_MONTY_H
+#define BOOST_INCLUDED_XINT_MONTY_H
+
+namespace xint {
+
+detail::digit_t inverse0(const integer& n);
+integer montgomeryR(const integer& n);
+integer toMontgomeryForm(const integer& n, const integer& m);
+integer fromMontgomeryForm(const integer& n, const integer& m);
+integer montgomeryMultiplyMod(const integer& x, const integer& y, const integer&
+    m, detail::digit_t nPrime0);
+integer montgomeryPowerMod(const integer& x, const integer& e, const integer& m);
+
+} // namespace xint
+
+#endif // BOOST_INCLUDED_XINT_MONTY_H

Added: sandbox/xint/boost/xint/xint_test.hpp
==============================================================================
--- (empty file)
+++ sandbox/xint/boost/xint/xint_test.hpp	2010-03-30 09:57:20 EDT (Tue, 30 Mar 2010)
@@ -0,0 +1,32 @@
+
+/*
+    The Extended Integer (XInt) Library
+    A fast, portable C++ library for multi-precision integer math
+    Copyright 2010 by Chad Nelson
+
+    Distributed under the Boost Software License, Version 1.0.
+    See accompanying file LICENSE_1_0.txt or copy at
+        http://www.boost.org/LICENSE_1_0.txt
+
+    This header file declares the library's self-testing functions.
+*/
+
+#ifndef BOOST_INCLUDED_XINT_TEST_H
+#define BOOST_INCLUDED_XINT_TEST_H
+
+namespace xint {
+
+bool testAll();
+bool testBitManipulations();
+bool testAddSubtract();
+bool testMultiply();
+bool testDivideMod();
+bool testConvert();
+bool testStreams();
+bool testRandom();
+bool testMontyMultiply();
+bool testMontyPowerMod();
+
+} // namespace xint
+
+#endif // BOOST_INCLUDED_XINT_TEST_H