# On efficient normal bases over binary fields

Mohamadou Sall  Department of Electrical and Computer Engineering, University
of Waterloo<EMAIL_ADDRESS>M. Anwar Hasan  Department of Electrical
and Computer Engineering, University of Waterloo<EMAIL_ADDRESS>
###### Abstract

Binary field extensions are fundamental to many applications, such as
multivariate public key cryptography, code-based cryptography, and error-
correcting codes. Their implementation requires a foundation in number theory
and algebraic geometry and necessitates the utilization of efficient bases.
The continuous increase in the power of computation, and the design of new
(quantum) computers increase the threat to the security of systems and impose
increasingly demanding encryption standards with huge polynomial or extension
degrees. For cryptographic purposes or other common implementations of finite
fields arithmetic, it is essential to explore a wide range of implementations
with diverse bases. Unlike some bases, polynomial and Gaussian normal bases
are well-documented and widely employed. In this paper, we explore other forms
of bases of ${\mathbb{F}}_{2^{n}}$ over ${\mathbb{F}}_{2}$ to demonstrate
efficient implementation of operations within different ranges. To achieve
this, we leverage results on fast computations and elliptic periods introduced
by Couveignes and Lercier, and subsequently expanded upon by Ezome and Sall.
This leads to the establishment of new tables for efficient computation over
binary fields.

##  1 Introduction

In numerous real-world applications a significant gap exists between fast
computation and security level. Usually, for the sake of efficiency, designers
of classical and post-quantum cryptosystems refrain from working in higher
dimensions. Nonetheless, there are situations where transitioning to those
dimensions becomes necessary in order to improve the security of the designed
schemes. For example, in the National Institute of Standards and Technology
(NIST) call for post-quantum cryptography schemes there are three levels of
security, and the complexity of computations increases from one level to the
next. So, without specifying a particular cryptographic algorithm, it would be
interesting to look for efficient implementation in large rings or finite
fields. The goal of this paper is to delve into a deep analysis of efficient
multiplications in large binary extensions for both common and extended
implementations.

The approach is to exploit an explicit isomorphism between the binary field
extension ${\mathbb{F}}_{2^{n}}$ and the corresponding vector space
${\mathbb{F}}_{2}^{n}$ through a basis that can be adapted to FFT (or NTT)
like algorithms. Inherently the power basis $\\{1,\ x,\ x^{2},\ \cdots,\
x^{n-1}\\}$ of ${\mathbb{F}}_{2^{n}}$ over ${\mathbb{F}}_{2}$ has such
property and we can perform a multiplication using this basis in a quasi-
linear time. Another type of basis that is usually encountered in the
application of finite fields is the so-called normal basis [9]. A normal basis
of ${\mathbb{F}}_{2^{n}}$ over ${\mathbb{F}}_{2}$ is a basis in the form
$\\{\alpha,\alpha^{2},\cdots,\alpha^{2^{n-1}}\\}$ where
$\alpha\in{\mathbb{F}}_{2^{n}}$ is a normal element. The simplest arithmetic
operation in normal basis is squaring, carried out by a cyclic right shift,
and hence almost free of cost in hardware. Such a cost advantage often makes
normal basis a preferred choice of representation, see work by Massey and
Omura [20] and its improvement by Reyhani and Hasan [17, 18]. Despite this
main advantage, a normal basis multiplication is not so simple. So, we aim to
explore the ranges of normal bases that can be tied to NTT-like algorithms in
order to perform fast multiplication in higher degrees $n$.

Optimal normal bases [13, 24] and their generalization using Gauss periods [1]
constitute an efficient way to implement finite fields arithmetic. Indeed,
they usually have sparse multiplication table and as shown by Gao, von zur
Gathen, Panario, and Shoup [11] their construction can be tied to NTT-like
algorithms. Nonetheless, for $q$ the cardinality of the finite field
${\mathbb{F}}_{q}$, these bases use the multiplicative group of
${\mathbb{F}}_{q^{r-1}}$ for some prime $r$ and do not always exist [31].
Later on, taking advantage of the properties given by elliptic curves and
other $1-$dimensional algebraic groups, Couveignes and Lercier [6] and
subsequently Ezome and Sall [7] constructed normal elements that enlarge the
number of cases where efficient normal bases exist. Indeed, these bases can
also be tied to NTT-like algorithms and in some cases, we can get low
complexity in term of number of non-zero elements of their multiplication
tables. In a recent preprint Panario, Sall, and Wang [25] show that even if we
may have the property of sparsity, it is very hard to predict the number of
non-zero elements of the multiplication table of the bases designed by
Couveignes and Lercier. Because of this fact, if multiplication tables are
required for efficient implementation, we will be mainly focused on other
types of bases.

Gaussian normal bases (GNBs) have been studied for decades; they are well
understood and there is a lot of computational material available online [15,
26] featuring their properties. This is not the case for normal bases from
elliptic periods or extension of normal elements. Indeed most of the data
available in the literature are mainly based on results from GNBs and trace
computation (see [23, Table 2.2.10]).

From the resolution of Fermat’s last theorem by Andrew Wiles to their recent
utilization in post-quantum cryptography (through isogenies), elliptic curves,
and by extension algebraic groups, have always given an interesting turn in
the research area. In this paper, we use their properties to establish new
ranges for fast computation. We make extensive use of the results described in
[6, 7] and the extended normal elements developed by Thomson and Weir [30] and
generalized to the Artin-Schreier-Witt and Kummer theories by Ezome and Sall
[8]. We should notice that the elliptic normal bases of ${\mathbb{F}}_{q^{n}}$
over ${\mathbb{F}}_{q}$ designed by Couveignes and Lercier require an
appropriate elliptic curve $E({\mathbb{F}}_{q})$ whose existence is related to
an integer $n_{q}$. This integer is implicitly tied to the number of
${\mathbb{F}}_{q}-$rational points of $E$ and should satisfy the condition
$n_{q}\leq\sqrt{q}$. This is just too large and can be very tight for a binary
extension. Indeed it is quasi-impossible to find an appropriate curve over
${\mathbb{F}}_{2}$. Even if workarounds are presented in [6] and [5], the
developed strategies involve either many ad hoc redundant representations or
lack of a convenient model for a universal curve of genus $g$ over
${\mathbb{F}}_{q}$, which make it difficult to handle in practice. In this
paper, we show how to use practical elliptic normal bases over binary fields
by exploiting the characteristics of central processing unit (CPU) registers
and the design of computational software. The data, we presented in various
tables show how the use of elliptic curves can enlarge the number of cases
where efficient normal bases exist.

The paper is organized as follows. In Section 2 we recall the results of fast
computation using NTT-like algorithms. In Section 3 we give the necessary
backgrounds on Gaussian normal bases. Our efforts culminate in Section 4 and
Section 5 where we give new tables for fast computations over binary fields.
In each section, we highlight how the concerned basis is tied to NTT-like
algorithms. Finally, in Section 6, we give concluding remarks. Our studies are
supported by Magma codes that we have developed and made available online.

##  2 Background on NTT algorithms

The search for algorithms with fast computation in a ring or finite field
extension is an important research area. This problem can be approached
according to different models of construction and representation. For each
computational problem, one should examine whether the type of representation
for the objects (e.g., polynomial, integer) at hand is of use. For the sake of
efficiency, one may ask: In which representation is the problem easiest to
solve? How do we convert to and from that representation? The Discrete Fourier
Transform and its implementation, the Fast Fourier Transform (FFT), are the
backbone of the general idea of change of representation.
Let ${\mathcal{R}}$ be a ring, $n\geq 1$ an integer, and
$\zeta\in{\mathcal{R}}$ be a primitive $n$-th root of unity. Let
$f\in{\mathcal{R}}[X]$ be a polynomial of degree less than $n$ with
coefficient vector $(f_{0},\cdots,f_{n-1})\in{\mathcal{R}}^{n}$.

######  Definition 1.

The ${\mathcal{R}}-$linear map

$f\longmapsto\left(f(1),\cdots,f(\zeta^{n-1})\right)$

which evaluates a polynomial at the powers of $\zeta$ is called the Discrete
Fourier Transform. The inverse operation is the interpolation at the powers of
$\zeta$.

An important result in computational algebra is that both the DFT and its
inverse can be computed with $O(n\log n)$ operations in ${\mathcal{R}}$.
However, if the underlying coefficient ring ${\mathcal{R}}$ is arbitrary, an
FFT-based approach will not work directly. Indeed, this approach works over
rings containing certain primitive roots of unity. As a counter-example, a
finite field ${\mathbb{F}}_{q}$ contains a primitive $n$-th root of unity if
and only if $n$ divides $q-1$. In 1971, Schonhage and Strassen [28] showed how
to create “virtual” roots that leads to a multiplication cost of only $O(n\log
n\log\log n)$. This idea gives rise to many studies and improvements, and
recently Harvey and Hoeven [16] proved that multiplication in
${\mathbb{F}}_{q^{n}}$ can be done with $O(n\log n)$ operations in
${\mathbb{F}}_{q}$.
In order to achieve quasi-linear speed in $O(n\log n)$ when performing
polynomial multiplication or any related operation (e.g., convolution product
of vectors) we use the FFT to compute the Discrete Fourier Transform or more
specifically the Number Theoretic Transform (NTT) [27]. DFT and NTT are just
different names for the same thing depending on the context. Indeed, NTTs are
DFTs defined in finite fields and rings of polynomials or integers. Their main
advantage over DFTs is that systematic advantage is taken from the operation
in finite fields or rings to define simple roots of unity which allows to
replacement of complex arithmetic by real arithmetic. The general principle of
NTT can be found in many algorithmic books because it is widely used in many
engineering, signal processing, mathematical and physical domains.

######  Definition 2.

In this paper, an NTT-like algorithm is an algorithm that involves the
computation of polynomials of degree less than $n$ or convolution products of
vectors of length $n$.

Even though NTT-like methods are the backbone of the fastest algorithms,
general-purpose computer algebra systems also implement the classical and
sometimes the Karatsuba method and its variants, which are sub-quadratic. So,
to perform efficient polynomial or vector arithmetic a large variety of
algorithms have to be coded and tested to determine the crossover point. That
is the point where one algorithm beats another in terms of performance
(running time, number of operations, memory size). For small degree or length
$n$, the school book method is sufficient, and the Karatsuba algorithm is used
when we have intermediate $n$. If the integer $n$ is very large, it becomes
much more interesting to work with NTT methods.

The choice of degree for using the Number Theoretic Transform (NTT) in the
context of binary extension fields typically involves several considerations.
Generally, the Karatsuba algorithm and NTT excel under different operand size
ranges. Finding precise crossover points can be empirical and is often
dependent on hardware architecture, implementation details, and the specific
characteristics of the multiplication tasks. For sizes less than a few hundred
bits, the Karatsuba algorithm might perform better and for larger operand
sizes, e.g., several hundred bits or more, the NTT might outperform. In binary
fields, the bit sizes are directly related to the degrees $n$ of the
extensions. This motivates us to work with different ranges for $n$ starting
from 250. It is noteworthy that in some contexts the users can limit
themselves to other algorithms like Karatsuba’s one and can utilize our codes
in [26] to customize the values according to their needs.

