# Memory Efficient Implementation of Modular Multiplication for 32-bit ARM Cortex-M4
## 2 Background
### Multi-Precision Multiplication  
For both outer and inner loops, the product-scanning method is utilized. In Figure 2, detailed descriptions are given. The left part is for the outer loop, and the right part is for the inner loop. One block in the outer loop consists of two word-multiplication, indicated by the dashed boxes and colors in the right part of Figure 2. At the beginning, two words of operand \(A\) (labeled \(a_{0}\) and \(a_{1}\) in Figure 2) along with two words of \(B\) (namely \(b_{0}\) and \(b_{1}\)) are loaded from the RAM. The 64-bit product of \(a_{0}\) and \(b_{0}\) is performed and accumulated to two registers by using the UMAAL instruction. Afterward, the product of \(a_{1}\cdot b_{0}\) is performed and the product of the two words is added into the accumulator registers. The carry values from this operation can be performed without other side effects. Thereafter, we multiply \(a_{0}\) by \(b_{1}\), and add the resulting 64-bit product of \(a_{0}\cdot b_{1}\) to registers. The result of the higher word is stored in a temporal register before accumulation to avoid overflows. After the last product of the first block (i.e., \(a_{0}\cdot b_{0}\)), we add the products with values in temporary registers to the three accumulator registers. The carry bit is finally propagated. The execution of the first block in Figure 2 executes four UMAAL, three SUB, and three ADD instructions, respectively. These instructions require 10 clock cycles. In Algorithm 1, the source code of the proposed implementation is given. In lines 1 to 3, the operands are loaded to the registers and the address pointer is corrected. In lines 4 to 9, the multiplication and accumulation routine is performed. In particular, registers R1  
Figure 2: The proposed product scanning multiplication. (**a**) outer loop, an example of 128-bit multiplication. (**b**) inner loop, (\(A0\cdot B0\), \(A1\cdot B0\), \(A0\cdot B1\), \(A2\cdot B0\)). and R2 are cleared with SUB instructions. In lines 10 to 12, the intermediate results are accumulated to the registers. The subsequent blocks are executed by following the computation of the first block. ```
0: operand pointers R0, R12
0:results {R8, R4, R5, R6, R7}
1:LDM R121,{R10-R11}
2:LDM R01,{R2-R3}
3:SUB R0, R16
4:SUB R1, R1, R10, R2



DD R7, R7, R3
80:UMAAL R8, R1, R10, R2
81:ADD R5, R5, R2
82:UMAAL R6, R6, R1
83:ADD R6, R6, R1
84:ADD R6, R6, R1
85:ADD R7, R7, R3
86:UMAAL R8, R1, R11, R2
87:ADD R7, R7, R3



130:UMAAL R8, R10, R3
131:ADD R8, R11, R20
132:ADD R8, R12
133:ADD R8, R13, R14
134:ADD R8, R15, R21
135:ADD R8, R16, R17, R3
136:ADD R8, R18, R19



MAAL R8, R29
37:ADD R8, R29



29:ADD R9, R59
20:ADD R9 In Figure 3, the procedure of doubling and MAC can be split into two blocks as represented by dashed boxes. Taking the computation of \(A_{0}\cdot A_{0}\) (marked in red) as an example, the 64-bit operand \(A_{0}\) can be represented as (\(a_{0}\) and \(a_{1}\)), where \(a_{i}\) is one word long. First, we load the intermediate results computed by the middle part of Figure 3 from the memory to the registers. Afterward, \(A_{0}\) is loaded into two registers which are labeled \(a_{0}\) and \(a_{1}\). We first perform the multiplication of \(a_{0}\cdot a_{1}\) and accumulate the 64-bit product to three intermediate result registers. The accumulated intermediate results are doubled at once. Next, we perform two-word multiplication (\(a_{0}\cdot a_{0}\) and \(a_{1}\cdot a_{1}\)) and the results are accumulated to the doubled results. During accumulation, we catch the carry value and store it in the temporal register. The carry value is used in the next doubling and MAC routine. In total, the proposed doubling and MAC method costs 21 clock cycles, including 3 UMAAL, 12 ADD (resp. ADC), 4 MOV and 1 SUB instructions. The source code can be found in Algorithm 3. In line 2, the operands are loaded to registers (R8, R9). In line 3, intermediate results are loaded from memory to registers (R2, R3, R4, and R5). In lines 4 and 5, two registers are cleared.