# Quantum Modular Adder over \(GF(2^{n}-1)\) without Saving the Final Carry
## 3 Quantum Modular Adder over \(\boldsymbol{GF(2^{n}-1)}\)  
We introduce our proposed quantum modular adder over Galois Field \(GF(2^{n}-1)\). Quantum algorithms are usually presented as quantum circuits for better understanding. We also modeled the circuit \(MA\) (modular adder) with \(3n+1\) index register qubits in the proposed algorithm, as shown in Figure 7. The Modular Adder (MA) realizes \(|c,a,b>\rightarrow|c^{\prime},a,(a+b)\;mod\;(2n-1)>\), where \(n\)-bit numbers \(a\), \(b\)_over_\(GF(2^{n}-1)\). This MA achieves its function based on the classical RCA as a full adder for two numbers and a value of the final carry. If the value is \(1\), \(1\) is added into the interim calculation result of \((a+b)\), and the final carry is truncated. In comparison, the general modular full adder usually adds \(2^{n}\), as shown in Figure 2. Specifically, \(c\) for carry is \(|c_{0}>,|c_{1}>,...,|c_{n}>=|0>,|0>,...,|0>\) with \(n+1\) register qubits. The two numbers \(a=|a_{0}>,|a_{1}>,...,|a_{(n-1)}>\) and \(b=|b_{0}>,|b_{1}>,...,|b_{(n-1)}>\) use \(n\) res  
Figure 6: The elementary gates for \(FA\): (**a**) CNOT gate; (**b**) CENOT gate. Figure 7: The proposed quantum modular adder over \(GF(2^{n}-1)\), called the module \(MA\). After quantum computation of MA, the result \((a+b)\ mod\ 2^{n}-1\) as \(S=s_{0},s_{1},...,s_{(n-1)}\) is the measured value for the register qubit \(b=b_{0},...,b_{(n-1)}\). The final carry, \(|c^{\prime}_{n}>\), in Figure 10 is \(s_{n}\) in Figure 8 as a flag to distinguish the case of specifications, but is truncated. The basic idea of our design with consideration of \(s_{n}\) is based on the following specifications:  
* If \(s_{n}\) is 0 and the sum of \(s_{(n-1)},...,s_{0}\) is not \(n\), \(S\) represents \(S=a+b\). * If \(s_{n}\) is 0 and the sum of \(s_{(n-1)},...,s_{0}\) is \(n\), \(S\) represents 0. * If \(s_{n}\) is 1, \(a+b\) consists of \((n+1)\)-bit and \(S\) is represented by Equation (2). \[S:=(a+b)\ mod\ (2^{n}-1):=(a+b)-(2^{n}-1):=(a+b+1)-2^{n} \tag{2}\]  
where \(a\), \(b\), and \(s\) consist of \(n\) bits \(a_{n-1},...,a_{0},b_{n-1},...,b0\), and \(n+1\) bits \(s_{n},s_{n-1},...,s_{0}\), sequentially, and \(S\) is \((a+b)\ mod\ 2^{n}-1\). In the first specification, the final carry \(c_{n}\), called \(s_{n}\), is zero because the sum of the two numbers does not exceed \(2^{n}-1\). The idea to define the first specification is based on the fact that the number of bits that are 1 is always less than \(n\). In the second specification, \(s_{n}\) is also zero because the sum of them equals \(2^{n}-1\). Because the remainder divided by \(2^{n}-1\) is zero, there is no need for any operation except to set zero into the register \(b\) as the result \(s_{0},...,s_{n}-1\). The idea to define the second specification is based on the fact that every bit of \(2^{n}-1\) is 1. In the third specification, the sum of the two numbers exceeds \(2^{n}-1\), and \(s_{n}\) is 1 because of the final carry. If the \(s_{n}\) in register \(c_{n}\) is 1, the result \(s_{0},...,s_{n}-1\) is calculated by Equation (2). Subtraction of \(2^{n}\) in Equation (2) is just a bit truncation of \(s_{n}\) without any operation, as shown in Figure 8 when \(s_{n}=1\). Because there is the difference of 1 as a binary 0...01 between \(2^{n}\) and \(\sum_{i=0}^{n-1}2^{i}\), 1 is added to \(S\) instead of truncating \(s_{n}\). Such a subtraction strategy by truncation is one of the common methods to speed up the modular calculation [29]. Such \(s_{n}\) is the flagship value to distinguish the above three cases before truncation. Compared to the RCA, our design does not store the final carry \(s_{n}\). This means it is more efficient when adding two numbers over \(GF(2^{n}-1)\). Figure 9 shows the sub-modules FA (full adder), SZ (set zero), and AT (adder truncated) designed with an intuitive arrangement of the specification. The first module, FA, is the full adder based on the ripple carry adder for the first specification, in which the final carry \(|c_{n}>\) as \(s_{n}\) is 0, and the result is \(a+b\).