##  3 Normal bases from Gauss periods

An early interest in normal bases may stem from the fact that Gauss [14] used
normal elements to show how to draw a regular polygon with ruler and compass
alone. This problem remained unsolved for more than 2000 years and he gave its
solution using elements that he called periods. Gauss’ insights laid the
foundation for many subsequent developments in theory as well as in practice.
Indeed, after approximately 200 years, in 1989 Ash, Blake, and Vanstone [1]
used these same periods to investigate low complexity normal bases over finite
fields.

######  Definition 3.

Let $q$ be a power of a prime number $p$. Let $r=nk+1$ be a prime number not
dividing $q$ and $\gamma$ a primitive $r$-th root of unity in
${\mathbb{F}}_{q^{nk}}$. Let $K$ be the unique subgroup of order $k$ of
${\mathbb{Z}}_{r}^{*}$ and ${\mathcal{K}}_{i}\subseteq{\mathbb{Z}}_{r}^{*}$ be
a coset of $K$ for $0\leq i\leq n-1$. The elements

$\alpha_{i}=\sum_{a\in{\mathcal{K}}_{i}}\gamma^{a}\in{\mathbb{F}}_{q^{n}},\
0\leq i\leq n-1$

are called Gauss period of type $(n,k)$ over ${\mathbb{F}}_{q}$.

After 10 years of Ash et al. [1] findings, Gao, Gathen, Panario, and Shoup
[11] showed how Gaussian normal bases of ${\mathbb{F}}_{q^{n}}$ over
${\mathbb{F}}_{q}$ can be adapted to NTT-like algorithms. In the following, we
highlight their strategy. Let
${\mathcal{N}}_{gp}=(\alpha_{0},\alpha_{1},\cdots,\alpha_{n-1})$ be a normal
basis of ${\mathbb{F}}_{q^{n}}$ over ${\mathbb{F}}_{q}$ generated by a Gauss
period $\alpha_{0}$ of type $(n,k)$. Let

$A=\sum_{0\leq i\leq n-1}a_{i}\alpha_{i},\ B=\sum_{0\leq i\leq
n-1}b_{i}\alpha_{i},\text{ and }C=\sum_{0\leq i\leq n-1}c_{i}\alpha_{i}$

the product of $A$ and $B$ computed in ${\mathcal{N}}_{gp}$ representation.
The equation

$A=\sum_{0\leq i\leq
n-1}a_{i}\sum_{j\in{\mathcal{K}}_{i}}\gamma^{j}=\sum_{1\leq j\leq
nk}a_{j}^{\prime}$

leads us to computations using polynomials of degree $\leq nk$. Indeed, let

$\Phi_{r}=x^{r}-1$

be the $r$ cyclotomic polynomial,
${\mathcal{L}}={\mathbb{F}}_{q}[X]/(\Phi_{r})$ the quotient ring and
$x=X\mod\Phi_{r}$. Then ${\mathcal{L}}$ has two power bases

$\\{1,\ x,\ \cdots,\ x^{nk-1}\\}\text{ and }\\{x,\ x^{2},\ \cdots,\ x^{nk}\\}$

over ${\mathbb{F}}_{q}$. The advantage of this change of representation is
that it is easy to go from one basis to another and the elements of
${\mathcal{L}}$ can be viewed as polynomials of degree less than $nk-1$ or
$nk$. The map

$\varphi:{\mathbb{F}}_{q^{n}}\longrightarrow{\mathcal{L}},\
A\longmapsto\sum_{1\leq j\leq nk}a_{j}^{\prime}x^{j}$

is a ring homomorphism with image $\varphi({\mathbb{F}}_{q^{n}})$ given by the
subring

${\mathcal{L}}_{1}=\\{c_{1}x+c_{2}x+\cdots+c_{nk}x^{nk}\in{\mathcal{L}}\ :\
c_{1},\cdots,c_{nk}\in{\mathbb{F}}_{q}\text{ and }c_{i}=c_{j}\text{ for }i,\
j\in{\mathcal{K}}_{i}\\}$

For every nonzero element $A$ of ${\mathbb{F}}_{q^{n}}$, $\varphi(A)$ can be
easily inverted. So, to compute $C$, we multiply $\varphi(A)$ and
$\varphi(B)$, perform the reduction in ${\mathcal{L}}$ and then invert the
result back to ${\mathbb{F}}_{q^{n}}$. This is how Gaussian normal bases are
tied to NTT-like algorithms. The basic idea is to convert the normal basis
representation to a polynomial basis in the ring ${\mathcal{L}}$, do fast
multiplication of polynomials in the ring, and then convert the result back to
the normal basis. We give a summary of the result in the following theorem,
for more details see [11, Section 4].

######  Theorem 1 ([11]).

Let ${\mathcal{N}}$ be a normal basis generated by a Gauss period of type
$(n,k)$ over ${\mathbb{F}}_{q}$. Then multiplication in ${\mathcal{N}}$ can be
computed with $O(nk\log(nk)\log\log(nk))$ operations in ${\mathbb{F}}_{q}$.

A normal basis generated by a Gauss period of type $(n,k)$ is often simply
called Gaussian normal basis (GNB) of type $k$. Theorem 1 shows that it is
very important to work with GNBs of small type. The parameter $k$ should be
kept as small as possible not only because of the cost of multiplication but
also for the structure of the multiplication table
${\mathrm{T}}_{{\mathcal{N}}}$ of ${\mathcal{N}}$. Indeed, as stated in
Proposition 1, in binary extensions the sparsity of
${\mathrm{T}}_{{\mathcal{N}}}$ depends on $k$.

######  Proposition 1 ([1, 2, 4]).

Let $n>3$ be an integer and ${\mathcal{N}}$ be a normal arising from a Gauss
period of type $(n,k)$ for ${\mathbb{F}}_{2^{n}}$ over ${\mathbb{F}}_{2}$. Let
${\mathcal{C}}_{{\mathcal{N}}}$ be the complexity of ${\mathcal{N}}$ in term
of number of nonzero elements of its multiplication table
${\mathrm{T}}_{{\mathcal{N}}}$.

  1. 1.

We have the following bounds on ${\mathcal{C}}_{{\mathcal{N}}}$.

$\begin{cases}kn-(k^{2}-3k+3)\leq{\mathcal{C}}_{{\mathcal{N}}}\leq(n-1)k+1\ \
\ \ \ \ \ \ \ \ \ \ \ \text{ if }k\text{ is even,}\\\
(k+1)n-(k^{2}-k+1)\leq{\mathcal{C}}_{{\mathcal{N}}}\leq(n-2)k+n+1\ \text{ if
}k\ \text{ is odd.}\end{cases}$

  2. 2.

If $1\leq k\leq 6$ then we have the following exact complexities:

     * •

If $k=1$ or $2$ then ${\mathcal{N}}$ is optimal and
${\mathcal{C}}_{{\mathcal{N}}}=2n-1$.

     * •

If $k=3$ or $4$ then ${\mathcal{C}}_{{\mathcal{N}}}=4n-7$.

     * •

If $k=5$ or $6$ then ${\mathcal{C}}_{{\mathcal{N}}}=6n-21$.

In practice, it is recommended to choose the type $k$ with the lowest
achievable complexity. So, in this paper, we work with Gauss periods of type
no more than 10. However, the reader should note that the algorithms (e.g.,
the Magma functions MultNBrange and ExtNBrange) we developed for the data in
Sections 4 and 5 can be extended to higher types $k$. We conclude this section
by giving a table of GNBs whose lowest types are less or equal to $10$ for
${\mathbb{F}}_{2^{n}}$ over ${\mathbb{F}}_{2}$, where $250\leq n\leq 600$. The
range

$250\leq n\leq 600$

is of particular interest for common implementations and we need the
properties (cost of multiplication, complexity) of GNBs in this range to work
with sub-normal elements in Section 5. Some more data related to Table 1 are
available in [15, 26].

$(n,k)$ | $(n,k)$ | $(n,k)$ | $(n,k)$ | $(n,k)$ | $(n,k)$ | $(n,k)$ | $(n,k)$ | $(n,k)$
---|---|---|---|---|---|---|---|---
250, 9 | 284, 3 | 326, 2 | 364, 3 | 407, 8 | 446, 6 | 491, 2 | 532, 3 | 572, 5
251, 2 | 285, 10 | 327, 8 | 367, 6 | 409, 4 | 447, 6 | 493, 4 | 534, 7 | 573, 4
252, 3 | 286, 3 | 329, 2 | 369, 10 | 410, 2 | 449, 8 | 494, 3 | 535, 4 | 574, 3
253, 10 | 287, 6 | 330, 2 | 370, 6 | 411, 2 | 451, 6 | 495, 2 | 537, 8 | 575, 2
254, 2 | 290, 5 | 331, 6 | 371, 2 | 412, 3 | 453, 2 | 498, 9 | 538, 6 | 577, 4
255, 6 | 291, 6 | 332, 3 | 372, 1 | 413, 2 | 458, 6 | 499, 4 | 540, 1 | 578, 6
257, 6 | 292, 1 | 334, 7 | 373, 4 | 414, 2 | 459, 8 | 501, 10 | 542, 3 | 579, 10
258, 5 | 293, 2 | 337, 10 | 374, 3 | 417, 4 | 460, 1 | 502, 10 | 543, 2 | 580, 3
259, 10 | 294, 3 | 338, 2 | 375, 2 | 418, 1 | 461, 6 | 503, 6 | 545, 2 | 581, 8
260, 5 | 297, 6 | 339, 8 | 378, 1 | 419, 2 | 462, 10 | 505, 10 | 546, 1 | 582, 3
261, 2 | 298, 6 | 340, 3 | 380, 5 | 420, 1 | 465, 4 | 506, 1 | 547, 10 | 583, 4
262, 3 | 299, 2 | 341, 8 | 381, 8 | 421, 10 | 466, 1 | 507, 4 | 548, 5 | 585, 2
263, 6 | 301, 10 | 342, 6 | 382, 6 | 423, 4 | 467, 6 | 508, 1 | 550, 7 | 586, 1
265, 4 | 302, 3 | 343, 4 | 385, 6 | 425, 6 | 469, 4 | 509, 2 | 551, 6 | 589, 4
266, 6 | 303, 2 | 345, 4 | 386, 2 | 426, 2 | 470, 2 | 510, 3 | 553, 4 | 591, 6
267, 8 | 305, 6 | 346, 1 | 387, 4 | 428, 5 | 471, 8 | 511, 6 | 554, 2 | 593, 2
268, 1 | 306, 2 | 347, 6 | 388, 1 | 429, 2 | 473, 2 | 513, 4 | 555, 4 | 595, 6
269, 8 | 307, 4 | 348, 1 | 390, 3 | 430, 3 | 474, 5 | 515, 2 | 556, 1 | 596, 3
270, 2 | 310, 6 | 349, 10 | 391, 6 | 431, 2 | 475, 4 | 516, 3 | 557, 6 | 597, 4
271, 6 | 311, 6 | 350, 2 | 393, 2 | 433, 4 | 476, 5 | 517, 4 | 558, 2 | 599, 8
273, 2 | 313, 6 | 351, 10 | 394, 9 | 434, 9 | 478, 7 | 519, 2 | 559, 4 |
274, 9 | 314, 5 | 354, 2 | 395, 6 | 435, 4 | 479, 8 | 522, 1 | 561, 2 |
276, 3 | 315, 8 | 355, 6 | 397, 6 | 438, 2 | 481, 6 | 523, 10 | 562, 1 |
277, 4 | 316, 1 | 356, 3 | 398, 2 | 439, 10 | 482, 5 | 524, 5 | 564, 3 |
278, 2 | 319, 4 | 357, 10 | 401, 8 | 441, 2 | 483, 2 | 525, 8 | 565, 10 |
279, 4 | 322, 6 | 358, 10 | 402, 5 | 442, 1 | 484, 3 | 526, 3 | 566, 3 |
281, 2 | 323, 2 | 359, 2 | 404, 3 | 443, 2 | 486, 10 | 527, 6 | 567, 4 |
282, 6 | 324, 5 | 362, 5 | 405, 4 | 444, 5 | 487, 4 | 530, 2 | 570, 5 |
283, 6 | 325, 4 | 363, 4 | 406, 6 | 445, 6 | 490, 1 | 531, 2 | 571, 10 |
Table 1: GNBs of type $\leq 10$ for ${\mathbb{F}}_{2^{n}}$ over
${\mathbb{F}}_{2}$, where $250\leq n\leq 600$.

