# How are extremely large integers stored and implemented in programming languages?

We have data types like int and long etc. which can store just a few bytes of integers. But when we are implementing cryptographic algorithms like RSA or Elliptic Curves, we know that the key values are usually 1024 bits long.

How is this implemented in C and C++?

I had gone through /crypto/rsa.c in the Linux kernel which stored these values in some sort of data type called MPI which was included by a module named <linux/mpi.h>. It would be nice if someone could explain what this MPI thing was.

• gmplib.org Jun 20, 2021 at 14:34

MPI stands for Multiple Precision Integer. Multiple precision arithmetic is what you need when you work with integer types that go beyond the machine width $$w$$.
The basic idea is simple, you represent a large integer with multiple fixed-width words where the i-th word is the i-th "digit" in base B where $$B = 2^w$$. For example, most current machines are 64-bit so the width $$w$$ is 64, so with a single word you can represent unsigned integers up $$2^{64}-1$$. To represent integers larger than $$2^{64}-1$$, say a 1024-bit integer as in your RSA example, you use $$\lceil{1024 / 64}\rceil = 16$$ words $$a_0, a_1, a_2, \ldots, a_{15}$$. Then your integer $$x$$ of choice is encoded as $$x = a_0 + 2^{64} a_1 + 2^{2*64} a_2 + \ldots + 2^{15*64} a_{15}.$$ Note that this is essentially a $$1024$$-bit representation, the only difference is that the bits are grouped into blocks of size 64.