Bignum representations

Montgomery Residue Number System (Monty BuRNS)

$\mathcal{M} = \left\{ m_i \vert m_i \mathrm{\;is\; prime},\; i \in [0,N-1] \right\}$

$\displaystyle M = \prod_{\mathcal{M}}^{m} m$

$x_i = X\cdot2^{64} \mod m_i$

$z_i = x_i + y_i \mod m_i$

$z_i = x_i \cdot y_i \mod m_i$

$z_i = x_i y_i^{-1} \mod m_i$

$X_n = \left\lfloor x b^{-n} \right\rfloor \mod b$

$x = \sum_{[0,N]}^{n} X_n b^n$

GMP!

Not easily distributable.

Easy to make distributable.

No GMP!