What is the highest limit for boost-multiprecision cpp_int?

Question

I'm working on factoring large semi-prime numbers. I am working on Java but I am just curious to explore other options as well. I know C++ Boost multiprecision supports large numbers.

I found the following information from Boost page:

typedef number<cpp_int_backend<128, 128, unsigned_magnitude, unchecked, void> >   uint128_t;
typedef number<cpp_int_backend<256, 256, unsigned_magnitude, unchecked, void> >   uint256_t;
typedef number<cpp_int_backend<512, 512, unsigned_magnitude, unchecked, void> >   uint512_t;
typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, unchecked, void> > uint1024_t;

My question is, what is the limit of largest number of cpp_int type? In Java BigInteger supports upto 2^Integer.MAX_VALUE.

Thank you.

Answer 1

cpp_int does not have a [theoretical] maximum value

It's important to bear in mind that in Java, the maximum size of the value is constrained by the physical limitations of the Java Virtual Machine to represent a value. In the underlying implementation, Java (probably) implements BigInteger with something like this:

public class BigInteger {
    private long[] bits;//limited by the maximum size of an array in Java
    /*...*/
}

^{Disclaimer: I do not know whether they use long[] or int[] to store bits.}

Similarly, in C++, cpp_int is, once you scrape away the abstractions, implemented with a pretty similar construction:

class boost::multiprecision::cpp_int {
    uint64_t * bits;
    uint64_t * end; //Points to the element-after-the-last in bits
    /*...*/
};

^{Disclaimer Again: they probably do something a little smarter than this.}

What puts the theoretical limit on Java is the fact that the JVM places a hard cap on array sizes at Integer.MAX_VALUE because arrays are indexed with int instead of long. C++ can directly use pointers, so the maximum size of cpp_int in C++ is proportional to the maximum memory range that a pointer can address—which in 64-bit architectures is usually-but-not-always™ 2⁶⁴-1; or in other words, the maximum value of cpp_int is 2^264-1-1, give-or-take an order of magnitude depending on how they implement the sign.

In environments that support larger pointers (or pointers that can address a larger range of memory), the maximum value is probably greater.

In practice, the largest value for cpp_int (and Java's BigInteger, for that matter) is the practical limit on how much memory your runtime environment is allowed to allocate.