##  4 Normal bases from algebraic groups

After 10 years of Gao et al.’s work on fast computation using Gauss periods
[11], Couveignes and Lercier [6] presented an alternative approach to the
construction of efficient normal bases by introducing elliptic periods. These
bases leverage the properties of elliptic curves, making it easier to expand
the range of cases where they exist. Another 10 years later, Ezome and Sall
[7] applied a similar strategy to all remaining $1-$dimensional algebraic
groups over a finite field ${\mathbb{F}}_{q}$.

######  Proposition 2 ([21], Chapter II, Section 3).

Any $1-$dimensional connected algebraic group over a perfect field
${\mathbb{K}}$ is isomorphic to one of the following:

  1. 1.

an elliptic curve group $E$,

  2. 2.

an additive group ${\mathbb{G}}_{a}$,

  3. 3.

multiplicative groupe ${\mathbb{G}}_{m}$, or

  4. 4.

Lucas torus ${\mathbb{T}}_{\alpha}:x^{2}-\alpha y^{2}=1$

We recall that any finite field is a perfect field. The following theorem
summarizes all the results on normal bases and fast multiplication derived
from $1-$dimensional algebraic groups.

######  Theorem 2 ([6, 7]).

Let ${\mathrm{G}}$ be a $1-$dimensional algebraic group over
${\mathbb{F}}_{q}$ and $t\in{\mathrm{G}}$ a point of order $n$. Let
${\mathrm{H}}={\mathrm{G}}/(t)$ and
$I:{\mathrm{G}}\longrightarrow{\mathrm{H}}$ the isogegy quotient. Let $a$ be a
point of ${\mathrm{H}}({\mathbb{F}}_{q})$ such that $I^{-1}(a)$ is irreducible
over ${\mathbb{F}}_{q}$. Then ${\mathbb{F}}_{q}(I^{-1}(a))$ is a cyclic
extension of ${\mathbb{F}}_{q}$ of degree $n$. Let ${\mathcal{L}}$ be a linear
space given by functions over $\bar{{\mathbb{F}}}_{q}({\mathrm{G}})$. Assume
there is a point $R\in{\mathrm{G}}({\mathbb{F}}_{q})$ such that the
application

$f\longmapsto(f(R+jt))_{0\leq j\leq n-1}$

is a bijection from ${\mathcal{L}}$ to ${\mathbb{F}}_{q}^{n}$. Then there is a
normal basis ${\mathcal{N}}_{ag}$ of ${\mathbb{F}}_{q^{n}}$ over
${\mathbb{F}}_{q}$ with NTT-like multiplication algorithm.

In the algebraic approach, first of all, we need to construct an extension
${\mathbb{L}}$ of degree $n$ of a field ${\mathbb{K}}$ using the properties of
an appropriate algebraic group ${\mathrm{G}}$. Note that in this section,
${\mathbb{L}}$ is equal to the finite field ${\mathbb{F}}_{q^{n}}$. The
geometric origin of this extension results in a nice description of
${\mathbb{K}}$-automorphisms of ${\mathbb{L}}$. Indeed, let $b\in I^{-1}(a)$
and $O$ the identity element of ${\mathrm{G}}$. Let $(*_{G})$ be the group law
of $({\mathrm{G}},*_{G})$ and by restriction $(*_{H})$ be the law in the
subgroup ${\mathrm{H}}$. Since

$I(t*_{G}b)=I(t)*_{H}I(b)=O*_{H}a=a$

then $t*_{G}b$ is Galois conjugated to $b$ and all conjugates are obtained
that way from all $n-$torsion points $(kt)_{0\leq k\leq n-1}$ in the subgroup
${\mathrm{T}}$ of order $n$ generated by $t$. So we have an isomorphism

$\psi:t\longmapsto\varphi_{t}$

between ${\mathrm{T}}$ and the Galois group of ${\mathbb{L}}$ over
${\mathbb{K}}$, where $\varphi_{t}$ is the residual automorphism

$b\in I^{-1}(a)\longmapsto b*_{G}t.$

In the context of the four algebraic groups enumerated in Proposition 2, the
geometric formulas that describe the translation $x\mapsto x*_{G}t$ in
${\mathrm{G}}$ give a nice description of the Galois group of ${\mathbb{L}}$
over ${\mathbb{K}}$, which leads to a succinct construction of
${\mathcal{N}}_{ag}$. For more details see [6, 7].
The linear space ${\mathcal{L}}$ of dimension $n$ plays a central role in the
computation over ${\mathcal{N}}_{ag}$. It results from the theory of divisors
over algebraic groups. For example, we can define ${\mathcal{L}}$ as follows:

${\mathcal{L}}=\\{f\in\bar{{\mathbb{K}}}({\mathrm{G}})\ :\
div(f)\geq-D\\}\cup\\{0\\}$

where $div(f)$ represents the divisor of any function $f$ over ${\mathrm{G}}$
and

$D=\sum_{0\leq k\leq n-1}k(t)$

is the divisor given by the formal sum of the points in ${\mathrm{T}}$. For
more details on the theory of divisors we refer to [29, Chapter 2, Section 3].
The main advantage of ${\mathcal{L}}$ is that it allows a bijective
correspondence

${\mathcal{L}}\longleftrightarrow{\mathbb{F}}_{q}^{n}\longleftrightarrow{\mathbb{F}}_{q^{n}}$

between functions on ${\mathrm{G}}$ and scalars in ${\mathbb{F}}_{q}$ given by
a representation in the normal basis ${\mathcal{N}}_{ag}$ of
${\mathbb{F}}_{q^{n}}$ over ${\mathbb{F}}_{q}$. This correspondence is
possible because ${\mathcal{N}}_{ag}$ is obtained by evaluating the elements
of a basis ${\mathcal{B}}$ of ${\mathcal{L}}$ at the
${\mathbb{F}}_{q^{n}}-$rational point $b\in I^{-1}(a)$. Even if we are in
different algebraic settings, the reader can note the similarity between the
importance of the linear space ${\mathcal{L}}$ and the ring ${\mathcal{L}}$
used in the Gaussian normal basis fast multiplication algorithm. This is why
we gave the same notation.

The element $R$ is an ${\mathbb{F}}_{q}-$rational point of ${\mathrm{G}}$ and
as outlined in Theorem 2 it is core to fast multiplication in a normal basis
from algebraic group. The multiplication tensor of ${\mathcal{N}}_{ag}$ is
based on evaluation and interpolation, and involves additions, subtractions,
component-wise products, and convolution products between vectors of length
$n$. The first three operations are very easy to perform, and the latter one
can be seen as a polynomial multiplication. This is how normal bases from
algebraic groups (NBAGs) are tied to NTT-like algorithms. For more details in
the study of fast algorithms and convolution products, we refer to [12] and to
see how it is applied to normal basis construction, we refer to [6, 7].

Each algebraic group mentioned in Proposition 2 possesses unique strengths and
limitations. The Lucas Torus, specifically, operates exclusively within finite
fields where the characteristic is $p\neq 2$. As such, since we are in the
context of binary field extensions it falls outside the scope of our study.
Normal bases derived from both additive and multiplicative groups offer the
additional benefit of featuring a sparse multiplication table. Nonetheless,
they are particularly well-suited for Artin-Schreier and Kummer extensions.

The main advantage of elliptic normal bases (ENBs) over GNBs and other normal
bases from algebraic groups is that for a given finite field
${\mathbb{F}}_{q}$ we can define many elliptic curves. This characteristic
significantly expands the range of cases where a normal basis, employing an
NTT-like algorithm, can exist. However, it’s crucial to note that implementing
an elliptic normal basis is a complex task. Furthermore, as demonstrated in
the following lemma (derived from Theorem 2), the degree $n$ should not be
excessively large.

######  Lemma 1 ([6]).

Let $p$ be a prime number, $q$ a power of $p$, and $n\geq 2$ an integer. Let
$\ell$ be any prime number and $v_{\ell}$ the valuation associated to $\ell$.
We denote by $n_{q}$ the unique positive integer satisfying

  * •

$v_{\ell}(n_{q})=v_{\ell}(n)$ if $\ell$ is coprime with $q-1$,

  * •

$v_{\ell}(n_{q})=0$ if $v_{\ell}(n)=0$,

  * •

$v_{\ell}(n_{q})=\mathrm{max}\\{2v_{\ell}(q-1)+1,2v_{\ell}(n)\\}$ if
$\ell|q-1$ and $\ell|n$.

If $n_{q}\leq\sqrt{q}$, then there exists an elliptic curve $E$ over
${\mathbb{F}}_{q}$ with a point $t$ of order $n$, a point $b$ in
$E({\mathbb{F}}_{q^{n}})$, and a ${\mathbb{F}}_{q}-$rational point $R$ outside
of $E[n]$. These points allow the construction of an elliptic normal basis
with NTT-like multiplication algorithms.

The assumption $n_{q}\leq\sqrt{q}$ poses a significant constraint in
applications involving binary field extensions
${\mathbb{F}}_{2^{n}}/{\mathbb{F}}_{2}$, primarily due to the inherent
difficulty of finding a suitable elliptic curve over $\mathbb{F}_{2}$.
Although a workaround is proposed in [6], the devised strategy introduces
numerous ad hoc redundant representations, making practical implementation
challenging. In the subsequent sections, we leverage the architecture and
software design of computers to demonstrate an efficient implementation of
elliptic normal bases on binary field extensions.

