pmont.ipynb

pmont.ipynb

参考文献

• 論文: Bos, J.W., Montgomery, P.L., Shumow, D., Zaverucha, G.M. (2014). Montgomery Multiplication Using Vector Instructions. In: Lange, T., Lauter, K., Lisoněk, P. (eds) Selected Areas in Cryptography -- SAC 2013. SAC 2013. Lecture Notes in Computer Science(), vol 8282. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43414-7_24
• スライド: http://sac2013.irmacs.sfu.ca/slides/s26.pdf (SAC 2013)

アルゴリズム・実装

MR0: 単純なモンゴメリ乗算 の実装テスト

$\textbf{Algorithm 0.}$

• $\displaystyle\textbf{Input: }A,B,M,\mu,R\text{ such that }$
  • $A,B,M,\mu,R\in\mathbb{Z},$
    • $A,B,M,\mu,R$ は整数
  • $0\leq A,B\lt M\lt R,$
  • $2\not\mid M,$
    • $M$ は奇数 ($R$ は通常、計算機上で除数 $R$ による除算・剰余算の計算コストを減らす目的で $2$ の累乗数とするため)
      • $2$ の累乗数である除数 $R$ による除算・剰余算は、論理右シフト演算（上位ビット取り出し）・ビット論理積演算（下位ビット取り出し）に置き換える事ができるため、計算コストが低い
    • $R$ が $2$ の累乗数である場合、 $M$ が奇数でないと $\gcd(R,M)=1$ が満たせず、 $\mu=M^{-1}\ \mathrm{mod}\ R$ が存在しない
  • $\gcd(R,M)=1,$
    • $R,M$ は互いに素
  • $\mu=M^{-1}\ \mathrm{mod}\ R.$
    • $\mu$ は $\mathrm{mod}\ R$ における $M$ の乗法逆元
    • $R,M$ は互いに素であるため、このような $\mu$ の値は存在する
• $\displaystyle\textbf{Output: }C\equiv A\cdot B\cdot R^{-1}\ (\mathrm{mod}\ M)\text{ such that }0\leq C\lt M.$

1. $t\leftarrow A\cdot B$
2. $q\leftarrow \mu\cdot (t\ \mathrm{mod}\ R)\ \mathrm{mod}\ R$
3. $C\leftarrow(t-q\cdot M)/R=\lfloor t/R\rfloor-\lfloor q\cdot M/R\rfloor$
4. $\textbf{if }C\lt 0\textbf{ then return }(C+M)\textbf{ else return }C$

• $t-q\cdot M\equiv t-t\cdot M^{-1}\cdot M\equiv 0\ (\mathrm{mod}\ R)$ $\quad\longrightarrow\quad t/R-\lfloor t/R\rfloor=(q\cdot M/R)-\lfloor q\cdot M/R\rfloor$ $\quad\longrightarrow\quad C=(t-q\cdot M)/R=\lfloor t/R\rfloor-\lfloor q\cdot M/R\rfloor$
• $C\cdot R\equiv t-q\cdot M\equiv t\equiv A\cdot B\ (\mathrm{mod}\ M)$ $\quad\longrightarrow\quad C\equiv A\cdot B\cdot R^{-1}\ (\mathrm{mod}\ M)$
• $0\leq t=A\cdot B\lt MR,\ 0\leq q\cdot M\lt MR$ $\quad\longrightarrow\quad -M\lt C=(t-q\cdot M)/R\lt M$

MR1: 論文の文中 Algorithm 1. の実装テスト

MR1m: Algorithm 1 modified.

($\mu=-M^{-1}\mod R$ ではなく $\mu=M^{-1}\mod R$ を用いたものに変更) の実装テスト

$\textbf{Algorithm 1 modified.}$

• $\displaystyle\textbf{Input: }A,B,M,\mu,R,n\text{ such that}$
  • $A,B,M,\mu,R,n\in\mathbb{Z},$
  • $\displaystyle A=\sum_{i=0}^{n-1} a_iR^i,$
  • $\displaystyle 0\leq a_i\lt R,$
  • $\displaystyle 0\leq A,B\lt M,$
  • $\displaystyle 2\not\mid M,$
  • $\displaystyle R^{n-1}\leq M\lt R^n,$
  • $\displaystyle \gcd(R,M)=1,$
  • $\displaystyle \mu=M^{-1}\ \mathrm{mod}\ R.$
