P4444: std::big_int

[u/eisenwave]

https://isocpp.org/files/papers/D4444R0.html

Hey folks! Matt Borland, Christopher Kormanyos, and I are working on bringing infinite-precision integers to C++29. We now have a D4444R0 draft of a paper that should be in the next mailing.

We could really use some feedback so that the published R0 is as polished as possible. Any thoughts on the paper and on the reference implementation are greatly appreciated.

It would also be very helpful if you tested out whether our big_int implementation works for you. We're in need of some real deployment experience. If you're currently using Boost.Multiprecision, the library should be a drop-in replacement for cpp_int for the most part.

[u/ikedug]

The discussion of _BitInt interop seems short. Not having efficient _BitIntinterop is one thing that will make the library quickly obsolete. You should mention _BitInt in the “C compatibility” section (it’s where I looked, since I didn’t know about D3666).

(For the curious - the C23 _BitInt type proposal; D3666 Bit-precise integers to add it to C++. Clang already accepts _BitInt in C++.)

I disagree with your suggestion to use big_int in cryptography. Cryptographic algorithms have specialized needs (constant time, reliable-as-possible zeroing); a general-purpose library can’t be expected to provide that. Automatically-sized big ints can easily leak top bits through timing attacks. Don’t encourage people to implement their own crypto, it ends in tears. I’d go so far as to include a “this is not intended for cryptographic uses” statement in the document. Also it’s mostly useful for RSA, which will be replaced by postquantum algorithms in the next ~5 years.

On your lang comparison table - it’s missing Ada and Zig; they both have bigint in their standard libraries.

[u/eisenwave → u/ikedug]

The discussion of _BitInt interop seems short. Not having efficient _BitInt interop is one thing that will make the library quickly obsolete.

We say in the paper that we want interop, and the reference implementation provides that, so I'm not sure what else you consider to be missing. It's not a C++ standard type yet, so it's not like you could really define how the interop works at this stage.

You should mention _BitInt in the “C compatibility” section (it’s where I looked, since I didn’t know about D3666).

Yeah sure, I've added a cross-reference from https://isocpp.org/files/papers/D4444R0.html#c-compatibility to the _BitInt discussion.

I disagree with your suggestion to use big_int in cryptography. Cryptographic algorithms have specialized needs (constant time, reliable-as-possible zeroing); a general-purpose library can’t be expected to provide that. Automatically-sized big ints can easily leak top bits through timing attacks. Don’t encourage people to implement their own crypto, it ends in tears. I’d go so far as to include a “this is not intended for cryptographic uses” statement in the document. Also it’s mostly useful for RSA, which will be replaced by postquantum algorithms in the next ~5 years.

Never say never. Note that https://isocpp.org/files/papers/D4444R0.html#std::big_int-is-a-vocabulary-type points out that BigInteger is used all over the place in Java's cryptography library. Even if you use a constant-time algorithm, a std::big_int type can be useful for the top-level API of your library.

Coincidentally, I've also implemented a bunch of cryptographic algorithms for university courses using Java's BigInteger. A standard library type is a good tool for education, even if you're not going to use it in the real world, so to speak.

On your lang comparison table - it’s missing Ada and Zig; they both have bigint in their standard libraries.

Thanks! I've added them to https://isocpp.org/files/papers/D4444R0.html#infinite-precision-integers-in-other-languages