Calculate very big unsigned int in C

Question

I have 32 bytes numbers and i store them in a uint8_t* buffer. How to calculate a 32 bytes number in C? Example: add, mod, multiplication Thanks!

Answer 1

You basically need to do math just like we learn in elementary school: Add individual elements and maintain a carry byte; or multiple each pair of byte elements, apply the appropriate offset and sum everything up. This would all be loops, naturally. These can be improved upon in various ways (e.g. Karatsuba's algorithm for multiplication, and beyond that - discrete FFT can be used for a multiplication which is O(n log(n)) in the number of fixed-size elements) - but you should start simple.

Now, you don't have to reinvent the wheel yourself; there are several FOSS libraries for these kinds of "Big Integer" or BigInt structures, e.g. this one or the even more popular LibTomMath suggested by @deamentiamundi. There are even more of these in C++ if you're not limited to C only.

Finally - instead of working with individual bytes - assuming the number of bytes is divisible by 2, 4 or 8 you can use uint16_t, uint32_t or uint64_t as the basic unit with which you work.

Answer 2

The public domain big integer C-library Libtommath, to be found at https://github.com/libtom/libtommath, has one advantage: it includes a full and easy to understand description of the algorithms in libtommath/doc (you will need Latex to build it from scratch, otherwise ask Google for a copy of tommath.pdf). Even the source is well readable in contrast to e.g. GMP!