C or C++ Bigint Library on Microsoft Windows

C or C++ BigInt library on Microsoft Windows

GMP.

LGPL. Standard download from official website is designed for GCC. VC++ port is available from here.

BigInteger in C?

Use libgmp:

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating-point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on...

Since version 6, GMP is distributed under the dual licenses, GNU LGPL v3 and GNU GPL v2...

GMP's main target platforms are Unix-type systems, such as GNU/Linux, Solaris, HP-UX, Mac OS X/Darwin, BSD, AIX, etc. It also is known to work on Windows in both 32-bit and 64-bit mode...

Best bignum library to solve Project Euler problems in C++?

Here are a couple of links regarding GMP and Visual Studio 2008:

GMP Install Help at CodeGuru

GMP Compile Guide at The Edge Of Nowhere (this one looks really thorough)

What is the equivalent of bigint in C#?

That corresponds to the long (or Int64), a 64-bit integer.

Although if the number from the database happens to be small enough, and you accidentally use an Int32, etc., you'll be fine. But the Int64 will definitely hold it.

And the error you get if you use something smaller and the full size is needed? A stack overflow! Yay!

Visual C++ BigInt and SecureRandom? Is there a BigInt library with modPow?

The modPow function can be evaluated efficiently with a "square and multiply" algorithm. In Java it would look like this (if Java's BigInteger did not already have it):

/* Compute x^n mod m. */
static BigInteger modPow(BigInteger x, BigInteger n, BigInteger m)
{
    if (n.signum() < 0)
        throw new IllegalArgumentException("bwah, negative exponent");
    BigInteger r = BigInteger.ONE;
    for (int i = n.bitLength() - 1; i >= 0; i --) {
        if (n.testBit(i))
            r = r.multiply(x).mod(m);
        if (i > 0)
            r = r.multiply(r).mod(m);
    }
    return r;
}

With this, the number of loop iteration is equal to the length, in bits, of the exponent, so that the computational time is acceptable.

You still get one or two modular reductions per iteration, so this will not be the fastest exponentiation algorithm ever (modular reductions are substantially more expensive than multiplication). Typical modPow() implementations use Montgomery reduction, which is a clever trick which merges all modular reduction into a single similar operation at the end.

If you have time, implementing your own modular exponentiation would be very pedagogical; you would start by reading chapter 14 of the "Handbook of Applied Cryptography", freely downloadable from this site. However, in this harsh world where mundane considerations of budget often limit creativity and free time, you would probably be happy with an already implemented library. GMP is known to be quite good, but somewhat difficult to use on Windows. You may have better luck with NTL.

A good and basic implementation of BigInt class in C++

Here's one. I haven't used it, but it doesn't look too complex, and it was the first result when I googled "bigint c++".

---

Related Topics