## 4 Implementation Details of Field Arithmetic
### Optimization Strategy on 8-Bit AVR  
The AVR processor is a family of 8-bit microcontrollers that is widely used in MICA2/MICAz sensor motes. The AVR processors are equipped with an 8-bit integer multiplier and register file with 32\(\times\)8-bit general registers that are numbered from R0 to R31. Registers R26 : R27, R28 : R29, and R30 : R31 pairs are used as 16-bit indirect address registers called X, Y, and Z. The automatic increment and decrement addressing modes are supported on all X, Y, and Z registers, and Y and Z support fixed positive displacement. R0 and R1 registers store the 16-bit results of \(8\times 8\)-bit multiplication. The AVR processors provide a typical 8-bit reduced instruction set computer (RISC) instruction set. The most important instructions for ECC are \(8\times 8\)-bit multiplication (MUL) and memory access (LD, ST) instructions, which require two cycles. Instructions between two registers, such as addition (ADD, ADC) or subtraction (SUB, SBC), require only one cycle. Therefore, the basic optimization strategy on 8-bit AVR is reducing the number of memory access instructions.  
To simulate our implementations, we targeted the ATxmega256A3 processor [33]. This processor can be clocked up to 32 MHz and provides 256 KB of programmable flash memory, 16 KB of SRAM, and 4 KB of EEPROM.  
Recently, [PERSON] and [PERSON] [34] proposed a highly optimized Karatsuba multiplication for the 8-bit AVR processor. There are two variants of the Karatsuba multiplication method: the additive Karatsuba and subtractive Karatsuba methods. Algorithm 4 outlines the subtractive Karatsuba multiplication. We consider \(n\times n\)-bit multiplication, where \(n\) is even and \(k=n/2\) (in our case, \(n=128\) and \(k=64\)). The additive Karatsuba method can be computed similarly to Algorithm 4. However, the additive Karatsuba method may produce the carry bits in the addition of two numbers \((a_{l}+a_{h})\) and \((b_{l}+b_{h})\). The additional multiplication using the carry bits incurs a significant overhead for integer multiplication. The subtractive Karatsuba method does not produce carry bits in the computation of \(M\), but computes two absolute values \(|a_{l}-a_{h}|\) and \(|b_{l}-b_{h}|\). This overhead is not only smaller than the overhead required for the additive Karatsuba method, but can also be executed in constant-time. Therefore, we chose and implemented the subtractive Karatsuba multiplication for the 8-bit AVR implementation.  
```
0:\(a=2^{k}a_{h}+a_{l}\), \(b=2^{k}b_{h}+b_{l}\in\mathbb{F}_{p}\) for \(k\)-bit integers \(a_{l},a_{h},b_{l}\), and \(b_{h}\).
0:\(c=a\cdot b\).
1: Compute \(L=a_{l}\cdot b_{l}\)
2: Compute \(H=a_{h}\cdot b_{h}\)
3: Compute \(M=|a_{l}-a_{h}|\cdot|b_{l}-b_{h}|\)
4: Set \(t=0\), if \(M=(a_{l}-a_{h})\cdot(b_{l}-b_{h})\), \(t=1\) otherwise
5: Compute \(\hat{M}=(-1)^{t}M=(a_{l}-a_{h})\cdot(b_{l}-b_{h})\)
6:\(c=A\cdot B=L+2^{k}(L+H-\hat{M})+2^{n}H\)
7:return\(c\).
```  
**Algorithm 4**Subtractive Karatsuba multiplication [34].  
For integer squaring, we chose the sliding block doubling (SBD) method [35], which is more efficient than the subtractive Karatsuba method in the case of 128-bit operands on 8-bit AVR. To improve the performance of field arithmetic, we combined integer multiplication and squaring with modular reduction.