# Memory Efficient Implementation of Modular Multiplication for 32-bit ARM Cortex-M4
## 2 Background
### Multi-Precision Multiplication
In lines 6 to 9, the partial product (\(a_{i}\cdot a_{j}\) for \(i=j\)) is performed and accumulated to the intermediate results. In lines 10 to 14, the intermediate results are doubled. In lines 15 to 17, the two-word multiplication (\(a_{i}\cdot a_{j}\) for \(i\
eq j\)) is performed. In lines 18 to 23, the results are accumulated to the doubled results. During accumulation, the carry value is stored in the R7 register. In lines 24 to 25, the intermediate results are stored in the memory. Finally, in lines 26 to 27, the loop count is measured, and the program counter is calculated depending on the loop condition. In Algorithm 4, full rounds of squaring implementation are given. In lines 1-21, similar to the integer multiplication, partial products (\(a[i]\times a[j]\) where \(i\
eq j\)) are performed by using Algorithm 1. In lines 22-34, the remaining part (\(a[i]\times a[j]\) where \(i=j\)) is performed with doubling and MAC routine given in Algorithm 3. Figure 3: The proposed product-scanning squaring. (**a**) outer loop, an example of 128-bit squaring. (**b**) inner loop, product scanning, (\(A0\cdot A0\), \(A0\cdot A2\), \(A0\cdot A3\)). (**c**) inner loop, doubling and MAC, (\(A0\cdot A0\), \(A1\cdot A1\)). ```
0:\(\text{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{\small{{\small{\small{{\small{{\small{{\small{{\small{{{\small}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}\)
```
1:\ \begin{tabular}{}{}\end{tabular} \end{table 1:
\begin{tabular}{}

\end{table 2:
\begin{tabular}{}

\end{table 3:
\begin{tabular}{}

\end{table 4:
\begin{tabular}{}

\end{table 5:
\begin{tabular}{}

\end{table 6:
\begin{tabular}{}

\end{table 7:

\end{table 8:
\begin{tabular}{}

\end{table 9:

\end{table 10:
\begin{tabular}{}

\end{table 11:

\end{table 12:
\begin{tabular}{}

\end{table 13:

\end{table 14:
\begin{tabular}{}

\end{table 15:

\end{table 16:
\begin{tabular}{}

\end{table 17:

\end{table 18:

\end{table 19:
\begin{tabular}{}

\end{table 15:

\end{table 14:

\end{table 15:
\begin{tabular}{}



egin{tabular}{}



## 3 Scalable Montgomery Reduction for All SIKE Round 2 on Cortex-M4

The parameter sets (SIKEp434, SIKEp503, SIKEp610, and SIKEp751) are selected as the SIKE round-2 protocol [28; 29]. For high performance, the Montgomery reduction method is used [30]. The Montgomery reduction replaces the expensive inversion operation into a relatively cheap operation (i.e., multiplication). The detailed descriptions for the Montgomery reduction are given in Algorithm 5. We evaluated the all-SIKE protocols with the proposed multi-precision multiplication operation and multi-precision squaring operation. For the Montgomery reduction, we used a scalable operand-scanning method. To support all-SIKE protocols, the internal word size is set to 32-bit wise. We divided the \(n\)-word operand scanning into three steps, including initialization, a middle round, and finalization. The initialization calculates one partial product first. The intermediate result is stored in the memory, which is a quotient value. The middle round performs the \((n-1)\)-word partial products. The result is accumulated to the intermediate result. Finally, the last word is multiplied and added to the intermediate results. Detailed descriptions of the SIKEp434 case are given in Figure 4.
```
0: Modulus \(m\), Montgomery radix \(r>m\), operand \(c\in[0,m^{2}-1]\), and constant \(m^{\prime}=-m^{-1}\bmod r\)
0: Montgomery product \(z=\text{MonRed}(c,r)=c\cdot r^{-1}\bmod m\)
1:\(q\gets c\cdot m^{\prime}\bmod r\)
2:\(z\leftarrow(c+q\cdot m)/r\)
3:if\(z\geq m\)then\(z\gets z-m\)
4:return\(z\)
```
**Algorithm 5** Montgomery reduction. The modulus (\(M\)) of SIKEp434 is multiplied by the quotient in a 32-bit wise (\(Q\); q0-q13). Since the lower part of the modulus (i.e., m0-m5) is zero, only remaining parts (m6-m13) are multiplied. During the inner loop, only two registers are used to maintain the intermediate results.