###  4.1 Choice of good embedding degrees

In the realm of finite field arithmetic, the efficiency of various operations,
such as addition and multiplication relies on the chosen representation for
the elements. While Zech logarithms could be applicable for small-sized
fields, these methods become impractical for larger finite fields commonly
employed in modern public key cryptography. Consequently, it is customary to
leverage an explicit isomorphism between the field ${\mathbb{F}}_{q^{n}}$ and
the corresponding vector space ${\mathbb{F}}_{q}^{n}$, achieved through a
carefully selected basis.
As obtaining a straightforward isomorphism proves challenging within the
framework of elliptic normal bases of ${\mathbb{F}}_{2^{n}}$ over
${\mathbb{F}}_{2}$, this section capitalizes on the implementation of Zech
logarithms, exploits the characteristics of computer registers, and utilizes
the embedding of finite fields. These measures are employed to enable better
functionality of elliptic normal bases over binary extensions. The basic idea
is based on the following scheme

${\mathbb{F}}_{2}$${\mathbb{F}}_{2^{e}}$${\mathbb{F}}_{2^{n}}$$e$$d$

where ${\mathbb{F}}_{2^{e}}$ is a subfield of ${\mathbb{F}}_{2^{n}}$, and the
degrees of the extensions ${\mathbb{F}}_{2^{n}}/{\mathbb{F}}_{2^{e}}$ and
${\mathbb{F}}_{2^{e}}/{\mathbb{F}}_{2}$ are respectively equal to $d$ and $e$.
To perform operations (e.g., multiplication) in ${\mathbb{F}}_{2^{n}}$ we
split the computations in two stages. Initially, we focus on identifying a
suitable normal basis for ${\mathbb{F}}_{2^{n}}/{\mathbb{F}}_{2^{e}}$ by
leveraging algebraic group properties. We keep the degree $e$ as small as
possible so that the computations in ${\mathbb{F}}_{2^{e}}/{\mathbb{F}}_{2}$
will be very easy to perform. For example, we can choose $e$ such that
multiplication and addition can be done through a Zech logarithms table. The
goal is to have the smallest embedding degree $e$ while ensuring
$n_{q}\leq\sqrt{q}$, where $q=2^{e}$. So, a natural question is how to upper
bound $e$? We will do that based on computer architecture and some software
design.

In CPUs and digital systems, the execution of operations within binary finite
fields is commonly achieved through the utilization of registers and
combinational logic circuits. Registers, serving as high speed data storage
elements in processors, store information on which combinational logic
circuits perform operations. For instance, in the case of addition or XOR
operations, the contents of two registers are XORed bit by bit to generate the
sum.

Multiplication, on the other hand, entails a sequence of XOR and bit-shift
operations. The multiplicand and multiplier are loaded into registers, and the
product is accumulated through a series of XOR and shift operations. The final
result undergoes reduction modulo an irreducible polynomial. The
implementation of these operations relies on fundamental components of digital
circuits, including XOR gates, AND gates, OR gates, and shift registers.

This underscores the importance of choosing embedding degrees of $2^{k}$,
typically with $k$ values such as 4, 5, or 6, corresponding to register sizes
of 16, 32, and 64. Opting for smaller data sizes, like 16 bits, reduces the
memory footprint of data structures and variables compared to larger sizes
such as 32 or 64 bits. Moreover, in real-time systems where timely and
predictable responses are crucial, using smaller data sizes can enhance
execution speed by processing smaller data chunks in each operation. To meet
the requirement of facilitating easy computations in ${\mathbb{F}}_{2^{e}}$,
it is advisable to select embedding degrees no greater than 16.

Beyond considerations of CPU micro-architecture, the design of certain
software can further support the rationale behind opting for a modest
embedding degree. For instance, within the Magma system [3], arithmetic
operations in small non-prime finite fields are facilitated through Zech
logarithm tables. When the field ${\mathbb{F}}_{2^{e}}$ is sufficiently
compact to be represented using Zech logarithms, the output of elements is
formatted as powers of a primitive element that generates
${\mathbb{F}}_{2^{e}}$. The following Magma code

        for e in [2..20] do
             F := GF(2^e); AssertAttribute(F, "PowerPrinting", true);
             print Random(F);
        end for;

prints the elements of ${\mathbb{F}}_{2^{e}}$, for $2\leq e\leq 20$ in power
mode. However, if we go beyond $20$ even if the function AssertAttribute is
set to ‘true’, the current version of the Magma system returns the following
statement

         Runtime error in ‘AssertAttribute’: Power printing is not
         available for this kind of field

and starts representing elements using polynomials. This means at this point
we can’t use Zech logarithms for field representation. So taking this fact
into account we can also choose a small embedding degree $e\leq 20$.

By synthesizing the two justifications outlined in the preceding paragraphs,
this paper focuses on small embedding degrees $e\leq 20$. It’s worth noting
that, upon reviewing Table 2, most extensions
${\mathbb{F}}_{2^{n}}/{\mathbb{F}}_{2}$ exhibit embedding degrees of 16 or
less. As mentioned earlier, the value 16 holds particular significance due to
its alignment with CPU micro-architecture. To illustrate the devised strategy
clearly, we provide the following example.

######  Example 1.

Let $n=507$, using the divisors of $n$, we get the following diagram.

${\mathbb{F}}_{2}$${\mathbb{F}}_{2^{3}}$${\mathbb{F}}_{2^{507}}$$3$$169$${\mathbb{F}}_{2}$${\mathbb{F}}_{2^{13}}$${\mathbb{F}}_{2^{507}}$$13$$39$${\mathbb{F}}_{2}$${\mathbb{F}}_{2^{169}}$${\mathbb{F}}_{2^{507}}$$169$$3$

The smallest embedding degree $e$ for which $n_{q}\leq\sqrt{q}$, where
$q=2^{e}$, is $13$. For a counterexample, there is no embedding degree $e\leq
20$ satisfying the condition $n_{q}\leq\sqrt{q}$ if $n=500$. That is why this
value is missing in Table 2.

###  4.2 Table for efficient computations

The data table presented in this section primarily relies on normal bases
derived from elliptic curves. Given the close correlation between the
existence of a suitable curve and the integer $n_{q}$ as defined in Lemma 1,
it becomes imperative to comprehend its inherent properties.

######  Property 1.

Let $p$ be a prime, $q$ a power of $p$. Let $n\geq 2$ and $e\geq 1$ be two
integers. We denote by $\varphi$ the Euler function.

  1. 1.

If $n$ is prime to $q-1$ then $n_{q}=n$.

  2. 2.

If $e$ is prime to $n\varphi(n)$ then $n_{q}=n_{q^{e}}$.

  3. 3.

If $q-1$ is squarefree then $n_{q}\leq n^{3}$.

  4. 4.

In any case $n_{q}\leq n^{2}(q-1)^{2}$.

The algorithms, as described in [26], that lead to the creation of Table 2 are
notably influenced by the parameter $n_{q}$. To provide a tangible perspective
on this value, we offer the following example featuring two instances of the
pair $(n,q)$.

######  Example 2.

The initial instance involves a finite field with a characteristic distinct
from $2$, while the second instance pertains to binary extensions.

  1. 1.

We consider the finite field extension ${\mathbb{F}}_{q^{n}}$ where $n=10$ and
$q=42989$. Since $n=2\times 5$ then $2$ and $5$ are the only primes $\ell$
that appear in the decomposition of $n_{q}$. So computing $n_{q}$ amounts to
finding $v_{2}(n_{q})$ and $v_{5}(n_{q})$. We have the following factorization
of

$q-1=2^{2}\times 11\times 977.$

Since $2$ divides both $n$ and $q-1$, by the third point of Lemma 1
$v_{2}(n_{q})=5$. Since $5$ is prime to $q-1$, by the first point of this
lemma $v_{5}(n_{q})=v_{5}(n)=1$. So finally, we have

$n_{q}=2^{5}\times 5=160.$

  2. 2.

We consider the binary field extension ${\mathbb{F}}_{2^{976}}$ over
${\mathbb{F}}_{2^{16}}$. So, for this instance $q=2^{16}$ and the degree of
the extension $n=61$. Since

$gcd(61,\ 2^{16}-1)=1,$

by Point (1) of Property 1, $n_{q}=n=61$. In this case, we can construct an
efficient elliptic normal basis because we have the sufficient condition
$n_{q}\leq\sqrt{q}$.

We can now compile Table 2, presenting a comprehensive list of elliptic normal
bases with embedding degrees $embed\leq 20$ within the range $500\leq n\leq
1000$. This particular range has been selected to accommodate highly demanding
applications. However, utilizing our algorithms detailed in [26], readers can
easily customize the values and generate a table tailored to their specific
requirements.

$n$ | $embed$ | $n$ | $embed$ | $n$ | $embed$ | $n$ | $embed$ | $n$ | $embed$
---|---|---|---|---|---|---|---|---|---
507 | 13 | 611 | 13 | 714 | 17 | 817 | 19 | 931 | 19
510 | 15 | 612 | 17 | 715 | 13 | 819 | 13 | 935 | 17
512 | 16 | 615 | 15 | 720 | 15 | 825 | 15 | 936 | 13
513 | 19 | 616 | 14 | 722 | 19 | 826 | 14 | 938 | 14
516 | 12 | 624 | 13 | 728 | 13 | 828 | 18 | 940 | 20
518 | 14 | 627 | 19 | 731 | 17 | 832 | 13 | 944 | 16
520 | 13 | 629 | 17 | 732 | 12 | 833 | 17 | 949 | 13
522 | 18 | 636 | 12 | 736 | 16 | 836 | 19 | 950 | 19
527 | 17 | 637 | 13 | 738 | 18 | 840 | 20 | 952 | 14
528 | 12 | 640 | 20 | 740 | 20 | 845 | 13 | 954 | 18
532 | 14 | 644 | 14 | 741 | 13 | 846 | 18 | 960 | 15
533 | 13 | 645 | 15 | 742 | 14 | 848 | 16 | 962 | 13
540 | 15 | 646 | 17 | 744 | 12 | 850 | 17 | 969 | 17
544 | 17 | 650 | 13 | 748 | 17 | 854 | 14 | 975 | 13
546 | 13 | 656 | 16 | 750 | 15 | 855 | 15 | 976 | 16
551 | 19 | 658 | 14 | 752 | 16 | 858 | 13 | 980 | 14
552 | 12 | 660 | 15 | 754 | 13 | 860 | 20 | 986 | 17
555 | 15 | 663 | 13 | 760 | 19 | 867 | 17 | 988 | 13
558 | 18 | 665 | 19 | 765 | 15 | 868 | 14 | 990 | 15
559 | 13 | 666 | 18 | 767 | 13 | 870 | 15 | 992 | 16
560 | 14 | 675 | 15 | 768 | 12 | 871 | 13 | 994 | 14
561 | 17 | 676 | 13 | 770 | 14 | 874 | 19 |  |
564 | 12 | 680 | 17 | 774 | 18 | 884 | 13 |  |
570 | 15 | 684 | 19 | 779 | 19 | 885 | 15 |  |
572 | 13 | 686 | 14 | 780 | 13 | 893 | 19 |  |
574 | 14 | 688 | 16 | 782 | 17 | 896 | 14 |  |
576 | 18 | 689 | 13 | 784 | 14 | 897 | 13 |  |
578 | 17 | 690 | 15 | 792 | 18 | 900 | 15 |  |
580 | 20 | 696 | 12 | 793 | 13 | 901 | 17 |  |
585 | 13 | 697 | 17 | 795 | 15 | 910 | 13 |  |
589 | 19 | 700 | 14 | 798 | 19 | 912 | 19 |  |
592 | 16 | 702 | 13 | 799 | 17 | 915 | 15 |  |
595 | 17 | 703 | 19 | 806 | 13 | 918 | 17 |  |
598 | 13 | 704 | 16 | 810 | 15 | 920 | 20 |  |
600 | 15 | 705 | 15 | 812 | 14 | 923 | 13 |  |
608 | 16 | 708 | 12 | 816 | 17 | 928 | 16 |  |
Table 2: ${\mathbb{F}}_{2^{n}}$ with ENB of embedding degree $\leq 20$ for
$500\leq n\leq 1000$.

