Bignum representations

Remco Bloemen

2009-11-28, last updated 2014-03-03

Montgomery Residue Number System (Monty BuRNS)

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

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

xi=X2^64modmi x_i = X\cdot2\^{64} \mod m_i

zi=xi+yimodmi z_i = x_i + y_i \mod m_i

zi=xiyimodmi z_i = x_i \cdot y_i \mod m_i

zi=xiyi^1modmi z_i = x_i y_i\^{-1} \mod m_i

Positional notation

Xn=xb^nmodb X_n = \left\lfloor x b\^{-n} \right\rfloor \mod b

x=[0,N]^nXnb^n 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!