## 4 Implementation Details of Field Arithmetic
### Optimization Strategy on 16-Bit MSP430X  
The MSP430X processor was designed as an ultra-low power microcontroller based on the 16-bit RISC CPU. The MSP430X CPU has 16 20-bit registers that are numbered from R0 to R15. Registers R0 to R3 are special-purpose registers that are used as the program counter, stack pointer, status register, and constant generator, respectively. Registers R4 to R15 are general-purpose registers that are used to store data values, address pointers, and index values.  
The MSP430X instruction set does not include multiply and multiply-and-accumulate (MAC) instructions. Instead, the MSP430 family is equipped with a memory-mapped hardware multiplier. The hardware multiplier provides four different multiply operations (unsigned multiplication, signed multiplication, unsigned multiplication and accumulation, and signed multiplication and accumulation) for the first operand, called \(\tt{MPY},\tt{MPYS},\tt{MAC},\) and \(\tt{MACS}\). The second operand register is common to all multiplier modes, called \(\tt{OP2}\). Namely, the first operand determines the operation type of the multiplier, but does not start the operation. Writing the second operand to the \(\tt{OP2}\) register starts the selected multiplication with two values. The multiplication result is written in three result registers \(\tt{RESLO},\tt{RESHI},\) and \(\tt{SUMEXT}.\tt{RESLO}\) stores the lower 16-bit of the result, \(\tt{RESHI}\) stores the upper 16-bit of the result, and \(\tt{SUMEXT}\) stores the carry bit or sign of the result.  
The MSP430X processor provides seven addressing modes for the source operand and four addressing modes for the destination operand. The total computation time depends on the instruction format and the addressing modes for the operand. Instructions between two CPU registers only require one cycle. However, memory access instruction (\(\tt{MOV}\)) requires two to six cycles depending on addressing modes of operands. To improve the performance of field arithmetic, reducing the number of memory access instructions and efficiently utilizing MAC operations are the basic optimization strategies.  
In our implementations, we targeted the MSP430 FR5969 processor [36]. This processor is equipped with 64 KB of program flash memory and 2 KB of RAM and can be clocked up to 16 MHz.  
For integer multiplication on 16-bit MSP430X processor, we chose and implemented the product scanning multiplication. Algorithm 5 outlines the product scanning method for multi-precision multiplication. The first loop in Algorithm 5 computes the lower half of the multiplication result \(c\), and the second loop computes the upper half of the result \(c\). It accumulates partial multiplications of the inner loop \(a_{j}\times b_{i-j}\) and these operations can be efficiently computed using the MAC operations of the hardware multiplier. Specifically, two 16-bit operands are multiplied and the results are added to the intermediate value \(s\), which is held in RESLO, RESHI, and SUMEXT.  
In FourQ[24], integer squaring was implemented using the SBD method [35]. We utilize the product scanning method for 128-bit integer squaring on 16-bit MSP430X. It can be easily implemented by modifying the product scanning multiplication. Additionally, this method results in better performance than the SBD method in FourQ. The implementation results can be found in Section 6.2.  
```
0:\(a=(a_{m-1},\cdots,a_{0}),b=(b_{m-1},\cdots,b_{0})\in\mathbb{F}_{p}\).
0:\(c=a\cdot b=(c_{2m-1},\cdots c_{0})\).
1:\(s\gets 0\)
2:for\(i\) from 0 to \(m-1\)do
3:for\(j\) from 0 to \(i\)do
4:\(s\gets s+a_{j}\cdot b_{i-j}\)
5:endfor
6:\(c_{i}\leftarrow s\pmod{2^{w}}\)
7:\(s\gets s/2^{w}\)
8:endfor
9:for\(i\) from \(m\) to \(2m-2\)do
10:for\(j\) from \(i-m+1\) to \(m-1\)do
11:\(s\gets s+a_{j}\cdot b_{i-j}\)
12:endfor
13:\(c_{i}\gets s\pmod{2^{w}}\)
14:\(s\gets s/2^{w}\)
15:endfor
16:\(c_{2m-1}\gets s\pmod{2^{w}}\)
17:return\(c=(c_{2m-1},\cdots,c_{0})\).
```  
**Algorithm 5**Product scanning multiplication.