######  Remark 1.

In Table 2, our primary emphasis lies on elliptic normal bases due to their
expansive range of possibilities compared to other bases. However, a normal
basis derived from the multiplicative group, aside from being easily
implementable, can exhibit superior characteristics when it is available. For
instance, our Magma function, named MultNBrange [26], executed within the
range $500\leq n\leq 1000$, yields embedding degrees of $9$ and $11$ for
respective values of $657$ and $979$. Although such cases are relatively
scarce, they seem to offer improved computational efficiency when encountered.
Note that there is no ENB with embedding degree $\leq 20$ when $n$ is equal to
$657$ or $979$.

##  5 Computation using sub-normal elements

Polynomial bases and normal bases from Gauss periods and $1-$dimensional
algebraic groups are not the only bases of ${\mathbb{F}}_{q^{n}}$ over
${\mathbb{F}}_{q}$ that allow fast multiplication using NTT-like algorithms.
Indeed, as shown by Thomson and Weir [30] and then Ezome and Sall [8], we can
take advantage of Artin-Schreier-Witt and Kummer theory to construct bases
that are not normal basis but can exploit the advantageous properties of
normal elements. For binary extensions, these bases are obtained by extending
(if possible) an appropriate normal basis of ${\mathbb{F}}_{2^{n/2}},\
{\mathbb{F}}_{2^{n/3}},$ or ${\mathbb{F}}_{2^{n/4}}$ over ${\mathbb{F}}_{2}$.
The goal of this section is to compile a table that reports the integers $n$
for which a GNB of type less than 10 does not exist. As a workaround, we
precise the feasibility of working with normal element extensions or elliptic
normal bases with small embedding degrees. Before delving into this analysis,
it is crucial to comprehend the conditions under which a Gauss period of type
$(n,k)$ over ${\mathbb{F}}_{q}$ generates a normal basis. This inquiry is
generally addressed by the Wasserman condition [31]. We present the refined
version for binary extensions.

######  Theorem 3.

There exists a Gaussian normal basis of ${\mathbb{F}}_{2^{n}}$ over
${\mathbb{F}}_{2}$ if and only if $8$ does not divide $n$.

Utilizing Theorem 3 and algorithms developed in [8, 30], we can broaden the
scope of cases where multiplication in ${\mathbb{F}}_{2^{n}}/{\mathbb{F}}_{2}$
can be efficiently performed through NTT-like algorithms and normal elements.
The basic idea is as follows: if there are no efficient normal bases of
${\mathbb{F}}_{2^{n}}/{\mathbb{F}}_{2}$, one may hope that $n$ has a proper
divisor $d$ such that ${\mathbb{F}}_{2^{d}}/{\mathbb{F}}_{2}$ admits an
efficient normal basis
${\mathcal{N}}=\\{\alpha,\alpha^{2},\cdots,\alpha^{2^{d-1}}\\}$. We consider
the cases where $d$ is chosen to be either $n/2$, $n/4$, or $n/3$, aligning
with values that are respectively effective in Artin-Schreir theory and its
generalization to Witt vectors and Kummer theory. The following theorem gives
a summary of the result derived from the first two theories. For background on
Artin-Schreir theory and Witt vectors, we refer the reader to [32] and [8,
Section 2.2].

######  Theorem 4 ([8, 30]).

Let ${\mathcal{N}}=\\{\alpha,\alpha^{2},\cdots,\alpha^{2^{d-1}}\\}$ be a
normal basis of ${\mathbb{F}}_{2^{d}}/{\mathbb{F}}_{2}$. Then there exists
${\mathfrak{a}}\in{\mathbb{F}}_{2^{2d}}$ and ${\mathfrak{b}}_{0}$ and
${\mathfrak{b}}_{1}$ in ${\mathbb{F}}_{2^{4d}}$ such that

${\mathcal{A}}={\mathcal{N}}\cup{\mathfrak{a}}{\mathcal{N}}$

is a basis of ${\mathbb{F}}_{2^{2d}}$ over ${\mathbb{F}}_{2}$ define as a
degree 2 Artin-Schreier extension of ${\mathcal{N}}$ and

$\mathcal{W}=(\mathcal{N}\cup{\mathfrak{b}}_{0}\mathcal{N})\cup{\mathfrak{b}}_{1}(\mathcal{N}\cup{\mathfrak{b}}_{0}\mathcal{N})$

is a basis of ${\mathbb{F}}_{2^{4d}}$ over ${\mathbb{F}}_{2}$ define as a
degree 4 Artin-Schreier-Witt extension of ${\mathcal{N}}$. If $d$ is odd we
can directly construct $\mathcal{W}$ as a degree 2 extension of
${\mathcal{A}}$.

  1. 1.

The cost of multiplication in ${\mathcal{A}}$ consists in at most 3
multiplications and 4 additions between elements lying in
${\mathbb{F}}_{2^{d}}$ and 1 vector-matrix multiplication between a vector of
${\mathbb{F}}_{2^{d}}/{\mathbb{F}}_{2}$ and the multiplication table of
${\mathcal{N}}$.

  2. 2.

The cost of multiplication in ${\mathcal{W}}$ consists in at most 9
multiplications, 33 additions between elements lying in
${\mathbb{F}}_{2^{d}},$ and 9 vector-matrix multiplications between a vector
of ${\mathbb{F}}_{2}^{d}$ and the multiplication table of ${\mathcal{N}}$.

  3. 3.

If ${\mathcal{N}}$ has subquadratic cost of multiplication and subquadratic
complexity, then ${\mathcal{A}}$ and ${\mathcal{W}}$ have also sub-quadratic
cost of multiplication.

Let $A\in{\mathbb{F}}_{2^{2d}}$, then $A$ can be represented in the extended
basis ${\mathcal{A}}$ as

$A=A_{0}+{\mathfrak{a}}A_{1},\text{ where
}A_{0}=\sum_{i=0}^{d-1}a_{0i}\alpha^{2^{i}}\text{ and
}A_{1}=\sum_{j=0}^{d-1}a_{1j}\alpha^{2^{j}}.$

We can represent an element $B$ of ${\mathbb{F}}_{2^{4d}}$ in ${\mathcal{W}}$
in a similar way. So, it is clear that if ${\mathcal{N}}$ supports an NNT-like
algorithm, then so does ${\mathcal{A}}$ and ${\mathcal{W}}$, and a natural
question is how to choose ${\mathcal{N}}$?

Theorem 4 shows that it is important to find a normal basis ${\mathcal{N}}$
with NTT-like algorithm and such that its multiplication table
${\mathrm{T}}_{{\mathcal{N}}}$ is as sparse as possible. This property is
featured by normal bases from additive and multiplicative groups and according
to Theorem 1 and Proposition 1 Gauss periods of small type $(d,k)$ are also
good candidates. Unfortunately, in terms of multiplication with an NTT-like
method, the first two bases are not adapted to extensions of the form
${\mathbb{F}}_{2^{d}}/{\mathbb{F}}_{2}$. For example, as shown in [7, Theorem
1], in order to tie a normal basis from the additive group to NTT-like
algorithms the base field ${\mathbb{F}}_{p}$ should be a proper subfield of
${\mathbb{F}}_{q}$, the underlying field of ${\mathbb{F}}_{q^{n}}$. This
requirement is impossible in the situation of this section. On the other hand,
elliptic normal bases have fast multiplication algorithms but it is hard to
expect a low complexity from them (see the recent preprint by Panario, Sall,
and Wang [25]). Consequently, to the best of our knowledge, Gaussian normal
bases of low types are the best candidates to work with Artin-Schreier-Witt
extensions of ${\mathbb{F}}_{2^{n}}$ over ${\mathbb{F}}_{2}$.

To establish Table 3 we work with the range $1000\leq n\leq 1200$ in order to
go beyond the possibilities given in Table 2. However, the interested readers
can customize the values and generate a table tailored to their specific
requirements using the algorithms available in [26]. In this section, for the
given range, we report the integers $n$ for which there is no GNB of type
$\leq 10$. Next, for $d\in\\{n/2,\ n/3,\ n/4\\}$ we check if
${\mathbb{F}}_{2^{d}}/{\mathbb{F}}_{2}$ has a GNB of type $k\leq 10$. In the
table, if possible, $(d,k)$ is defined for each of the three types of extended
bases: ${\mathcal{A}},\ {\mathcal{W}},$ and ${\mathcal{K}}$. The Kummer basis
extensions, defined by the column ${\mathcal{K}}$, are obtained from Theorem
5. Note that these extensions work for $d=n/3$ and contrary to Artin-Schreir-
Witt extensions we need the additional condition $3\ |\ 2^{n}-1$. Finally as
an additional study, in the column ${\mathcal{E}}$, we check if an elliptic
normal basis with embedding degree $\leq 20$ exists for the extension
${\mathbb{F}}_{2^{n}}/{\mathbb{F}}_{2}$. If such an ${\mathcal{E}}$ exists we
note the corresponding embedding degree, if not we leave the field blank.

######  Theorem 5 ([8]).

Let $d$ be a positive integer such that $3$ divides $2^{d}-1$. Assume that
${\mathcal{N}}=\\{\alpha,\alpha^{2},\cdots,\alpha^{2^{d-1}}\\}$ is a primitive
normal basis ${\mathbb{F}}_{2^{d}}/{\mathbb{F}}_{2}$. Then there exists
$\beta$ in ${\mathbf{F}}_{2^{3d}}$ such that
$\Omega={\mathcal{N}}\cup\beta{\mathcal{N}}\cup\beta^{2}{\mathcal{N}}$ is a
degree $3$ Kummer extension of ${\mathcal{N}}$.

  1. 1.

