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 $$

Positional notation

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

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

Advantages

GMP!

Disadvantages

Not easily distributable.

Chinese remainder theorem

Advantages

Easy to make distributable.

Disadvantages

No GMP!

Remco Bloemen
Math & Engineering
https://2π.com