2009-11-28 (updated 2014-03-03)

Bignum representations

% Remco Bloemen % 2009-11-28, last updated 2014-03-03

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!