## 2 Background
### Schoolbook Strategy
Upon reset, the _count_ register is initialized with the ratio of the size of the input operands as 2. For example, for an \(m\)-bit operand length, the size of the _count_ register would be \(m/2\). Whenever users target input operands with odd values, the _count_ register is initialized with \(m+1/2\) to make them even. Then, in each clock cycle, when FSM is in state-1, the controller inspects \(b_{j+1}\) and \(b_{j}\) from _Reg-b_ and passes them as a select line to the routing multiplexer. Moreover, the controller also passes \(b_{j+1}\) and \(b_{j}\) to the _Shift-right-add_ block. Additionally, in each clock cycle, when FSM is in state-1, the controller updates the _count_ register with a decrement of 1. When the value of the _count_ register becomes 0, FSM shifts its state from state-1 to state-0, which means polynomial multiplication has finished. Consequently, if we consider the computational cost of our proposed Booth accelerator, it needs \(\frac{m}{2}\) clock cycles for multiplying one \(m\)-bit polynomial. The reason is that the traditional Booth multiplier deals with two bits in one clock cycle for multiplying polynomials. In summary, this section outlines the hardware architecture of the Booth polynomial multiplier, which offers advantages in reducing hardware resource usage (as will be detailed in the upcoming section) with a polynomial multiplication overhead, requiring \(\frac{m}{2}\) clock cycles to implement. It is important to note several polynomial multiplication algorithms from the literature that demand fewer clock cycles, such as [PERSON] (1999), [PERSON] (1999); [PERSON] (2008), and multipliers based on number theoretic transform (NTT) [PERSON] (2008); [PERSON] (2010). However, it is worth mentioning that the corresponding algorithms for these multiplication

Figure 2: FSM controller of the parameterized Booth multiplier. methods typically require higher hardware resources. Thus, there is always a trade-off between parameters like clock cycles and hardware resources. ## 4 Results and Comparison

We provide implementation results and a comparison with state-of-the-art hardware accelerators in Section 4.1 and Section 4.2, respectively. ### Results

Using the Vivado IDE design tool, we implement the proposed Booth accelerator in a Verilog HDL. For different operand lengths, the register-transfer-level (RTL) implementations are verified against the equivalent C/C++-implemented reference design. The hardware-implemented results after the post-place and route are given in Table 1. We used the Xilinx Virtex-7 (xc7 vx690 tfg1930-3) device for performance evaluations. The targeted operand sizes are presented in \(j\times k\) format in column one, where \(j\) and \(k\) show the size of the first and second operands to the multiplier as inputs. Moreover, we targeted different operand sizes: first, in powers of 2, which means we start from 16 \(\times\) 16 and go up to the maximum operand size of 1024 \(\times\) 1024; second, in NIST-recommended binary field lengths of 163, 233, 283, 409, and 571; and finally, in the NIST recommended prime field lengths of 192, 224, 256, 384, and 521. The area results in slices, LUTs, and flip-flops (FFs) are provided in column two. The design's clock cycle utilization and operating frequency are in columns three and four. Column five shows the computation time for one polynomial multiplication in \(\upmu\)s. The computation time is the latency (in \(\upmu\)s), which can be calculated using Equation (2). Finally, the last column shows the power results in milliwatts (mW). Moreover, we point out to the reader that the Vivado tool gives the slices, LUTs, FFs, frequency, and power results reported in Figure 1.0 For clock cycles, it is understood that the traditional Booth multiplier needs \(\frac{m}{2}\) cycles for \(m\)-bit polynomial multiplications as it operates two bits in one clock cycle for multiplying \(m\)-bit polynomials. Figure 1.1