## 3 Polynomial-Based Bipartite Multiplication-Squaring Algorithm over GF(2\({}^{n}\))  
Let \(G(\beta)\) denote the irreducible polynomial of order \(n\) over GF(2) that defines GF(2\({}^{n}\)). Furthermore, let \(E(\beta)\) and \(F(\beta)\) denote any two polynomial elements of order \(n-1\) over GF(2\({}^{n}\)). The polynomials \(G(\beta)\), \(E(\beta)\) and \(F(\beta)\) can be respectively expressed as:  
\[G  
\[\beta^{n+1}\bmod G(\beta) = \sum_{j=1}^{n-1}(g_{n-1}g_{j}+g_{j-1})\beta^{j}+g_{n-1}g_{0} \tag{5}\] \[\cong G^{{}^{\prime}}(\beta)=\sum_{j=0}^{n-1}g_{j}^{{}^{\prime}}\beta^{j}\]  
Suppose \(c=\lfloor n/2\rfloor\), \(d=\lceil n/2\rceil\), and assume that \(G^{{}^{\prime}}(\beta)\) is available in advance. We can express polynomial multiplication and squaring over \(GF(2^{n})\) as:  
\[Q(\beta) = E(\beta)F(\beta)\bmod G(\beta) \tag{6}\] \[= \sum_{i=0}^{n-1}f_{i}E(\beta)\beta^{i}\bmod G(\beta)\] \[= [\sum_{i=0}^{d-1}f_{2i}E(\beta)\beta^{2i}+\] \[\beta\sum_{i=0}^{c-1}f_{2i+1}E(\beta)\beta^{2i}]\bmod G(\beta)\]  
\[R(\beta) = E(\beta)E(\beta)\bmod G(\beta) \tag{7}\] \[= \sum_{i=0}^{n-1}e_{i}E(\beta)\beta^{i}\bmod G(\beta)\] \[= [\sum_{i=0}^{d-1}e_{2i}E(\beta)\beta^{2i}+\] \[\beta\sum_{i=0}^{c-1}e_{2i+1}E(\beta)\beta^{2i}]\bmod G(\beta)\]  
We can divide \(Q(\beta)\) and \(R(\beta)\) into two parts as:  
\[\cong G^{{}^{\prime}}(\beta)=\sum_{j=0}^{n-1}g_{j}^{{}^{\prime}}\beta^{j}\]0 \[\cong G^{{}^{\prime}}(\beta)=\sum_{j=0}^{n-1}g_{j}^{{}^{\prime}}\beta^{j}\]1  
where,  
\[\cong G^{{}^{\prime}}(\beta)=\sum_{j=0}^{n-1}g_{j}^{{}^{\prime}}\beta^{j}\]2 \[\cong G^{{}^{\prime}}(\beta)=\sum_{j=0}^{n-1}g_{j}^{{}^{\prime}}\beta^{j}\]3 (11) \[\cong G^{{}^{\prime}}(\beta)=\sum_{j=0}^{n-1}g_{j}^{{}^{\prime}}\beta^{j}\]4 (12) \[\cong G^{{}^{\prime}}(\beta)=\sum_{j=0}^{n-1}g_{j}^{{}^{\prime}}\beta^{j}\]5Employing the above equations, [PERSON] [37; 41] proposed the unified bipartite algorithm, Algorithm 1, to simultaneously compute the products \(Q(\beta)\) and \(R(\beta)\). In Algorithm 1, we denote partial values of polynomials \(E(\beta)\), \(X(\beta)\), \(Y(\beta)\), \(P(\beta)\), and \(S(\beta)\) as \(E^{i}\), \(X^{i}\), \(Y^{i}\), \(P^{i}\), and \(S^{i}\), where \(i\) represents the iteration index. The symbols \(f_{2i-2}\), \(f_{2i-1}\), \(e_{2i-2}\), and \(e_{2i-1}\) indicate the \((2i-2)^{th}\) and \((2i-1)^{th}\) coefficients of input polynomials \(F(\beta)\) and \(E(\beta)\), respectively. In the initialization step of the algorithm, we notice that the coefficients of input polynomial \(E(\beta)\) are allocated to the initial variable \(E^{0}\) and zero values are allocated to the initial variables \(X^{0}\), \(Y^{0}\), \(P^{0}\), and \(S^{0}\). The for-loop terminates after \(d=\lceil n/2\rceil\) iterations, and the products \(Q\) and \(R\) can be concurrently computed as shown in Steps 8 and 9 of Algorithm 1. ```
0:\(E(\beta)\), \(F(\beta)\in\) GF(\(2^{n}\)), \(G(\beta)\), \(G^{\prime}(\beta)\), \(d=\lceil n/2\rceil\), and \(c=\lfloor n/2\rfloor\)
0:\(\textbf{Mult. Output}\): \(Q(\beta)=E(\beta)\). \(F(\beta)\mod G(\beta)\)
0:\(R(\beta)=E(\beta)\). \(E(\beta)\mod G(\beta)\) Initialization: \(E^{(0)}\gets E(\beta)\), \(F\gets F(\beta)\), \(X^{0}\gets 0\), \(Y^{0}\gets 0\), \(P^{0}\gets 0\), \(S^{0}\gets 0\)., \(G\gets G(\beta)\), \(G^{\prime}\gets G^{\prime}(\beta)\) Algorithm:
1:for\(1\leq i\leq d\)do
2:\(E^{i}=E^{i-1}\), \(\beta^{2}\mod G\)
3:\(X^{i}\gets X^{i-1}+f_{2i-2}E^{i-1}\)
4:\(Y^{i}\gets Y^{i-1}+f_{2i-1}E^{i-1}\)
5:\(P^{i}\gets P^{i-1}+e_{2i-2}E^{i-1}\)
6:\(S^{i}\gets S^{i-1}+e_{2i-1}E^{i-1}\)
7:endfor
8:\(Q\leftarrow(X^{d}+\beta Y^{c})\) mod \(G\)
9:\(R\leftarrow(P^{d}+\beta S^{c})\) mod \(G\)
```  
**Algorithm 1** Bipartite multiplication and squaring algorithm in GF(\(2^{n}\)). For the hardware implementation of Algorithm 1, we developed the corresponding bit-level form as shown in Algorithm 2. The algorithm has two nested loops to compute Steps 2 to 6 of Algorithm 1, the outer loop with the \(i\) index and the inner loop with the \(j\) index.