## 3 Results
### The SHA-256
#### 3.4.1 Rijndael's Finite Field  
The several steps are based on the arithmetic in Galois field \(\mathrm{GF}\big{(}2^{8}\big{)}=\mathrm{GF}(2)[x]/\big{(}x^{8}+x^{4}+x^{3}+x+1 \big{)}\). In AES, they use two operations in this field:  
1. Inverse operation in \(\mathrm{GF}\big{(}2^{8}\big{)}\);
2. Multiplication by \(1,2\) and \(3\).  
The first operation was implemented in Ref. [22]. The calculation of the inverse operation in the \(\mathrm{GF}\big{(}2^{8}\big{)}\) is a hard problem, but it is easy in the \(\mathrm{GF}(2)\), where multiplication is the AND operation; therefore, \(1^{-1}=1,0^{-1}=0\). (Overall, 0 does not have the inverse element but for definiteness, we put \(0^{-1}=0\). This agreement is valid for any \(\mathrm{GF}(2^{p})\), \(p\geqslant 1\).) In Refs. [22], the authors reduce sequentially the inversion in \(\mathrm{GF}\big{(}2^{8}\big{)}\) into multiplication and inversion in \(\mathrm{GF}\big{(}2^{4}\big{)}\), then into \(\mathrm{GF}\big{(}2^{2}\big{)}\) and, finally, into \(\mathrm{GF}(2)\). For example, the \(G\) element in \(\mathrm{GF}(2^{8}\big{)}\) can be represented as \(G=\gamma_{1}y+\gamma_{0}\) with a multiplication modulo, an irreducible polynomial \(r(y)=y^{2}+\tau y+\
u\) and \(\gamma_{0},\gamma_{1}\in\mathrm{GF}\big{(}2^{4}\big{)}\). Making a similar transformation with step-by-step (more details in [22]) arithmetical operations, only \(\mathrm{GF}(2)\) is left. So, the given logic gates are enough for making an inversion in \(\mathrm{GF}\big{(}2^{8}\big{)}\): the XOR, NAND and NOR. All these operations can be transformed into linear equations (QUBO) using our approach from the previous Sections 2.1 and 2.2. One can see the correspondinglinear equation in Table 4. For one byte, it requires 180 gates (XOR, NAND, and NOR) [22]. Each gate is decomposed into one additional equation and two additional bits (\(z\) and \(a\)).  
Multiplications by 1, 2 and 3 in the \(\operatorname{GF}(2^{8})\) are also easy to implement. Multiplying by 1 is exactly the same number (\(a\times 1=a(a\in\operatorname{GF}(2^{8}))\). Multiplying by 2 is equivalent to shifting the number left by one, and then XOR'ing the value 0x1B if the high bit was one; otherwise it has to do nothing. Let us build the linear system by steps. \(x=[x_{0},x_{1},\ldots,x_{7}]\) is the initial number. In the beginning, we make the shifting and XOR with 0x1B (or 00011011 as the binary number). After that, we obtain \(z=[z_{0},z_{1},\ldots,z_{7}]\). As 0x1B is constant, the XOR gate can be simplified (\(a\oplus 0=a,a\oplus 1=\overline{a}\)). Therefore, after shifting, we have to flip the value if the highest bit of \(x\) is equal to 1 and the corresponding bit of 0x1B is also equal to 1. Therefore, the full multiplication is the following linear system:  
\[\begin{cases}z_{0}=x_{7}\\ z_{1}=x_{7}+x_{0}-2a_{0}\\ z_{2}=x_{1}\\ z_{3}=x_{7}+x_{2}-2a_{1}\\ z_{4}=x_{7}+x_{3}-2a_{2}\\ z_{5}=x_{4}\\ z_{6}=x_{5}\\ z_{7}=x_{6}\end{cases} \tag{50}\]  
The equation with two variables can be eliminated because it is just the substitution. So, multiplication by 2 requires 3 additional equations and 6 additional bits. Multiplication by 3 can be considered as follows:  
\[x\times 3=x\times(2\oplus 1)=x\times 2\oplus x \tag{51}\]  
The XOR operation requires one additional equation and one additional bit per bit. So, multiplication by 3 requires \(3+8=11\) additional equations and 22 additional bits.