• $\displaystyle\textbf{Output: }C\equiv A\cdot B\cdot R^{-n}\ (\mathrm{mod}\ M)\text{ such that }0\leq C\lt M.$

1. $C\leftarrow 0$
2. $\textbf{for }i=0\text{ to }n-1\textbf{ do}$
3. $\quad C\leftarrow C+a_i\cdot B$
4. $\quad q\leftarrow \mu\cdot C\mod R$
5. $\quad C\leftarrow(C-q\cdot M)/R=\lfloor C/R\rfloor-\lfloor q\cdot M/R\rfloor$
6. $\quad \textbf{if }C\lt 0\textbf{ then}$
7. $\quad\quad C\leftarrow C+M$
8. $\textbf{return }C$

MR2: 論文の文中 Algorithm 2. の実装テスト

(Computation 1 と Computation 2のループは順次実行ではなく並行実行を企図?)

Algorithm 2. の現在の解釈

$$ \begin{array}{l} \textbf{Algorithm 2. }\text{(current interpretation)} \\ \textbf{Input: } \begin{cases} A,B,M,\mu,R,n,W\text{ such that} \\ \quad A,B,M,\mu,R,n,W\in\mathbb{Z}, \\ \quad W\geq 1, \\ \quad R=2^W, \\ \quad\displaystyle A=\sum_{i=0}^{n-1}a_iR^i,\ B=\sum_{i=0}^{n-1}b_iR^i,\ M=\sum_{i=0}^{n-1}m_iR^i, \\ \quad a_i,b_i,m_i\in\mathbb{Z}\quad(0\leq i\lt n), \\ \quad 0\leq a_i,b_i,m_i\lt R\quad(0\leq i\lt n), \\ \quad 0\leq A,B\lt M, \\ \quad R^{n-1}\leq M\lt R^n, \\ \quad \gcd(R,M)=1, \\ \quad 2\not\mid M, \\ \quad \mu=M^{-1}\ \mathrm{mod}\ R\text{ such that }0\leq\mu\lt R. \end{cases} \\ \textbf{Output: }C\equiv A\cdot B\cdot R^{-n}\ \mathrm{mod}\ M\text{ such that }0\leq C\lt M. \\ \hline \textbf{Computation} \\ \hline \begin{cases} d_i=0\textbf{ for }0\leq i\lt n\\ e_i=0\textbf{ for }0\leq i\lt n\\ \end{cases} \\ \textbf{for }j = 0\text{ to }n - 1\textbf{ do} \\ \quad q \leftarrow ((\mu\cdot b_0)\cdot a_j+\mu\cdot(d_0-e_0))\ \mathrm{mod}\ R \\ \quad\begin{cases} t_0\leftarrow a_j\cdot b_0+d_0 \\ t_1\leftarrow q\cdot m_0+e_0 \\ \end{cases} \\ \quad\begin{cases} t_0\leftarrow \lfloor t_0/R\rfloor \\ t_1\leftarrow \lfloor t_1/R\rfloor \\ \end{cases} \\ \quad\textbf{for }i=1\text{ to }n-1\textbf{ do} \\ \quad\quad\begin{cases} p_0\leftarrow a_j\cdot b_i+t_0+d_i \\ p_1\leftarrow q\cdot m_i+t_1+e_i \\ \end{cases} \\ \quad\quad\begin{cases} t_0\leftarrow\lfloor p_0/R\rfloor \\ t_1\leftarrow\lfloor p_1/R\rfloor \\ \end{cases} \\ \quad\quad\begin{cases} d_{i-1}\leftarrow p_0\ \mathrm{mod}\ R \\ e_{i-1}\leftarrow p_1\ \mathrm{mod}\ R \\ \end{cases} \\ \quad\begin{cases} d_{n-1}\leftarrow t_0 \\ e_{n-1}\leftarrow t_1 \\ \end{cases} \\ \displaystyle C\leftarrow\sum_{i=0}^{n-1}(d_i-e_i)\cdot R^i \\ \textbf{if }C\lt 0\textbf{ do } C\leftarrow C+M \\ \textbf{return }C \\ \end{array} $$