The complexity of $\Omega$ consists of at most 6 multiplications and 15
additions between elements of ${\mathbb{F}}_{2^{d}}$, 2 vector-matrix
multiplications between vectors in ${\mathbb{F}}_{2}^{d}$ and the
multiplication table of ${\mathcal{N}}$.

  2. 2.

If ${\mathcal{N}}$ has subquadratic complexity and subquadratic weight in $d$,
then $\Omega$ has also subquadratic complexity in $d$.

The following Magma code

        KL := [339, 349, 351, 358, 359, 364, 381, 387, 397];
        for d in KL do
            if (2^d-1) mod 3 eq 0 then print d; end if;
        end for;

returns only 358 and 364, which means the integers $d$ satisfying the
additional condition $3$ divides $2^{d}-1$ correspond respectively to the
values $n=1074$ and $n=1092$ in Table 3. Furthermore, in the case of Kummer
extensions we may need a primitive normal element and it is shown in [19] such
element exists for any finite field extension
${\mathbb{F}}_{q^{n}}/{\mathbb{F}}_{q}$. Note that looking for a concrete
normal element and assessing its properties (e.g., being primitive or
efficient or having low complexity) can be resource-demanding [22] and is out
of the scope of our study. However, we can read the following conjecture in
[10]. For any positive integer $d$ not divisible by 8, there exists an integer
$k>1$ such that the Gauss period of type $(d,k)$ is primitive normal in
${\mathbb{F}}_{2^{n}}$ over ${\mathbb{F}}_{2}$. An experimental study
indicates that this is true for all $d<569$. Except the five cases where
$d\in\\{571,\ 572,\ 575,\ 580,\ 596\\}$ all the underlying Gaussian normal
bases in Table 3 satisfy this range. Since the excepted values do not concern
Kummer extensions, there is a high probability of getting an appropriate
primitive Gaussian normal basis that works well for our study.

$n$ | ${\mathcal{A}}$ | ${\mathcal{W}}$ | ${\mathcal{K}}$ | ${\mathcal{E}}$ | $n$ | ${\mathcal{A}}$ | ${\mathcal{W}}$ | ${\mathcal{K}}$ | ${\mathcal{E}}$
---|---|---|---|---|---|---|---|---|---
1000 |  | (250, 9) |  |  | 1109 |  |  |  |
1007 |  |  |  | 19 | 1111 |  |  |  |
1008 |  | (252, 3) |  |  | 1112 | (556, 1) | (278, 2) |  |
1016 | (508, 1) | (254, 2) |  |  | 1114 | (557, 6) |  |  |
1017 |  |  | (339, 8) |  | 1120 |  |  |  | 14
1024 |  |  |  | 16 | 1128 | (564, 3) | (282, 6) |  |
1028 |  | (257, 6) |  |  | 1132 | (566, 3) | (283, 6) |  |
1032 | (516, 3) | (258, 5) |  |  | 1136 |  | (284, 3) |  | 16
1040 |  | (260, 5) |  | 13 | 1139 |  |  |  | 17
1042 |  |  |  |  | 1141 |  |  |  |
1047 |  |  | (349, 10) |  | 1142 | (571, 10) |  |  |
1048 | (524, 5) | (262, 3) |  |  | 1143 |  |  | (381, 8) |
1051 |  |  |  |  | 1144 | (572, 5) | (286, 3) |  | 13
1053 |  |  | (351, 10) | 13 | 1149 |  |  |  |
1056 |  |  |  |  | 1150 | (575, 2) |  |  |
1058 |  |  |  |  | 1152 |  |  |  | 18
1059 |  |  |  |  | 1153 |  |  |  |
1064 | (532, 3) | (266, 6) |  | 14 | 1160 | (580, 3) | (290, 5) |  | 20
1072 |  | (268, 1) |  | 16 | 1161 |  |  | (387, 4) |
1073 |  |  |  |  | 1163 |  |  |  |
1074 | (537, 8) |  | (358, 10) |  | 1168 |  | (292, 1) |  | 16
1077 |  |  | (359, 2) |  | 1175 |  |  |  |
1079 |  |  |  | 13 | 1176 |  | (294, 3) |  |
1080 | (540, 1) | (270, 2) |  | 15 | 1177 |  |  |  |
1081 |  |  |  |  | 1180 |  |  |  | 20
1085 |  |  |  |  | 1181 |  |  |  |
1088 |  |  |  | 17 | 1184 |  |  |  | 16
1092 | (546, 1) | (273, 2) | (364, 3) | 13 | 1188 |  | (297, 6) |  |
1094 | (547, 10) |  |  |  | 1189 |  |  |  |
1095 |  |  |  | 15 | 1191 |  |  | (397, 6) |
1096 | (548, 5) | (274, 9) |  |  | 1192 | (596, 3) | (298, 6) |  |
1097 |  |  |  |  | 1195 |  |  |  |
1104 |  | (276, 3) |  |  | 1196 |  | (299, 2) |  |
1105 |  |  |  | 13 | 1200 |  |  |  | 15
Table 3: Extensions ${\mathbb{F}}_{2^{n}}/{\mathbb{F}}_{2}$ without GNB of
type $\leq 10$ for $1000\leq n\leq 1200$.

##  6 Concluding remarks

It is clear that the strategies described in Section 4 and 5 do not work if
$n$ is a prime number $p$. Fortunately, we still have the possibility of using
efficient normal bases. Indeed, as shown by Theorem 3, a Gaussian normal basis
that can be adapted to NTT-like algorithms exists for the binary extension
${\mathbb{F}}_{2^{p}}/{\mathbb{F}}_{2}$. The only remaining question is how to
choose the type $k$ of this basis, which depends on the user’s needs. If any
GNB of type $k$ over ${\mathbb{F}}_{2^{p}}$ does not satisfy the user’s
expectations, another possibilty is to embed ${\mathbb{F}}_{2^{p}}$ itself
into a field ${\mathbb{F}}_{2^{ep}}$ using the following scheme:

${\mathbb{F}}_{2}$${\mathbb{F}}_{2^{p}}$${\mathbb{F}}_{2^{ep}}$.$p$$e$

Next, we check if ${\mathbb{F}}_{2^{ep}}$ over ${\mathbb{F}}_{2}$ admits a GNB
of type $k$ that satifies our requirements. A list of GNBs of lowest type
$(n,k)$ for $n\leq 2000$ is available in [15, 26]. In this case, since the
elements of ${\mathbb{F}}_{2^{p}}$ are interpreted as elements of
${\mathbb{F}}_{2^{2p}}$ we will lose (slightly) computational efficiency, and
it is better to choose $e=2$ or as small as possible.

## References

  * [1] D. W. Ash, I. F. Blake and S. A. Vanstone,  Low complexity normal bases,  Discrete Appl. Math., 25 (1989) 191-210.
  * [2] T. Beth, W. Geiselmann, and F. Meyer.:  Finding (good) normal bases in finite fields,  In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC ’91, 173-178, ACM, New York, NY, USA, 1991.
  * [3] The Magma algebra system,  Computational Algebra Group, University of Sydney,  http://magma.maths.usyd.edu.au/magma/.
  * [4] M. Christopoulou, T. Garefalakis, D. Panario, and D. Thomson.:  Gauss periods as constructions of low complexity normal bases,  Des. Codes Cryptogr. 62 (2012) 43-62.
  * [5] J.-M Couveignes and T. Ezome.:  The equivariant complexity of multiplication in finite field extensions  Journal of Algebra 622 (2023) 694-720.
  * [6] J.-M Couveignes and R. Lercier,  Elliptic periods for finite fields.  Finite Fields Appl., 15 (2009) 1-22.
  * [7] T. Ezome and M. Sall,  Normal bases from 1-dimensional algebraic groups.  J. Symb. Comput., 101 (2020) 152-169.
  * [8] T. Ezome and M. Sall,  On finite field arithmetic in characteristic 2.  Finite Fields Appl., 68 (2020) 101739.
  * [9] S. Gao.  Normal bases over finite fields,  ProQuest LLC, Ann Arbor, MI, 1993\.  Thesis (Ph.D), University of Waterloo (Canada).
  * [10] S. Gao, J. von zur Gathen, D. Panario:  Gauss periods: orders and cryptographical applications.  Math. Comput., 67, (1998) 343–352.
  * [11] S. Gao, J. von zur Gathen, D. Panario and V. Shoup,  Algorithms for exponentiation in finite fields,  J. Symb. Comput., (2000) 879-889
  * [12] J. von zur Gathen and J. Gerhard.:  Modern Computer Algebra.  Cambridge University Press, Cambridge (2003).  https://books.google.fr/books?id=NuEHj0wPwgIC
  * [13] J. von zur Gathen, A. Shokrollahi, and J. Shokrollahi.:  Efficient multiplication using type 2 optimal normal bases.  In Claude Carlet and Berk Sunar, editors, WAIFI, volume 4547 of Lecture Notes in Computer Science, pages 55-68. Springer, 2007.
  * [14] C. F. Gauss:  Disquisitiones Arithmeticae,  Braunschweig, 1801, republished, 1863, as vol. 1 of Werke; French transl., Recherches Arithmétiques, Paris, 1807, republished Hermann, Paris, 1910; German transl., Arithmetische Untersuchungen, Springer-Verlag, Berlin, 1889, republished Chelsea, New York, 1965; English transl., Yale, New Haven and London, 1966, 1986.
  * [15] Handbook of Finite Fields Website.  https://people.math.carleton.ca/~daniel/hff/,  Last accessed on January 31, 2024.
  * [16] D. Harvey and J. van der Hoeven  Polynomial multiplication over finite fields in time $O(n\log n)$ 2019\.
  * [17] A. Reyhani-Masoleh and M. A. Hasan.  A new construction of Massey-Omura parallel multiplier over ${\mathrm{GF}}(2^{m})$.  IEEE Trans. Comput, 51: 511-520, 2002.
  * [18] A. Reyhani-Masoleh and M. A. Hasan.  Efficient multiplication beyond optimal normal bases.  IEEE Trans. Comput, 52: 428-439, 2003.
  * [19] H. W. Lenstra and R. Schoof  Primitive normal bases for finite fields.  Math. Comp., 48 (1987) 217-231.
  * [20] J. L. Massey and J. K. Omura.:  Computational method and apparatus for finite field arithmetic,  U.S. patent #4,587,627, May 1986.
  * [21] J. Milne:  Elliptic Curves.  BookSurge Publishers 2006\.
  * [22] L. Moura, D. Panario, D. Thomson,  Normal Basis Exhaustive Search: 10 Years Later,  In: Budaghyan, L., Rodriguez-Henriquez, F. (eds) Arithmetic of Finite Fields. WAIFI 2018.  Lecture Notes in Computer Science., vol 11321, Springer, Cham (2018) 188-206.
  * [23] G. L. Mullen and D. Panario,  Handbook of Finite Fields,  CRC Press, Boca Raton, FL, (2013).
  * [24] R. C. Mullin, I. M. Onyszchuk, S. A. Vanstone and R. C. Wilson,  Optimal normal bases $GF(p^{n})$,  Discrete Appl. Math., 22 (1988/1989) 149-161.
  * [25] D. Panario, M. Sall, Q. Wang.: The complexity of elliptic normal bases,  preprint available, https://arxiv.org/abs/2401.11872v1.
  * [26] Normal Bases algorithms and tables for fast computation in high dimensions  https://github.com/sallme/FastComputationAlgorithms
  * [27] J.M. Pollard.  The Fast Fourier Transform in a finite field.  Mathematics of Computation 25(114), 365-374 (1971)
  * [28] A. Schonhage, V. Strassen: Schnelle multiplikation großer zahlen [fast multiplication of large numbers].  Computing 7 (3–4), 281–292 (1971).  https://doi.org/10.1007/BF02242355
  * [29] J. H. Silverman,  The arithmetic of elliptic curves,  volume 106 of Graduate Texts in Mathematics. Springer, Dordrecht, second edition, 2009.
  * [30] D. Thomson and C. Weir,  Artin-Schreier extensions of normal bases.  Finite Fields Appl. 53 (2018) 267-286.
  * [31] A. Wassermann,  Konstruktion von Normalbasen,  Bayreuther Mathematische Schriften., 31 (1990) 155-164.
  * [32] E. Witt,  Zyklische körper und algebren der charateristik $p$ vom grad $p^{n}$ structur diskret bewerteter perfekter körper mit vollkommenem restklassenkörper der characteristik $p^{n}$,  J. Reine Undwandte Math., 176 (1936) 126–140.


