## 2 Background
### Schoolbook Strategy  
The Schoolbook multiplication method offers a more straightforward way to multiply input polynomials of the form \(a(x)\times b(x)\), as demonstrated in Equation (1). The resulting polynomial \(c(x)\) is computed through bit-by-bit operations. Algorithm 1 illustrates the steps of the Schoolbook multiplication, where polynomial \(a\) is multiplied by the shifted polynomial \(b\) to yield the desired polynomial \(c\). The Schoolbook multiplication method requires \(m\) clock cycles when multiplying \(m\)-bit polynomials \(a(x)\) and \(b(x)\). Instead of the clock cycle requirement or the computation cost, the associated hardware cost involves \((m-1)\) additions and \(m\) shifts for multiplications. It is worth noting that the Schoolbook multiplication method is particularly suited for area-optimized accelerators, taking into account clock cycle overhead. \[c(x)=\sum_{i=0}^{m-1}\sum_{j=0}^{m-1}a_{i}b_{j}x^{i+j} \tag{1}\]```
0:\(a\) and \(b\) (\(m-bit\) polynomial integers)
0:\(c\Leftarrow a\times b\)
1:\(A\Leftarrow 0\) (\(m-bit\) temporary integer)
2:\(\bar{b}\Leftarrow\{b,0\}\)
3:for\(\{j\) from \(0\) to \(m-1\}\)do
4:if\((\bar{b}_{1}\!\!+\!\bar{b}_{\bar{1}})=01\)then
5:\(A\Leftarrow A+a\)
6:\(c\Leftarrow shift\_right\_add(A,\bar{b}_{\bar{1}}\!\!+\!1,\bar{b}_{\bar{1}})\)
7:endif
8:if\((\bar{b}_{\bar{1}+1}\!\!+\!\bar{b}_{\bar{1}})=10\)then
9:\(A\Leftarrow A-a\)
10:\(c\Leftarrow shift\_right\_add(A,\bar{b}_{\bar{1}}\!\!+\!1,\bar{b}_{\bar{1}})\)
11:endif
12:endfor
```

**Algorithm 1** Schoolbook Multiplier [1]

Algorithm 2 performs multiplication by analyzing the least significant two bits of the multiplier, addressing four possible cases: 00, 01, 10, and 11. In cases where the inspected bits are either 00 or 11, no action is needed, and the partial product remains unchanged. For the remaining two cases, the multiplicand may be added (line 5) or subtracted (line 8) from the partial product (\(A\)). The _shift_right_add_ function in lines 6 and 9 of Algorithm 2 facilitates the multiplication of the multiplicand by 2 through the shift and add operations. In short, for operands of length \(m\), Algorithm 2 requires \(m/2\) clock cycles. ### Schoolbook and Booth Algorithms: Trade-Offs

Sections 2.1 and 2.2 describe the Schoolbook and Booth multiplication approaches for multiplying polynomials. Concerning [1], these two methods operate in a constant time as these utilize partial product generation, and then, accumulation to produce resultant polynomials in fixed clock cycles. The constant time means that these Schoolbook and Booth methods need \(m\) and \(\frac{m}{2}\) clock cycles for multiplying two polynomials of size \(m\)-bit. Moreover, constant-time computation is one approach to resist simple power analysis attacks, which are side-channel attacks that measure the power traces of the device to reveal a secret. This is a significant benefit. Some other benefits include area efficiency and low power utilization for applications specific to RFID and WSNs. Despite these benefits, one issue of the Schoolbook and Booth approaches is that they are not useful for high-speed cryptographic applications such as network servers because these require higher clock cycles for computation, resulting in a decrease in the (overall) performance or throughput. Higher clock cycle utilization can imply low throughput, while more down clock cycles can help optimize throughput. Therefore, the \(\frac{m}{2}\) clock cycle requirement for \(m\)-bit polynomial inputs motivates us to evaluate the performance of Algorithm 2 on FPGA devices, as it helps to obtain highly area-optimized cryptographic accelerators with reasonable throughput utilization. ## 3 Proposed Booth Accelerator Architecture

The architecture of the proposed Booth multiplier design is given in Figure 1. It contains six input/output pins. The input pins are \(clk\), \(rst\), \(start\), \(a\), and \(b\). The corresponding output pin is \(c\).