# Consistency of quantum computation and the equivalence principle

Marcin Nowakowski111Electronic address<EMAIL_ADDRESS>Faculty of
Applied Physics and Mathematics, Gdansk University of Technology, 80-952
Gdansk, Poland  National Quantum Information Center of Gdansk, Andersa 27,
81-824 Sopot, Poland

###### Abstract

The equivalence principle, being one of the building blocks of general
relativity, seems to be also crucial for analysis of quantum effects in
gravity. In this paper we consider the question if the equivalence principle
has to hold for consistency of performing quantum computation in gravitational
field. We propose an analysis with a looped evolution consisting of steps both
in the gravitational field and in the accelerated reference frame. We show
that without the equivalence principle the looped quantum evolution cannot be
unitary and looses its consistency. For this reasoning the equivalence
principle is formulated in terms of the gauge transformations and is analyzed
for particles acquiring an appropriate phases associated with the actions over
the looped path. In consequence, to keep consistency of quantum operations in
gravitational field, it is required to keep some quantum variant of the
equivalence principle. This proves importance of the quantized versions of
this fundamental gravitational principle for quantum information processing.

###### pacs:

03.67.-a, 03.67.Hk

The equivalence principle is one of the foundations of general relativity.
Although its roots are classical, the long-standing research is focused on
inclusion of this principle [1, 2, 3, 4, 6, 12, 7, 8] into the future
quantized version of gravity which is based on the assumption that it should
be also a foundation of quantum gravity. There has been also a long-standing
debate if gravity itself is quantum but recent research [4, 5] shed some light
on the quantumness of gravity proposing interferometric experiments testing
its quantum nature. In this context, it is an objective of this paper to
consider the issue of consistency of distributed quantum information
processing in background of weak gravitational fields which can be considered
quantum for this task [19].

Our proposal is based on the model of a looped system (Fig. 1) with quantum
evolution connecting two different regions of space-time from which one is in
gravitational field and the another one being a gravity-free region is only
accelerated. For this consideration we engage a standard understanding of the
equivalence principle assuming that the state of motion of a point particle at
rest in a local uniform gravitational field g is indistinguishable from the
state of motion of a point particle in an accelerated reference frame (with
$\textbf{a}=\textbf{-g}$) in a gravity-free region. Alternatively, it can be
formulated in terms of local reference frames stating that there is no way, by
experiments confined to infinitesimally small regions of space-time, to
distinguish one local Lorentz frame in one region of space-time from any other
local Lorentz frame in the same or any other region [18]. This formulation is
a basis for recent [7] quantum proposal of the equivalence principle with
quantum coordinate systems and is naturally connected with the problem of
defining a quantum reference frame [14, 10] and relativity of quantum
superpositions [9].

In the context of this paper, it is fundamental to note that gauge
transformations govern the way of transforming a system from a region with
gravitational field g to the accelerated reference frame with
$\textbf{a}=\textbf{-g}$. In quantum mechanics the Schrodinger equation is
invariant when both potentials and the wave-function are subject of these
transformations. For the vector potential gauge transformations are:

$A^{\prime}_{\mu}=A_{\mu}+\partial_{\mu}X$

Then the quantum state is transformed as:
$|\Psi^{\prime}\rangle=U|\Psi\rangle=e^{i\phi}|\Psi\rangle$ with the gauge
parameter $U$ being a phase factor which is actually an element of the unitary
group $U(1)$ for Maxwell theory. It is also worth mentioning that this element
is space-time dependant which is vital for further reasoning. For a series of
gauge transformations $U_{1}\rightarrow U_{2}\ldots\rightarrow U_{n}$ of the
state $|\Psi\rangle$ the composition law holds:

$|\Psi\rangle\rightarrow U_{1}|\Psi\rangle\rightarrow
U_{2}U_{1}|\Psi\rangle\rightarrow\ldots\rightarrow U_{n}\ldots
U_{2}U_{1}|\Psi\rangle$ (1)

For our example of the closed quantum-gravitational loop we get effectively a
version of the Wilson loop (being also gauge invariant) for the closed space-
time path. The gauge parameter for this case is periodic ($U(\lambda+2\pi)=U$
for some $\lambda$ parametrizing the path) on the loop which physically is in
line with the equivalence principle and with the conservation of energy as
presented in this paper.

For the linearized gravitational fields [18] the Riemann tensor is gauge
invariant with the same property inherited by the stress-energy tensor and
Einstein tensor. Thus, we can formally further consider quantum-gravitational
systems having this property. However, it is an open question if the following
reasoning is also fully applicable to gravity with non-linear gravitational
field equations.

We shall analyze now the model of the looped evolution and show that if the
quantum version of the equivalence principle, associating quantum phase with
each path in different background fields, does not hold, then the looped
evolution cannot be unitary. We consider further a closed loop (Fig. 1) with
part of the loop (space-time region A) being in the gravitational field $g$
and part in the accelerated system with $a=-g$ (space-time region B). We
follow the Feynman path methods assuming that each sub-path contributes to the
final probability amplitude of a quantum process adding actions for paths in
regions A and B. By the very property of associating a quantum phase with a
path traversed by a quantum system in gravitational field, we assume
quantumness of the interaction which is actually also a hidden assumption in
this type of analysis and we also assume consistency of the single path
traversing both regions.

Figure 1: A looped quantum-gravitational interferometer with space-time region
A in gravitational field g and space-time region B with acceleration a=-g. The
looped particle traverses the loop $abcda$.

The probability amplitude for the history branch of the 1-loop process is:

$\mathcal{A}_{1}=\langle\Psi_{1}|e^{\frac{i}{\hslash}S_{da}}e^{\frac{i}{\hslash}S_{cd}}e^{\frac{i}{\hslash}S_{bc}}e^{\frac{i}{\hslash}S_{ab}}|\Psi_{1}\rangle$
(2)

For simplification we can consider only two paths of this loop: $a\rightarrow
c$ (including $b$) and $c\rightarrow a$ (including $d$) putting the actions
$S_{ac}$ and $S_{cd}$. Thus, a quantum particle traversing this loop acquires
phase $e^{i\phi_{ac}}$ associated with existence of the gravitational field
$g$ on the sub-path $a\rightarrow b$ and $e^{i\phi_{ca}}$ with traversing the
accelerated (by $a$) sub-path $c\rightarrow d$. Following one gets:

$\mathcal{A}_{1}=\langle\Psi_{1}|e^{i\phi_{ca}}e^{i\phi_{ac}}|\Psi_{1}\rangle$
(3)

where $\phi_{ca}=S_{ca}/\hslash$ and $\phi_{ac}=S_{ac}/\hslash$ (we omit in
the calculation the acquired phases of paths $b\rightarrow c$ and
$d\rightarrow a$ which is dependant on a particular implementation of the
system).

Further for the n-loop process its probability amplitude is:

$\mathcal{A}_{n}=\langle\Psi_{1}|[e^{i\phi_{ca}}e^{i\phi_{ac}}]^{n}|\Psi_{1}\rangle$
(4)

which is in agreement with the composition law for the gauge transformations
$U=[U_{2}U_{1}]^{n}=[e^{i\phi_{ca}}e^{i\phi_{ac}}]^{n}$.

Even not assuming correctness of the gauge transformation on the closed loop
(closed history associated with the evolution of the particle), one would be
forced to introduce a relation between systems A and B (the relation actually
is created due to existence of the connection created by the history of a
particle traversing both ’regions’ A and B) which is related to changes in the
state of the system. As an implication of this reasoning the change of state
(associated with the acquired phase) within A has to be related to the change
on B, which is imposed by the consistency of the traversing particle’s
history. The binding evolution of the traversing particle is unitary which is
postulated by quantum mechanics and is a necessary condition of consistency of
quantum information processing. If that does not hold, then many paradoxes
would arise like those related to contradiction of the quantum no-cloning
principle.

There are two important principles necessary for ensuring unitarity of a
quantum evolution with gravitational field interaction for our model:

1\. Firstly, we assume that laws of physics apply in the same way to each
history branch which has its formulation in 1-loop, 2-loop up to n-loop
processes where we apply the superposition rule up to the n-loop processes
imposing its application to gravitational fields.

2\. Secondly, we assume correctness of the equivalance principle imposing a
direct relation between the gravitational field and the accelarated system.
This relation is being ensured by the binding history of the quantum particle
traversing the system A and then system B which also creates information
connection between the regions of space-time with different gravitational
characteristics [15].

It is now crucial to show that the processes are unitary up to the n-loop
processes in the infinite regime with convergence of the superposition series.
For the $0$-loop process where the particle is just reflected from the BS
(beam-splitter), one gets:

$|\Psi_{in}\rangle\rightarrow|\Psi_{out}\rangle=|\Psi_{in}\rangle$ (5)

For the 1-loop process, where a particle traverses the loop only once but
acquiring the phases due to gravitational interaction and existence of the
accelerated region $B$, one gets:

$|\Psi_{in}\rangle\rightarrow|\Psi_{out}\rangle=\alpha|\Psi_{0}\rangle+\beta
e^{i\phi_{ca}}e^{i\phi_{ac}}|\Psi_{1}\rangle$ (6)

where $|\Psi_{0}\rangle$ denotes the state associated with the outgoing path
from the interferometer, $|\Psi_{1}\rangle$ with the looped path and
$|\Psi_{out}\rangle$ denotes the total output state of the beam splitter (i.e.
superposition of two output ports). Replicating this procedure up to the
n-loop process we get a partial sum of the geometric series:

$\displaystyle|\Psi_{out}\rangle$ $\displaystyle=$
$\displaystyle\alpha(\frac{1-\beta^{2n}}{1-\beta^{2}U^{2}})^{\frac{1}{2}}|\Psi_{0}\rangle+\beta^{n}U^{n}|\Psi_{1}\rangle$

where $U=e^{i\phi_{ca}}e^{i\phi_{ac}}$ and $\beta^{2}=1-\alpha^{2}$ for
normalization in our model. Thus, within the n-looped process there is still
non-zero probability of finding a particle within the loop which is not the
case in the infinite regime, i.e. this looped interferometer is fully
reflective.

For the convergence of the series for $n\rightarrow+\infty$, it is required to
put unitarity of the loop. For the $\infty$-loop process, the series converges
to:

$|\Psi_{out}\rangle\rightarrow\frac{\alpha}{(1-\beta^{2}U^{2})^{\frac{1}{2}}}|\Psi_{0}\rangle$
(8)

and as expected, this system is reflective. Noticeably,
$\det(1-\beta^{2}U^{2})\neq 0$ which results from $|\beta|<1$ (iff $|\beta|=1$
then there is effectively no history branch with the particle outgoing the
loop) and unitarity of U (implying $|U|=1$). This condition leads to
convergence of the series. Conversely, if the loop was not unitary and the
equivalence principle did not hold, then the series would be divergent and
would lead to inconsistency of information processing. For general variants of
the unitary operations replacing the beam splitter and the loop, one can apply
the methods engaged in [16]. This analysis naturally resembles Feynman diagram
methods, however, in our case we consider a space-time loop-diagram.

For the mass particle traversing this looped interferometer we can modify the
model of the Colella-Overhauser-Werner (COW) experiment [20] superposing a
state of single neutron in two different positions (heights) of the Earth’s
gravitation field. Let us consider a particle of mass m at state
$|\Psi\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ with the branch
$|1\rangle$ getting into the loop of our interferometer. For calculation of
the action for the mass particle traversing the arm of an interferometer in
the gravitational field $g$, the Lagrangian is straightforward:

$L_{g}=\frac{1}{2}m(\dot{\lambda})^{2}-mg\lambda$ (9)

and for the arm accelerated with the acceleration rate $a$:

$L_{a}=\frac{1}{2}m(\dot{\lambda}+at)^{2}$ (10)

Assuming that acceleration of the region B happens with the same value $g$,
one gets the gauge parameter $G(x,t)=-mg\lambda t-\frac{1}{6}mg^{2}t^{3}$ and
the relation between Lagrangians:

$L_{g}=L_{a}+\partial_{t}G(\lambda,t)$ (11)

leading to the output state from the loop interferometer for
$n\rightarrow\infty$:

$|\Psi_{out}\rangle\rightarrow\frac{1}{(2-U^{2})^{\frac{1}{2}}}|0\rangle$ (12)

where the total $U=e^{i\phi_{a}}e^{i\phi_{g}}$,
$\phi_{g}=\frac{1}{\hslash}\int_{t_{1}}^{t_{2}}L_{g}dt$ and
$\phi_{a}=\frac{1}{\hslash}\int_{t_{3}}^{t_{4}}L_{a}dt$. It is also worth
mentioning that the gauge transformation introduces naturally a phase shift
$\Delta\phi$ [3] between the two regions A and B. If the proper time of
traversing the region A and B is the same, then the difference can be
formulated in terms of the gauge transformation, i.e.
$\Delta\phi=G(\lambda,t)/\hslash$.

If the equivalence principle did not hold for the quantum systems, then
firstly the looped evolution would be not unitary and secondly, we could
violate the conservation of energy for the looped system increasing energy ad
infinitum.

It is also interesting to analyze the role of the equivalence principle in
quantum algorithms where parts of the algorithms are processed in different
gravitational setups. As an example, we consider the Deutsch-Jozsa algorithm
represented in terms of the binary tree which has a direct representation by
means of Feynman paths. In the following scheme the equivalance principle can
play a destructive role in each iteration of the binary tree. If the overall
process is not corrected at each step of the algorithm, due to the phase shift
acquired by the accelerated branches of the tree, then the final outcome of
the algorithm is incorrect. The Deutsch-Jozsa algorithm is initiated with an
input register of $n=log_{2}N$ qubits (where N represents a binary tree level
in our scheme - Fig. 2) in a state $|\Phi_{in}\rangle=|00\ldots 0\rangle$.
Then each qubit is processed with a Hadamard operator leading to a
superposition of all states in the computational basis of
$\mathcal{H}=(\mathbb{C}^{2})^{\otimes n}$. In the binary tree approach the
whole input register state can be generated by $N$-level tree splitting the
state (e.g. by the bean-splitter in the interferomter) at each level of the
tree. The proposal of implementation of such an evolution with the ring cavity
is discussed in [21, 22] but it can be also implemented by nested
interferometers as aforementioned for the COW interferometer above.

Figure 2: Any binary balanced or constant function can be encoded as a binary
tree with the superposition state
$\frac{1}{\sqrt{2^{n}}}\sum_{x=x_{1},\ldots,x_{n}=0,1}(-1)^{f(x)}|x\rangle$ as
a sum over all paths up to the N-level nodes. The phase shifts are encoded in
the 1-branches. $U_{\Lambda}$ introduces additional gauge phase shift in the
process disturbing flow of the algorithm.

The process of creating n-qubit paths works as follows:

$\displaystyle|0\rangle$ $\displaystyle\rightarrow$
$\displaystyle\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\rightarrow\ldots\rightarrow$
$\displaystyle\rightarrow$
$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x=x_{1},\ldots,x_{n}=0,1}|x\rangle$

thus, we consider a N-level tree for creation of the $n=log_{2}N$ qubit state
(Fig. 2). There are two other fundamental steps in the Deutsch-Jozsa
algorithm. The oracle $U_{f}$ implements the function as constant or balanced
which is queried by the whole algorithm:

$U_{f}\frac{1}{\sqrt{2^{n}}}\sum_{x=x_{1},\ldots,x_{n}=0,1}|x\rangle=\frac{1}{\sqrt{2^{n}}}\sum_{x=x_{1},\ldots,x_{n}=0,1}(-1)^{f(x)}|x\rangle$
(14)

The second step includes again the Hadamard operation and measurement in the
computational basis. If the state $|00\ldots 0\rangle$ is achieved (with
probability $P(|00\ldots
0\rangle)=|\frac{1}{\sqrt{2^{n}}}\sum_{x=x_{1},\ldots,x_{n}=0,1}(-1)^{f(x)}|^{2}$),
then the function is constant. For the balanced function we get destructive
interference and the probability of getting $|00\ldots 0\rangle$ tends to
zero.

In our scheme we engage a binary tree that can encode effectively any binary
balanced function $f(\cdot)$ by introduction of the phased paths for the
$|1\rangle$-branches (the chosen branches should face a $\pi$-phase shift for
the oracle implementation). We can disturb the oracle implementation by
introduction of a gravitational phase shift if branches $0$ and $1$ are
localized in two different gravitational setups as discussed in this paper:

$\displaystyle U_{\Lambda}$
$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{x=x_{1},\ldots,x_{n}=0,1}(-1)^{f(x)}|x\rangle=$
$\displaystyle=$ $\displaystyle\pm\frac{1}{\sqrt{2^{n}}}(|0\rangle\pm
e^{i\phi_{g}}|1\rangle)(|0\rangle\pm
e^{i\phi_{g}}|1\rangle)\ldots(|0\rangle\pm e^{i\phi_{g}}|1\rangle)$

where the unitary operator $U_{\Lambda}$ introduces a $e^{i\phi_{g}}$ shift
(that can be the gauge phase shift due to the equivalence principle) to
$|1\rangle$ branches and can effectively change the final answer about the
nature of the function $f(\cdot)$. If one considers the scenario with regions
A in the gravitational field and B with the corresponding acceleration, then
only the difference in phases between the $|0\rangle$ and $|1\rangle$ branches
influences the final result of the algorithm - the global phase can be
omitted.

In summary, we showed that the quantum version of the equivalence principle
guarantees unitarity of quantum information processing in the weak
gravitational field and is necessary for keeping consistency of quantum
operations, especially if the processing algorithm is distributed spatially
across regions with different gravitational characteristics. It is an open
question how the presented analysis should be modified to be correct also for
strong gravitational fields.

It would be also interesting to perform an experiment with light signals
exchanged in a looped system between the system A being close to the Earth
surface and the system B being on a stationary orbit around Earth to check the
presented model.

## References

  * [1] Y. Aharonov, G. Carmi, Found. Phys. 3, 493 (1973).
  * [2] Y. Aharonov, G. Carmi, Found. Phys. 4, 75 (1974).
  * [3] C. Marletto et al., Entropy 22, 228 (2020).
  * [4] S. Bose, et al. Phys. Rev. Lett. 119, 240401 (2017).
  * [5] Y. Margalit et al., Realization of a complete Stern-Gerlach interferometer: Towards a test of quantum gravity, arXiv: 2011.10928, (2020).
  * [6] C. Marletto and V. Vedral, Phys. Rev. Lett. 119, 240402 (2017).
  * [7] L. Hardy, Implementation of the Quantum Equivalence Principle, arXiv:1903.01289, (2019).
  * [8] M. Zych, C. Brukner, Nat. Phys., 14, 1027-1031, (2018).
  * [9] M. Zych, F. Costa, T. C. Ralph, Relativity of quantum superpositions, arXiv: 1809.04999, (2018).
  * [10] Y. Aharonov, T. Kaufherr, Quantum frames of reference. Phys. Rev. D, 30, 368 (1984).
  * [11] G. Rosi et al., Nat. Commun. 8, 15529 (2017).
  * [12] C. Marletto and V Vedral, 3, 29, npj Quantum Information, 2017\.
  * [13] C. Marletto and V. Vedral, Phys. Rev. D 98, 046001 (2018).
  * [14] F. Giacomini, E. Castro-Ruiz, C. Brukner, Nature Commun., 10, 494 (2019).
  * [15] M. Nowakowski, In preparation.
  * [16] M. Czachor, Phys. Lett. A 383, 2704-2712 (2019).
  * [17] M. D. Schwartz, Quantum Field Theory and the Standard Model, Cambridge, 2013.
  * [18] C. W. Misner, K. S. Thorne, J. A. Wheeler, Gravitation, Princeton, 2017.
  * [19] R. P. Feynman, Rev. Mod. Phys. 20, 367 (1948).
  * [20] R. Collela, A. W. Overhauser, S. A. Werner, Phys. Rev. Lett. 34, 1472 (1975).
  * [21] B. Perez-Garcia et al., Phys. Lett. A, 379 1675 (2015).
  * [22] S. K. Goyal et al., Phys. Rev. A 92 040302 (2015).