Axel Hutt
email: ahutt@uottawa.ca

Local excitation-lateral inhibition interaction yields wave instabilities in spatial systems involving finite propagation delay

The work studies wave activity in spatial systems, which exhibit nonlocal spatial interactions at the presence of a finite propagation speed. We find analytically propagation delay-induced wave instabilities for various local excitatory and lateral inhibitory spatial interactions. The final numerical simulation confirms the analytical results.

Introduction

In the recent decades the space-time dynamics of extended complex systems has attracted much attention in physical, chemical and biological science [START_REF] Haken | Brain Dynamics[END_REF][START_REF] Nicolis | Self-Organization in Non-Equilibrium Systems: From Dissipative Structures to Order Through Fluctuations[END_REF]. In this context the nonlocal interactions between system subunits have been studied extensively [START_REF] Coombes | Waves and bumps in neural field theories[END_REF][START_REF] Cross | Pattern formation outside of equilibrium[END_REF][START_REF] Wilson | Excitatory and inhibitory interactions in localized populations of model neurons[END_REF]. By virtue of this nonlocal spatial interaction, the propagation delay between two spatial locations may not be negligible if the the propagation speed in the system is small enough. Such propagation delays have been found to affect the activity spread solids [START_REF] Tzou | Thermal lagging in random media[END_REF][START_REF] Mitra | Experimental evidence of hyperbolic heat conduction in processed meat[END_REF] and plasmas [START_REF] Lazzaro | Fast heat pulse propagation in hot plasmas[END_REF], they affect the stability of neuronal systems [START_REF] Hutt | Pattern formation in intracortical neuronal fields[END_REF] or may be responsible for subballistic transport in solids [START_REF] Metzler | Fractional diffusion, waiting-time distributions, and cattaneo-type equations[END_REF]. The present work addresses these phenomena and studies the effect of a finite propagation speed in a generic spatio-temporal model. To describe the space-time evolution of nonlocal systems mathematically, partial differential equations have been studied vastly, e.g. [START_REF] Haken | Synergetics: Introduction and Advanced topics[END_REF][START_REF] Nicolis | Self-Organization in Non-Equilibrium Systems: From Dissipative Structures to Order Through Fluctuations[END_REF]. Moreover integraldifferential equations also have been studied in recent years to describe nonlocal interaction in spatially extended neuronal systems [START_REF] Hutt | Effects of distributed transmission speeds on propagating activity in neural populations[END_REF][START_REF] Coombes | Waves and bumps in neural field theories[END_REF][START_REF] Blomquist | Localized activity patterns in two-population neuronal networks[END_REF][START_REF] Bressloff | Synaptically generated wave propagation in excitable neural media[END_REF][START_REF] Wilson | Excitatory and inhibitory interactions in localized populations of model neurons[END_REF]. Both latter equation types are strongly related for some specific integral-differential equations [START_REF] Murray | Mathematical Biology[END_REF][START_REF] Hutt | Analysis of nonlocal neural fields for both general and gamma-distributed connectivities[END_REF]. To illustrate this relation, assume a one-dimensional spatial field u(x) and the spatial kernel function K(x). Then it is with the Fourier transforms K and ũ of K and u, respectively. Then choosing 2 . This means that fast-decaying integral kernels K(x) with √ D ≪ 1 represents a local diffusion process with diffusion constant D, while slowly-decaying integral kernels yield higher orders of spatial derivatives and thus represent long-ranged or nonlocal interactions. This procedure has been studied in some more detail in a previous work [START_REF] Hutt | Analysis of nonlocal neural fields for both general and gamma-distributed connectivities[END_REF] and it turned out that integraldifferential equations generalize some types of partial differential equations. In this context the present work extends the previous work by the study of a more general spatio-temporal model. In the research field of spatially extended systems, let the underlying model be partial differential equations or integral-differential equations, it is well-known that local excitation and lateral inhibition (local inhibition and lateral excitation) may yield stationary (non-stationary) spatial patterns in one or more spatial dimensions [START_REF] Cross | Pattern formation outside of equilibrium[END_REF][START_REF] Hutt | Pattern formation in intracortical neuronal fields[END_REF]. However, a recent study showed that local inhibition and lateral excitation may yield stationary instabilities as well for gammastributed spatial interactions [START_REF] Hutt | Analysis of nonlocal neural fields for both general and gamma-distributed connectivities[END_REF]. This finding let us look more carefully on the nature of spatial interactions and the classification criteria for these instabilities. The present work investigates wether there are traveling waves in local excitatory and lateral inhibitory systems, which may contrast to the findings in previous studies. The work is structured as follows. The subsequent section introduces and motivates the generic model studied and presents the steps of corresponding linear stability analysis about a stationar state. Then section 3 applies the model to a field of harmonically damped oscillators, which are coupled by nonlocal excitation and inhibition. The analytically results are confirmed by numerical simulations. The subsequent summary closes the work.

K(x) = exp(-|x|/ √ D)/2 √ D, it is K(k) = 1/(1 + Dk 2 ) = 1 -Dk 2 + D 2 k 4 + • • • and Eq. (1) reads ∞ -∞ K(x -y)u(y)dy ≈ u(x, t) + D∆u(x, t) +D 2 ∆ 2 u(x, t) + • • • with ∆ = ∂ 2 /∂x

The generic model

The model studied presumes identical elements which obey the (non-)linear differential equation

Tt V (x, t) = h[V (x, t)] .
Here V (x, t) represents the scalar activity variable, Tt = Tt (∂/∂t) denotes the temporal operator and the functional h[V (x, t)] defines the local dynamics at spatial location x. Let the elements {x} be located in a spatial domain and coupled to each other. This configuration reflects a topological network with identical elements in which no spatial metric is considered, or a topological network embedded in a physical space [START_REF] Xulvi-Brunet | Evolving networks with disadvantaged long-range connections[END_REF][START_REF] Jost | Evolving networks with distance preferences[END_REF]. In the the present model the single elements are connected according to a probability density function similar to topological networks but their connectivity function depend on the Euclidean distance between the elements similar to spatial networks. Further the spatial coupling is presumed homogeneous in space, that is the coupling is dependent on the spatial distance between the elements. These properties describe a scale-free lattice [START_REF] Yang | Lattice scale-free networks with weighted linking[END_REF][START_REF] Karmakar | Sandpile model on an optimized scale-free network on euclidean space[END_REF]. Moreover, the presented model presumes infinitely dense elements, that is we consider a continuous field. This contrasts to networks whose major element is the discreteness. However in biological systems, e.g. in the brain, the single cells are dense and the continuum limit holds [START_REF] Van Hemmen | Continuum limit of discrete neuronal structures: is cortical tissue an 'excitable' medium?[END_REF]. Furthermore the speed by which the activity is transmitted between single elements shall be finite. This finite propagation speed also contrasts to most spatial networks, which frequently neglect propagation delay effects.

Considering all previous aspects, the element at spatial location x obeys the integral-differential equation

Tt V (x, t) = h[V (x, t)] + I(x, t) + Ω K(x -y)f V (y, t - |x -y| v K ) +L(x -y)g V (y, t - |x -y| v L ) dy.
Here I(x, t) represents the external input and the kernel functions K, L represent the probability density functions of spatial connections in two networks, and thus K(x) and L(x) are normalized to unity in the spatial domain Ω.

In the following we assume Ω = R. The functionals f [V ] and g[V ] represent the (non-)linear coupling functions. Further the model considers propagation delays between spatial locations x and y at distance |x -y| due to the finite transmission speed v K and v L corresponding to the two networks. This model allows the study of a wide range of combined spatial interaction. For instance spatial systems involving both mean-field and local interactions may be modeled by K(x) = const and L(x) = δ(x), respectively. The subsequent paragraphs focus on the combination of excitatory and inhibitory interactions with kernel functions K(x) and L(x), respectively. In addition we specify

f [V ] = a K S[V ], g[V ] = a L S[V ]
with the nonlinear functional S[V ] and the total amount of excitation and inhibition a K and a L , respectively. Further we presume a K > a L . For h(V ) = 0, Eq. ( 1) represents a well-studied nonlocal model of neural populations [START_REF] Pinto | Spatially structured activity in synaptically coupled neuronal networks: I. travelling fronts and pulses[END_REF][START_REF] Coombes | Waves and bumps in neural field theories[END_REF][START_REF] Hutt | Pattern formation in intracortical neuronal fields[END_REF][START_REF] Hutt | Analysis of nonlocal neural fields for both general and gamma-distributed connectivities[END_REF][START_REF] Hutt | Effects of nonlocal feedback on traveling fronts in neural fields subject to transmission delay[END_REF]. First let us determine the stationary state which is constant in space and time. Applying a constant external input I 0 , we find the implicit equation 0 = h(V 0 ) + f (V 0 ) + g(V 0 ) + I 0 . Here we used the fact that the kernel functions are normalized to unity. Then small deviations u(x, t) about the stationary state obey a linear evolution equation and relax in time to the stationary state V 0 with u(x, t) ∼ e λt , λ ∈ C if Re(λ) < 0. Then the subsequent expansion of u(x, t) in the continuous Fourier basis {e ikz } yields the implicit condition

T (λ) = h 0 + S ′ Ω dy × a K K(y)e -λ|y|/vK -a L L(y)e -λ|y|/vL e iky (1)
with h 0 = ∂h/∂V , S ′ = ∂S/∂V computed at V = V 0 . Since the external input drives the system, its stability is subjected to I 0 and subsequently S ′ represents the reasonable control parameter. Equation ( 1) is difficult to solve exactly for λ. In a previous study a more specific model has been studied in detail for stationary and non-stationary instabilities [START_REF] Hutt | Analysis of nonlocal neural fields for both general and gamma-distributed connectivities[END_REF]. We follow its approach and consider large but finite propagation speeds. Then it is exp

(-λ|z|/v) ≈ 1 -(λ/v)|z| for |λ|/v K , |λ L |/v L ≪ 1 and (1) reads T (λ) ≈ h 0 + S ′ K0 (k) -λS ′ K1 (k) . (2)
with

K0 (k) = a K K(0) (k) -a L L(0) (k) K1 (k) = a K v K K(1) (k) - a L v L L(1) (k) with F (n) (k) = ∞ -∞ F (z)|z| n exp(-ikz)dz.
The term K0 (k) and K1 (k) represents the Fourier transform and the first kernel Fourier moment of a K K(x) + a L L(x), respectively. Essentially let us specify the temporal evolution of a single element to a damped oscillator with

Tt = ∂ 2 ∂t 2 + γ ∂ ∂t + 1.
Then the stability threshold of stationary and non-stationary instabilities read

1 S ′ c = K0 (k c ) 1 -h 0 (stationary instability) (3) 1 S ′ c = - K1 (k) γ (non-stationary instability) (4)
Hence the global maximum of K0 (k c ) and -K1 (k c ) define the critical wavenumber k c and the critical threshold S ′ c of stationary and non-stationary instabilities, respectively. Figure 1 illustrates this result for non-stationary instabilities. In the following, we call an emerging non-stationary phenomena a wave instability, if k c = 0. and the instability with k c = 0 is called a global oscillation. Moreover it is interesting to note that the threshold of the non-stationary instability does not depend on the local (non-)linear dynamics of the elements h(V ). 4) (solid line) and its left hand side (dotdashed line). If the stability threshold is not reached, i.e. S ′ = s < < S ′ c , the system is stable. In contrast, if S ′ = s c = S ′ c (S ′ = s > > S ′ c ) the system is marginal stable (unstable).

Application to specific model

First let us discuss briefly various types of nonlocal interactions. We choose the excitatory and inhibitory spatial kernel to the gamma function and the decreasing exponential function, resp., with

K(z) = 1 2q p Γ(p) |z| p-1 e -|z|/q , L(z) = 1 2r e -|z|/r (5)
Since the Eq. ( 4) does not depend on h[V ], we set h[V ] = 0. In other words, the single elements in the field are assumed damped harmonic oscillators, which are coupled by an excitatory and an inhibitory network. The parameter r defines the spatial range of the inhibitory interaction, while both p and q represent the spatial constants of the excitatory nonlocal interaction. The scase p = 1 is wellstudied, see e.g. [START_REF] Hutt | Pattern formation in intracortical neuronal fields[END_REF], and the combination of q and r yield the four important cases, namely the global excitation, the global inhibition, the local excitationlateral inhibition and the local inhibition-lateral excitation. Further the choice p > 1 yields local inhibitory interactions or local inhibitory-lateral excitatory interactions [START_REF] Hutt | Analysis of nonlocal neural fields for both general and gamma-distributed connectivities[END_REF]. The present work focus on the case p < 1 which yields the local excitation or the local excitation-lateral inhibition. Please see Fig. 2 for the corresponding illustration of the cases p < 1 and p > 1. In order to gain the critical wavenumber of the wave instability, the kernel Fourier moment in Eq. ( 4) is computed to

K(1) (k) = pq cos((p + 1) arctan(kq)) (1 + q 2 k 2 ) (p+1)/2 (6) L(1) (k) = r cos(2 arctan(kr)) (1 + r 2 k 2 ) (7) p<1 p>1 (a) (b) (c) (d) M(x) x x x x M(x) M(x) M(x)
Figure 2: Illustration for some spatial interaction types for different parameters p, q and r. Panel (a) shows the kernel function for p < 1, q > r that yields global excitations while panel (b) reveals local excitation-lateral inhibition for p < 1, q < r. In panel (c) the kernel function has been illustrated for p > 1, q < r, which represents global inhibition, while panel (d) shows local inhibition-lateral excitation for p > 1, q > r.

It is M (x) = K(x) -L(x) Since K1 (k) → 0 for |k| → ∞, there is a maximum of -K1 (k) at some |k| = |k c | with -K1 (k c ) > 0 if -K1 (0) > 0 and -d 2 K1 (0)/dk 2 > 0. These sufficient conditions read ξ > p/a r , ξ 3 < v r 6a r p(p + 1)(p + 2) ( 8
)
with the new parameters ξ = r/q, v r = v L /v K and a r = a L /a K < 1. Figure 3 illustrates the different parameter regimes of the conditions. At first it turns out that there is large parameter regime which allows for non-stationary instabilities. In order to gain further insight to the nature of spatial interactions for p < 1, Fig. 4 shows the parameter regimes and the different number of roots of the kernel function K(z). We find a parameter regime of single roots, which reflects local excitation-lateral inhibition interaction, and a parameter regime of no roots, i.e. global excitation. Moreover, there is a parameter regime of multiple roots which, for instance, reflects local excitation -mid-range inhibitionlateral excitation and allows for wave instabilities.

To illustrate the relation of the spatial interaction type and the resulting non-stationary instability, Figure 5 plots the kernel functions K(z) and the corresponding negative first kernel Fourier moments -K1 (k) for four different cases of spatial interactions. These specific cases are denoted by filled dots in Fig. 4. We find local excitation-lateral inhibition for ξ = 0.8 (top row, left panel in Fig. 4). Since the global maximum of -K1 (k) gives the critical wavenumber k c , this case yields global oscillations with k c = 0 (top row, right panel in Fig. 4). For ξ = 0.75, now the kernel function exhibits two roots which 0,2 0,4 0,6 0,8 1 p 1 ξ=r/q g lo b a l o s c il la t io n is p o s s ib le w a v e i n s t a b i l i t y i s p o s s i b l e w a v e i n s t a b i l i t y Figure 3: The occurrence of oscillatory instabilities subject to the parameters ξ = r/q and p. The dashed and thin solid line represent the function ξ = (v r p(p + 1)(p + 2)/6a r ) 1/3 and ξ = p/a r , respectively, taken from Eq. ( 8). Here it is v r = 1, a r = 0.8 . still leads to global oscillations. In case of ξ = 0.70 the sufficient condition for wave instabilities are fulfilled, as -K1 (k) reveals a critical wavenumber k c = 0, see Fig. 4. Moreover, the spatial interaction function reveals local excitation, mid-range inhibition and lateral excitation, which has not been found yet in previous studies. At last for ξ = 0.55 there is also a wave instability showing local excitation, mid-range inhibition and lateral excitation. In addition to this study, Fig. 6 compares the spatial interaction function, the Fourier transform K0 and -K1 (k) for two values of ξ. This comparison is necessary as the stationary instability may occur first before the wave instability while increasing the control parameter from small values. For both parameter values of ξ the global maximum of -K1 (k) exceeds the global maximum of K0 and thus a wave instability and not a stationary instability may occur. Thus Fig. 6 supports the previous findings.

To visualize and confirm the analytical findings, finally we integrate the integral-differential equation (1) numerically. The Euler integration scheme is applied for the time evolution integration and the Monte-Carlo method VE-GAS [START_REF] Lepage | A new algorithm for adaptive multidimensional integration[END_REF][START_REF] Gough | GNU Scientific Library Reference Manual[END_REF] computed the spatial integration. This specific Monte-Carlo integration method combines stratified and importance sampling, which is important to gain good estimates of the divergent excitatory kernel function. Moreover boundary conditions are set periodic with the period L while the initial conditions have to be defined in the time interval t 0 ∈ [-L/v; 0]. We have chosen V (z, t 0 ) = cos(k c x) + 0.5 * cos(5k c x). Figure 7 shows the wave instability for p = 0.5, ξ = 0.7 discussed above, cf. Fig. 4, and confirms the analytical finding.

Summary

The present work describes the nonlocal spatial interaction of single elements in a continuous field. The application to damped oscillators, which are coupled by both nonlocal excitation and inhibition, reveals a new mechanism of wave instabilities. In contrast to previous findings in pattern forming systems, we find wave instabilities for local excitation and lateral inhibition. To obtain more information on the corresponding spatial interaction, we investigated additionally the spatial interaction function. It turns out that various spatial interaction types exhibit wave instabilities, as local excitation-lateral inhibition and local excitation-midrange inhibition-lateral excitation. Hence the sign of the spatial interaction function does not carry the full information of the expected instability patterns in spatial systems with finite propagation delay. We have observed that the comparison of the global maximum of the Fourier component and global maximum of the negative first kernel Fourier moment allows for a reliable estimation of the instability type. Future work shall study the classifiers in vectorial models, as the nonlocal version of the Bruesselator, and the classification scheme in two-and three-dimensional systems.

Figure 1 :

 1 Figure 1: Sketch to illustrate the mechanism of non-stationary instabilities. The plot shows the right hand side of Eq. (4) (solid line) and its left hand side (dotdashed line). If the stability threshold is not reached, i.e. S ′ = s < < S ′ c , the system is stable. In contrast, if S ′ = s c = S ′ c (S ′ = s > > S ′ c ) the system is marginal stable (unstable).

  t a b i l i t y

Figure 4 :Figure 5 :

 45 Figure 4: Number of zero-croosings, i.e. roots, of the kernel function K(z) and the corresponding nature of spatial interactions subject to the parameters ξ and p. The dashed and thin solid line are taken from Fig.3. The red lines delimits the novel parameter regime of multiple roots. In addition to the parameters from Fig.3, it is a K = 10, a L = 8, v K = v L = 1 and q = 1.

Figure 6 :Figure 7 :

 67 Figure 6: The comparison of the kernel functions a K K(z) + a L L(z) (left coloumn), the Fourier transform K0 (k) (dashed line in right coloumn) and -K1 (k) (solid line in right coloumn) for two values of ξ. Additional parameters are taken from Fig. 4.

Appendix: The kernel Fourier moments

The n-th kernel Fourier moment of the specific kernels (5) can be computed from

cos (p arctan(kq))

Then we find for the excitatory kernel

In addition, we find

Since the inhibitory kernel is a specific case of the excitatory kernel with p = 1 and q = r, we obtain Eqs. ( 6), [START_REF] Haken | Brain Dynamics[END_REF] from the previous expressions.


Axel Hutt

Andre Longtin

Lutz Schimansky-Geier

Additive Global Noise Delays Turing Bifurcations

Keywords: numbers: 05.40.ÿa, 02.30.Jr, 47.20.Ky PRL 98, 230601

We apply a stochastic center manifold method to the calculation of noise-induced phase transitions in the stochastic Swift-Hohenberg equation. This analysis is applied to the reduced mode equations that result from Fourier decomposition of the field variable and of the temporal noise. The method shows a pitchfork bifurcation at lower perturbation order, but reveals a novel additive-noise-induced postponement of the Turing bifurcation at higher order. Good agreement is found between the theory and the numerics for both the reduced and the full system. The results are generalizable to a broad class of nonlinear spatial systems.

The patterns exhibited by real-world dynamical systems are an ongoing subject of intense study, especially because of their relevance in a multitude of experimental contexts. Additive noise [1], and especially multiplicative or ''statedependent'' noise [START_REF] Horsthemke | Noise-Induced Transitions[END_REF], can alter the bifurcations of simple dynamical systems framed in terms of stochastic differential equations. The analysis of the influence of noise on nonlinear spatially extended systems is a more serious challenge. This problem has received some attention at the theoretical level [START_REF] Garca-Ojalvo | Noise in Spatially Extended Systems[END_REF][START_REF] Lindner | [END_REF] and at the experimental level, e.g., in hydrodynamic systems [5], laser systems [6], in nematic liquid crystals [7], or in neural systems [8]. Since the key point of interest is the effect of noise on nonequilibrium phase transitions, an approach that tracks the behavior of the most unstable mode in terms of the more stable modes and the noise is warranted, a so-called center manifold approach, or relatedly, a slaving approach. A first useful method is to investigate the effect of noise on the bifurcating mode in a heuristic manner [1,9]. More rigorous methods have been developed for specific models [START_REF] Risken | The Fokker-Planck Equation-Methods of Solution and Applications[END_REF]. The stochastic center manifold approach (SCM) [START_REF] Boxler | [END_REF] directly calculates the center manifold in the presence of noise. Here we show that this approach enables the calculation of changes of stability in Turing patterns near their onset. Our work further reveals that additive global noise, which is white in time, has a stabilizing effect on the homogeneous state; i.e., it postpones the onset of the Turing pattern. Such effects have been reported for multiplicative global noise [7], while for additive spatiotemporal white noise, previous studies revealed no such postponement [START_REF] Horsthemke | Noise-Induced Transitions[END_REF]. Our results underscore the importance of extending the center manifold calculations to sufficiently high order for this substantial effect to be seen.

Our method first expands the stochastic partial differential equation (SPDE) of interest into coupled stochastic mode equations, and subsequently applies the SCM analysis. This yields a reduced set of equations involving col-ored noise, and this system is reduced to an order parameter equation by an adiabatic elimination. We then confirm the analytical results by numerical simulations of both the reduced mode equations and the original full SPDE.

We examine the stochastic Swift-Hohenberg equation [12]

@ x; t @t " x; t ÿ 3 x; t ÿ 1 @ 2 @x 2 2 x; t D 0 p t; (1)
with periodic boundary conditions, where is the real field amplitude, and the random Gaussian fluctuations t (a) The spatiotemporal activity subtracted by its spatial average is shown without (D 0 0, left) and with additive noise (D 0 6:25 10 ÿ4 , right). (b) shows the stationary probability density Pu c of the Fourier amplitudes u c at wave number k 1 computed in the time interval t 2 13 500; 13 600 for both noise variances. A stochastic Runge-Kutta algorithm of second order was used for the time integration with a time step dt 0:005 over a spatial grid of 400 elements, " 0:001.

obey hti 0, hti 2t ÿ ; i.e., t are uncorrelated in time and constant in space. In the following we refer to t as global fluctuations. Figure 1(a) shows the spatiotemporal dynamics of (1) and we observe a spatially periodic pattern with wave number k 1 for the deterministic case D 0 0 for large times. In contrast, the additive global fluctuations with D 0 Þ 0 stabilize the homogeneous state; i.e., no prominent pattern is observed. Moreover, the probability density of the spatial Fourier amplitude u c uk 1 has been computed from the simulated data over a large time interval in the stationary regime [Fig. 1(b)]. We recognize a narrow distribution at the Fourier amplitude value u c 0:032 and the amplitude value u c 0 for D 0 0 and D 0 6:25 10 ÿ4 , respectively. The rest of this Letter is devoted to an analytic derivation of this dramatic effect. We introduce the discrete spatial Fourier transform u n with

x; t P 1 nÿ1 u n te ik n x = jj p at discrete values k n n2=jj, where denotes the spatial domain. Inserting the Fourier expansion yields the infinite number of stochastic differential equations

du n t n u n t ÿ X l;m u l tu m tu nÿlÿm t dt n;0 D p dWt; (2)
where

D D 0 jj, n " ÿ 1 2k 2 n ÿ k 4 n , 1=jj
, and dWt is the differential Wiener process corresponding to the global fluctuations t. We find n ÿn 2 R, and since x; t ÿx; t it is u n u ÿn 2 R. In the following, the stochastic differential equations are interpreted in the Stratonovich sense.

Near the deterministic stability threshold, there is a linear coefficient c " 0 for the wave number k c 1. This means that the time scale 1= c of the corresponding amplitude u c t is very large compared to that of the other amplitudes. In the present work, we assume a single amplitude u c t and thus a single value c may become positive at a time. Further we will call k c and the corresponding amplitude u c the critical wave number and the critical amplitude or order parameter, respectively. By virtue of the time scale separation between amplitudes, the SCM theorem [START_REF] Boxler | [END_REF]13] allows for the reduction of the number of amplitude Eqs. [START_REF] Horsthemke | Noise-Induced Transitions[END_REF]. This theorem states that, near the stability threshold, all stable amplitudes u nÞc depend on the critical amplitude and the random fluctuations, i.e., u nÞc t u nÞc u c t; t. In more physical terms, the amplitude u c t enslaves the other amplitudes [START_REF] Haken | Synergetics[END_REF]. Moreover, assuming the parameters c and D p are on the order of the control parameter " with " 1, while the other parameters nÞc O1 are large, previous examinations of the deterministic Swift-Hohenberg equation at the lowest order in " [START_REF] Haken | Synergetics[END_REF] have shown the scaling of the amplitudes u c O" 1=2 , u 0 , u 2c , u 3c ; . . . O", and u j O" 3=2 for all j Þ 0, 2c, 3c, . . . . Here u 2c , u 3c , . . . denote the amplitudes with wave numbers k 2k c , 3k c , . . . . The SCM approach allows for the derivation of an evolution equation of the order parameter at specific orders of ". It is important to note that the treatment of high orders O" n leads to a better approximation of the dynamics. Consequently, our analysis starts at low orders of ", and improves by increasing the order in subsequent steps. Since the time scale of the constant mode 1=j 0 j is much larger than that of the amplitudes u 2c , u 3c , . . . and the latter relax much faster than u 0 t and u c t. Thus all amplitudes besides u 0 t and u c t are neglected in the subsequent analytical study.

At the low order O" 3=2 , the application of the SCM approach yields:

u 0 t D p Z 0 t; Z 0 t Z t ÿ1 e 0 tÿ dW 0 : (3)
We observe that u 0 t obeys a noise process Z 0 t with correlation time 1= 0 , i.e., Z 0 t is an Ornstein-Uhlenbeck process. Inserting Eq. ( 3) into Eq. ( 2), we obtain du c c u c ÿ 2u 3 c dt. This amplitude equation is independent of the colored noise and shows accordance to the wellknown deterministic result [12]: if c < 0, the system is stable and the stationary amplitude of the critical mode vanishes with u stat 0, i.e., no spatial pattern occurs. In contrast, c > 0 yields u 2 stat c =2 > 0 and the spatial pattern occurs; cf. Fig. 1(a). Thus the additive global fluctuations do not affect the stability of the amplitude u c t at low order O" 3=2 . Now let us examine the next higher nonlinear orders. At O" 2 , the SCM approach yields the same amplitude equations as for O" 3=2 . However, important modifications occur at O" 5=2 . It turns out that the stochastic center manifold u 0 remains the same as in the lower orders, while the critical amplitude becomes

du c c u c ÿ 3DZ 2 0 tu c ÿ 2u 3 c dt; (4)
dZ 0 0 Z 0 dt dW 0 t: (5)
In contrast to the lower orders, now the critical amplitude depends on the colored noise process and explicitly on the noise variance D. In other words, we observe a noisedependent effect of the additive global fluctuations on the critical amplitude.

To arrive at a final order parameter equation, the system (4) and ( 5) must be reduced to a single order parameter equation. However, the further additional application of the SCM approach does not allow for the further reduction of the equations, as Z 0 does not depend on u c and the system obtained consequently represents an irreducible form with respect to the Fourier amplitudes [13]. Subsequently, we choose a complementary approach to obtain this single equation, which does not apply directly to the Fourier amplitudes. In a recent study [START_REF] Drolet | [END_REF], Drolet and Vinal pro-with th 3D=j 0 j > 0. At first, we observe that the amplitude u c t is deterministic and approaches the stationary state u stat for large times. In the case c ÿ th < 0, the system is stable and u stat 0, while c ÿ th > 0 yields the stationary states u stat c ÿ th =2. Moreover, the stability threshold is shifted by th to larger values. Since this shift depends on the noise variance D, we conclude that the additive global fluctuations yield noiseinduced phase transitions and stabilize the homogeneous state of the system. This analytical finding confirms qualitatively the numerical finding in Fig. 1.

In the following we aim to confirm the latter analytical results by numerical simulations. In a first step, the stochastic evolution equations of the amplitudes u 0 t and u c t taken from Eq. ( 2) are integrated over several realizations to compute the stationary probability density P s u c . Figure 2 presents P s u c below and beyond the deterministic threshold for various values of D. We observe P s u c u c below the deterministic threshold for all noise variances [Fig. 2(a)]; i.e., the system is stable. In contrast, beyond the deterministic threshold, the stationary probability density P s u c changes in proportion to D [see Fig. 2(b)]. Specifically, the stationary amplitude shows values u c u stat Þ 0 for D 1 0 and the stationary probability density reads P s u c u c ÿ u stat u c u stat =2. This means the system exhibits a spatial pattern with wave number k c and amplitude u stat . This case represents the well-known Turing phase transition. Now, increasing D, the stationary amplitude u stat decreases and vanishes for D D 4 . In other words, the global fluctuations stabilize the system for large noise variances, which shows accordance with the previous analytical results and the numerical findings in Fig. 1. Moreover, the numerical results in Fig. 2 show very good agreement with the analytical results, which highlights the power of the analytical technique.

Further, Fig. 3 shows the stability diagram of u stat with respect to the control parameter c " for two noise variances. The absence of random fluctuations, i.e., D 0, yielded the well-known pitchfork bifurcation (left panel in Fig. 3). In contrast, additive global fluctuations shift the bifurcation point to larger values, i.e., it delays the bifurcation, and thus stabilize the system as shown in Fig. 3 for D 0:16. This stability can be observed in Fig. 2 of the Rayleigh-Be ´nard convection revealed thermal fluctuations at the instability onset, which are uncorrelated in space and time [16]. Since the Swift-Hohenberg equation allows for the modeling of the convective instability near the onset [12], we add the thermal noise x; t to Eq. (1):

@ x; t @t x; t ÿ 3 x; t ÿ 1 @ 2 @x 2 2 x; t D 0 p t D th p x; t:
The global fluctuations t are taken from Eq. ( 1), and the added thermal fluctuations x; t with variance D th obey a Gaussian distribution and are uncorrelated in space and time with hx; ti 0; hx; ty; i 2x ÿ yt ÿ . In addition, the global and thermal fluctuations are independent of each other in space and time.

FIG. 1 .

 1 FIG.1. Effects of global fluctuations on the system Eq. (1). (a) The spatiotemporal activity subtracted by its spatial average is shown without (D 0 0, left) and with additive noise (D 0 6:25 10 ÿ4 , right). (b) shows the stationary probability density Pu c of the Fourier amplitudes u c at wave number k 1 computed in the time interval t 2 13 500; 13 600 for both noise variances. A stochastic Runge-Kutta algorithm of second order was used for the time integration with a time step dt 0:005 over a spatial grid of 400 elements, " 0:001.

4 FIG. 2 .

 42 FIG.2. The stationary probability density P s u c computed numerically for various values of " and D and their comparison to analytical results. (a) " ÿ0:001, and the system is stable for all D. (b) " 0:001 and the system exhibits a single mode with c > 0. The different probability density functions are computed for D 1 0, D 2 0:01, D 3 0:04, and D 4 0:16 and the dotted lines represent the analytical results u stat c ÿ th =2. We applied the stochastic Euler forward algorithm with dt 0:01 for the amplitudes u c t and u 0 and computed P s u c by an ensemble average over 1000 paths after 6 10 5 time steps.

FIG. 4 .

 4 FIG. 4. Effects of global fluctuations in the presence of thermal noise. In (a), the spatiotemporal activity subtracted by its spatial average at each time is shown for thermal noise alone (left panel, D th 2:5 10 ÿ5 , D 0 0) and for the sum of thermal and strong global fluctuations (right panel, D th 2:5 10 ÿ5 , D 0 0:25). (b) shows the stationary probability density Pu c of the critical Fourier amplitudes u c computed in the time interval t 2 35 000; 35 100 for both noise variances. The same numerical methods and parameters as in Fig. 1 were used.

FIG. 3 .

 3 FIG. 3. Bifurcation diagram of the stationary amplitude u c u stat subjected to the control parameter c " for two noise variances D. The vertical arrows denote the values of c " examined in Fig. 2.

posed an adiabatic elimination approach for Fokker-Planck equations, which allows for dimensionality reduction near the stability threshold. After introducing the scaleindependent variables u c u c =" 1=2 , D D=" 2 , c c =" with Z 0 , 0 , O1, the Fokker-Planck equation (FP) associated with Eqs. ( 4) and ( 5) can be formulated for the time-dependent joint probability density P u c ; Z 0 ; t. Then the integration over Z 0 of the Fokker-Planck equation (assuming natural boundary conditions) yields the evolution equation of the probability density P u c ; t:

We observe that P u c ; t evolves on two slow time scales of order O" and O" 2 . Further, the integration of the FP for P u c ; Z 0 ; t over u c yields the evolution equation of the probability density PZ 0 ; t. It turns out that PZ 0 ; t evolves on the fast time scale O1. Consequently, the probability densities of the amplitudes u c and Z 0 evolve on different time scales, and thus reflect the time scale separation of the amplitudes. The adiabatic elimination procedure assumes that the conditional probability density PZ 0 j u c ; t P u c ; Z 0 ; t=P u c ; t evolves on the time scale O1 by virtue of this time scale separation and thus assumes @P u c ; t=@t 0. In other words, the processes on the fast time scale of order O1 experience an almost stationary probability density P u c ; t. One then finds the FP for PZ 0 j u c ; t, which evolves at time scale O1 with the stationary solution P s Z 0 j u c N 0; 1=j 0 j and we may write P u c ; Z 0 ; t P s Z 0 j u c P u c ; t. Inserting this result into Eq. ( 7) yields hZ 2 0 j u c i 1=j 0 jP u c ; t and the final Fokker-Planck equation of the order parameter (6) reads @Pu c ; t @t ÿ @ @u c c ÿ th u c ÿ 2u 3 c Pu c ; t; (8)


Razvan Barbulescu
email: razvan.barbulescu@u-bordeaux.fr

Adrien Poulalion
email: adrien.poulalion@mines.org

The special case of cyclotomic fields in quantum algorithms for unit groups

Unit group computations are a cryptographic primitive for which one has a fast quantum algorithm, but the required number of qubits is Õ(m 5 ). In this work we propose a modification of the algorithm for which the number of qubits is Õ(m 2 ) in the case of cyclotomic fields. Moreover, under a recent conjecture on the size of the class group of

, the quantum algorithms is much simpler because it is a hidden subgroup problem (HSP) algorithm rather than its error estimation counterpart: continuous hidden subgroup problem (CHSP). We also discuss the (minor) speed-up obtained when exploiting Galois automorphisms thnaks to the Buchmann-Pohst algorithm over OK -lattices.

Introduction

The difficulty to compute class groups and its cardinality, the class group, plays an important role in cryptography. Notably, they are at the foundation of a time commitments protocol [START_REF] Aravinda Krishnan Thyagarajan | Efficient CCA timed commitments in class groups[END_REF], a scheme of homomorphic encryption [START_REF] Castagnos | Linearly homomorphic encryption from[END_REF] and a verifiable delay function [START_REF] Wesolowski | Efficient verifiable delay functions[END_REF]. Note that the particular cases play an important role as the former two examples use quadratic fields and for the latter the cyclotomic case can be the fastest.

From a perspective of theoretical computer science, these schemes are broken because there exists a quantum algorithm of polynomial time complexity [START_REF] Biasse | Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields[END_REF]. However, from a cryptographic point of view it is required to obtain a more precise estimation of the amount of qubits and of quantum gates, as it was done for the other primitives of public key cryptography [START_REF] Daniel J Bernstein | Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies[END_REF][START_REF] Banegas | Concrete quantum cryptanalysis of binary elliptic curves[END_REF][START_REF] Liu | CNOT-count optimized quantum circuit of the Shor's algorithm[END_REF][START_REF] Beauregard | Circuit for Shor's algorithm using 2n+ 3 qubits[END_REF][START_REF] Proos | Shor's discrete logarithm quantum algorithm for elliptic curves[END_REF][START_REF] Zalka | Shor's algorithm with fewer (pure) qubits[END_REF][START_REF] Häner | Factoring using 2n + 2 qubits with toffoli based modular multiplication[END_REF][START_REF] Roetteler | Quantum resource estimates for computing elliptic curve discrete logarithms[END_REF][START_REF] Liu | CNOT-count optimized quantum circuit of the Shor's algorithm[END_REF].

Let us recall the chronology of the works addressing this question. Note that both in the classical and quantum algorithms class group and unit group are very similar and they are sometimes computed simultaneously in order to have a halting condition, as in the classical algorithm of Buchmann and McCurley. In 1994, Shor designed a quantum algorithm to factor integers and, respectively, solve the discrete log problem in cyclic groups [START_REF] Peter | Algorithms for quantum computation: discrete logarithms and factoring[END_REF]. Kitaev [START_REF] Yu | Quantum measurements and the abelian stabilizer problem[END_REF] reformulated the algorithms by reducing both problems to finding the set of periods of functions defined over Z r with finite r and taking values in a finite set; this is the hidden subgroup problem (HSP). Note that the parameter r affects the time and space complexity only in a polynomial manner.

In 2002, Hallgren [START_REF] Hallgren | Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem[END_REF] 3 reduced the computation of a fundamental unit of a real quadratic field to finding the set of periods of a function defined over R. More generally, if a function defined over R m has a lattice (discrete subgroup) of periods, then finding the set of periods is the continuous hidden subgroup problem (CHSP). As for factoring and discrete log, the unit group is sub-exponential on a classical computer and polynomial on a quantum one.

When m = 1, the main difference between HSP and CHSP is the problem of finding α ∈ R when given approximations of kα and ℓα for two integers k and ℓ ; this is solved using continued fractions. To compute fundamental units for a family of number fields of constant degree, one has to solve CHSP for m ≥ 1 bounded by a constant. In contemporary works, Hallgren [START_REF] Hallgren | Fast quantum algorithms for computing the unit group and class group of a number field[END_REF] and Schmidt [START_REF] Schmidt | Polynomial time quantum algorithm for the computation of the unit group of a number field[END_REF] replaced the continued fractions by an LLL-based algorithm of Buchmann and Pohst [START_REF] Buchmann | Computing a lattice basis from a system of generating vectors[END_REF].

To this point, CHSP and HSP have an identical quantum part and differ in the classical post-treatment. When the degree of the number fields is free to be unbounded in a family of discriminants going to infinity, one has to solve CHSP for unbounded parameters m, possibly as large as the logarithm of the discriminants. In this case, the previous algorithms [START_REF] Hallgren | Fast quantum algorithms for computing the unit group and class group of a number field[END_REF][START_REF] Schmidt | Polynomial time quantum algorithm for the computation of the unit group of a number field[END_REF] require an exponential time in m, the degree of the number fields, as it was shown by Biasse and Song in [START_REF] Biasse | On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in Q(ζ 2 k )[END_REF]Prop. B.2] 4 .

In 2014, Eisenträger et al. [START_REF] Eisenträger | A quantum algorithm for computing the unit group of an arbitrary degree number field[END_REF] 5 achieved to make this algorithm polynomialtime for arbitrary degree number fields. For this the periodic function is multiplied by a Gaussian. Before the full version [START_REF] Eisenträger | Long version of the submission to STOC 2014 for A quantum algorithm for computing the unit group of an arbitrary degree number field[END_REF] of this work was made public, a second team, de Boer et al. [START_REF] Koen De Boer | On the quantum complexity of the continuous hidden subgroup problem[END_REF], worked on a more thorough analysis of the algorithm and established in 2019 the precise complexities (space and time) for the CHSP.

Our contribution and cryptographic recommendations. The goal of this article is to make possible a precise resource comparison between computing unit and class groups on one side and breaking symmetric cryptosystems like AES on the other side, as requested by the NIST specifications [START_REF]Submission requirements and evaluation criteria for the postquantum cryptography standardization process[END_REF]. Indeed, experts in the technology of quantum computers study the NISQ scenario in which errorcorrected quantum computers with 100-to-1000 qubits become available whereas a quantum computer with 10 20 qubits remains unfeasible or too expensive to be considered. In this context, the estimation of the number of qubits as "polynomial" in [START_REF] Eisenträger | Long version of the submission to STOC 2014 for A quantum algorithm for computing the unit group of an arbitrary degree number field[END_REF] is not enough. We instantiate the case of unit and class group in the general frame of CHSP [START_REF] Koen De Boer | On the quantum complexity of the continuous hidden subgroup problem[END_REF] and obtain that the number of qubits is O(m 5 ), e.g. when m = 10000 a quantum attack requires 10 20 error-corrected qubits.

We continue by investigating possible weak number fields K: is it a security problem if K has automorphisms? Is it a weakness if K is cyclotomic?

In Section 3.3 we explain that automorphisms allow to implement LLL over O K and obtain a speed-up which is at most polynomial in the number of automorphisms.

In the case of cyclotomic fields, the speed-up is not automatic: if one runs the general algorithm on these fields, the number of qubits is O(m 5 log m). However, we make the following observation: Assume that L is an unknown lattice, M ⊂ L is known and has a short basis, and one has an algorithm to produce vectors near L * . Then one can use the short basis of M to bring any vector near L * to their nearest vector of M * and they will automatically be in L * .

Cryptographic recommendations. A precise estimation of the resources to compute class and unit groups shows that they are more resistant than symmetric cryptosystems if one avoids weak keys. If one wants to use class group based (CGP-based) cryptography then:

one must avoid fixed degree fields as they use O(m) qubits; one must avoid cyclotomic fields as they use O(m 2 log m) qubits; Also a HSP-based algorithm exists; one might prefer to use fields with automorphisms to speed-up the computations as they require Ω(m 3 ) qubits and the speed-up concerns only the Buchmann-Pohst algorithm and is polynomial in the number of automorphisms.

Road map. The article is organized as follows. In Section 2 , we explain our improvement as a general problem of lattices, outside the context of unit groups and quantum computing. Then, in Section 3 we make a detailed presentation of the quantum algorithms for unit groups and combine results to state the complexity of the algorithms for arbitrary number fields. We exploit the automorphisms in Subsection 3.3. In Section 4 we instantiate the previous complexities in the case of cyclotomic and abelian fields, and compare with our improvement from Section 2. Finally, in Section 4.2 we make an attempt to reduce the unit-group computations to HSP instead of CHSP, this reduces massively the number of qubits needed, especially for cyclotomic fields of index p k for small primes p.

Our improvement seen as a lattice problem

Let ⟨x, y⟩ denote the dot product of two vectors x, y ∈ C n . Given a lattice L ⊂ R m , we call dual of L the lattice

L * = {y ∈ R m | ∀x ∈ L, ⟨x, y⟩ ∈ Z n }.
Let us recall a series of properties of L * (see [START_REF] Banaszczyk | New bounds in some transference theorems in the geometry of numbers[END_REF] for a reference).

Lemma 21 1. If L is generated by the rows of a matrix B then L * is generated by the rows of (B t ) -1 ; in particular det

L * = 1/ det L; 2. If M is a sublattice of L then L * ⊂ M * and [L : M ] = [M * : L * ].

Informal presentation

The CHSP algorithm to compute unit groups calls L the lattice of units and follows the following strategy:

1. Use a quantum procedure to generate vectors of C n in a small ball around each vector of a set of generators of L * . 2. Apply the Buchmann-Pohst algorithm (which is classical of polynomial time)

and the previously found vectors to find a basis of L * . 3. Invert the matrix of the previously found basis to obtain a basis of L (this is classical of polynomial time).

A characteristic of Buchmann-Pohst's algorithm is that it has a large precision decrease 6 , namely one needs a large number of bits of precision on the vectors computed in Step 1 in order to have much fewer bits of precision on the basis of L * . Given a precision requirement τ , i.e. log τ bits of precision, in [START_REF] Koen De Boer | On the quantum complexity of the continuous hidden subgroup problem[END_REF] one computes that the input of Buchmann-Pohst must have precision which depends on k. In this work we reduce the number of qubits required by Step 1.

In the case of cyclotomic fields, one has a basis for the lattice of cyclotomic units M ⊂ L. This allows to compute a basis of M * which contains the unknown lattice L * . Our idea is as follows: when given a vector sufficiently close to L * , solve CVP with respect to M * and automatically it will be in L * . In more detail, let m 1 , . . . , m n be a basis of L. We do Step 1 at low precision and obtain y and then we correct it into y so that ⟨y, m i ⟩ ∈ Z n for all i = 1, 2, . . . , n. At this point we have a generating set of L * at high precision. For simplicity of exposition we can still apply the Buchmann-Pohst algorithm. In view of a practical implementation one can also use an algorithm for Hermite normal form.

Precise statement

Step 1 produces vectors y close to L * such that y := CVP( y, L * ) follow a continuous distribution on R m which is close to a discrete Gaussian distribution c on L * . The following definition is a precise description of its output and focuses on the properties of c used in the following sections.

Definition 22 (Dual lattice sampler) Let c : L * → C be a map such that

ℓ * ∈L * |c ℓ * | 2 = 1. Let 1/4 > ϵ > 0, 1/2 >
δ > 0 and r > 0 be three parameters. An algorithm is a dual lattice sampler of parameters (ϵ, δ, r) if it outputs a vector x ∈ R m such that, for any finite set S ⊂ L * , one has

Prob y ∈ ℓ * ∈S B(ℓ * , δλ * 1 ) ≥ ℓ * ∈S |c ℓ * | 2 -η.
for a map c satisfying:

6 See Th 10 in [START_REF] Koen De Boer | On the quantum complexity of the continuous hidden subgroup problem[END_REF] for a precise estimation. 1. Uniformity property: there exists ε ≤ 1/4 such that, for every strict sublattice N ⊊ L * :

ℓ * ∈N |c ℓ * | 2 < 1 2 + ε.

Concentration property:

There exists r = r(m) and 0 < p < 1 2 -ε -η such that:

|ℓ * |>r |c ℓ * | 2 < p.
We can now define the problem we tackle. Problem 1. Let M ⊂ L ⊂ R m be two lattices. Let ϵ, δ, r > 0 and k ∈ N be parameters. We are given a basis of M ; an upper bound on [L : M ]; a dual lattice solver for L of parameters δ and η of our choice.

Compute a basis (z 1 , . . . , z m ) ∈ L given by the value of [L : M ] and the coordinates of the z i in a basis of 1 [L:M ] M .

Let B M be the matrix whose rows are the basis (z 1 , . . . , z m ) of M . We propose the following solution to this problem, where we will make precise later the value of δ so that the time complexity is polynomial.

Algorithm 1 Full computation of L using the dual lattice sampler.

α,β = max{∥M v∥ α | ∥v∥ β ≤ 1}.
When α and β are not specified 7 , ∥B∥ denotes ∥B∥ ∞,1 :

∥B∥ = ∥B∥ ∞,1 = max j i |B i,j |.
When α = β we simply write ∥B∥ α . Note that

∥B∥ ∞,1 ≥ ∥B∥ 2 = max i j |B i,j | 2 ≥ ∥B∥ ∞,1 / √ m.
In this article, the complexity of the algorithms depends on O(log ∥B∥ ∞,1 ) = O(log ∥B∥ 2 +log m). Since log ∥B∥ = Ω(m), this justifies that we drop the indices of the operator norm.

Theorem 24 a) Algorithm 1 solves Problem 1 if δλ * 1 (M ) < 1/(2 ∥B M ∥). The number of qubits is O(Qm) with Q given in Equation (1).
We prepare the proof with two lemmas.

Lemma 25 (Lemma 5 in [19]) We note k = α(m + m log 2 R + log 2 (det L)), for an absolute constant α > 1.
Let y 1 , y 2 , . . . , y k be the first k vectors output by a dual basis sampler. For i = 1, 2, . . . , k put y i = CVP( y i , L). Then for any value of the absolute constant α > 2 we have

Prob(y 1 , . . . , y k generate L) ≥ 1 -c m ,
where c < 1 is an explicitly computable constant.

From now on, we fix such a k, and we use it in Algorithm 1.

Algorithm 2 Babai's BDD solver.

Input: y ∈ R m such that d( y, M * ) < 1/(2 ∥BM ∥)
Output: CVP( y, M * ), as a vector and as coordinates in a basis of M * compute z := B t M y; round z = (z1, . . . , zn) := (⌊ z1⌉, . . . , ⌊ zn⌉)

return y := BM * z ∈ M * and z ∈ Z m . Let us put δ such that d( y, M * ) = δλ * 1 (M ).
The following result can be seen as a reformulation of a result of Babai.

Lemma 26 ([2] Eq. (4.3)) Algorithm 2 solves BDD( y, M * , δλ * 1 (M )) in clas- sical polynomial time when δλ * 1 (M ) < 1/(2 ∥B M ∥ 2 )
, where B M is the matrix of a basis of M .

Proof. We claim that ⌊B t M y⌉ = B t M y ′ where y ′ = CVP( y, M * ). Indeed

B t M y -B t M y ′ ∞ ≤ B t M y -B t M y ′ 2 ≤ ∥BM ∥ 2 • y -y ′ 2 = ∥BM ∥ 2 δλ * 1 (M ) < 1/2. Since ⌊B t M y⌉ = B t M y ′ , by Lemma 21, y = B M * = ((B M ) t ) -1 (B t M y ′ ) = y ′ , so the algorithm is correct.
Proof (Proof of Theorem 24.a)). We structure the proof in several steps. step 1. We apply Lemma 25 to the lattice L * . Then, with probability 1 -c m , the vectors y 1 , y 2 , . . . , y k generate L * . step 2. Let us fix i ∈ {1, 2, . . . , k}. By the definition of the dual sampler, with probability greater than 1 -η, dist( y i , L * ) < δλ * 1 (M * ). Hence Lemma 26 applies and Line 4 is executed in classical polynomial time.

Since, L * ⊂ M * and y

′ i := CVP( y i , L * ) belongs to M * . Since d( y i , L * ) < λ * 1 (M )/2, y ′ i is the closest vector of M * to y i , or equivalently y ′ i = y i .
We summarize by y i = CVP( y, L).

step 3. Algorithm 2 can output z in addition to y. This means that the vectors y i ∈ L * are given by their integer coordinates with respect to a basis of M * .

In Line 6, one computes the HNF [16, Sec 2.4.2] by manipulating integer coefficients only. This is done in classical polynomial time without loss of precision. step 4. Since 3 Previous results on the quantum unit-group calculation

B M ∈ Mat k (Z), (B -1 M ) ∈ 1 det B M Mat k (Z).

A summary on CHSP

We first define the Continuous Hidden Subgroup Problem to which the problem of computing the unit group can be reduced.

Definition 31 (Continuous Hidden Subgroup Problem -CHSP [START_REF] Eisenträger | Long version of the submission to STOC 2014 for A quantum algorithm for computing the unit group of an arbitrary degree number field[END_REF]) Let f : R m → S, where S = ⊕ i∈{0,1} n C|i⟩ is the space of states of n qubits. The function f is an (a, r, ε)-oracle hiding the full-rank lattice L if and only if it verifies the following technical conditions:

1. L is the period of f , i.e. ∀x∀ℓ ∈ L, f (x + ℓ) = f (x). (periodicity) 2. The function f is a-Lipschitz. (Lipschitz condition) 3. ∀x, y ∈ R m such that dist(x -y, L) ≥ r, we have |⟨f (x) | f (y)⟩| ≤ ε. (strong periodicity)
Given an efficient quantum algorithm to compute f , compute the hidden lattice of periods L.

Let us now recall the algorithm which solves CHSP. We mimick the technique which solve the Hidden Subgroup Problem (HSP). For this latter, let g : G → S, with G a finite cyclic group. The solution goes as follows:

1. compute the superposition x∈G |x⟩ and then apply g to obtain the superposition of the values of g: |ψ(g)⟩ = x∈G g(x)| x ⟩; 2. apply the Quantum Fourier Transform (see [START_REF] Peter | Algorithms for quantum computation: discrete logarithms and factoring[END_REF]) to obtain y∈G ĝ(y)| y ⟩; this expression is equal to y∈H ⊥ ĝ(y)| y ⟩ 3. measure the state to obtain an element g ∈ H ⊥ .

A few iterations of the algorithm allow to have a set of generators of H ⊥ and hence to compute h.

Coming back to the continuous case, if we were able to implement the Fourier Transform, we would be able to draw random vectors of L * . If a set of generators is known, then one can extract a basis to completely describe L * . Then L would be obtained thanks to Lemma 21. The obstacle is here that R m is infinite and the Fourier Transform (QFT) is now an integral instead of a finite sum so we cannot compute the QFT precisely. As a way around, we do an approximate computation of the QFT by the means of a Riemann sum, which amounts to restrict the domain to a segment and to discretize it. Set

ρ σ (x) = exp(-π 2 ||x|| 2 σ 2
).

Lemma 32 (Thm. 2 in [START_REF] Koen De Boer | On the quantum complexity of the continuous hidden subgroup problem[END_REF]) There exists dual lattice sampler quantum algorithm of polynomial time which uses Qm + n qubits, where

Q = O m log m log 1 η + O log Lip(f ) ηδλ * 1 . (1)

Algorithm 3 A CHSP solver

Input: A function f which can be computed in polynomial time, as in Definition 31 having a hidden period lattice L. We require det L up to one bit of precision and Lip(f ). A parameter τ of required precision. Theorem 33 (Space complexity of the CHSP solver, Th 1 of [START_REF] Koen De Boer | On the quantum complexity of the continuous hidden subgroup problem[END_REF]) We set8 η = 1/k 2 . Let N f be the amount of qubits necessary to encode f . We fix τ the error expected on basis' vectors. Then, Algorithm 3 is correct and requires a number of qubits:

Output: ( x1, . . . , xm) such that (x1, . . . , xm) is a basis of L for xi = CVP( xi) and ∥xi -xi∥ ≤ τ 1: k → log 2 ( √ m Lip(f )) + log 2 (det L)) ▷ value from [19, th 3] 2: for i = 1, 2, . . . , k do ▷ Step 1 -Quantum 3: ỹi ← output(dual lattice sampler: δλ * 1 = (λ * 1 ) 3 (det L) -1 2 O(mk) ∥B L * ∥ m ∞ ) ▷ value from [
N qubits = O(m 3 • log(m)) + O(m 3 • log(Lip(f ))) + O(m 2 • log(det(L))) +O m • log Lip(f ) λ * 1 + O m • log 1 λ * 1 •τ + O(N f ).
(

) 2
The complexity of the algorithm depends on λ * 1 which has the advantage that it is an invariant of the lattice. However, λ * 1 is difficult to lower bound and in some applications one has bounds on the coefficients of B L , the matrix of some basis of L.

Lemma 34 2 -3m ∥B t L ∥ ≤ 1 λ * 1 ≤ ∥B L ∥. Proof. The first inequality is [19, Corollary 6 in Appendix B.1]. The second inequality is direct. Let v ∈ L * such that ∥v∥ 2 = λ * 1 . By Nota- tion 23 we have ∥B L v∥ 1 ≤ ∥B L ∥ ∥v∥ ∞ . Since v ∈ L * , v ̸ = 0, B L v ∈ Z n and then ∥B L v∥ 1 ≥ 1. Also, ∥v∥ 2 ≥ ∥v∥ ∞ , so 1 ≤ ∥B L ∥ λ * 1 ,
which proves the second inequality.

Reduction of the computation of the unit group to CHSP

In this subsection, we present the method of [START_REF] Eisenträger | Long version of the submission to STOC 2014 for A quantum algorithm for computing the unit group of an arbitrary degree number field[END_REF] to reduce the computation of the unit group to the CHSP. For completeness, we reproduce the description of [START_REF] Biasse | Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields[END_REF]Sec ].

Let G := R n1+n2 × (Z/2Z) n1 × (R/Z) n2
, and the mapping φ : (u 1 , . . . , u n1+n2 , µ 1 , . . . , µ n , θ 1 , . . . , θ n2 ) → ((-1) µ1 e u1 , . . . , (-1) µn 1 e un 1 , e 2iπθ1 e un 1 +1 , . . . , e 2iπθn 2 e un 1 +n 2 ) Let σ 1 , σ n1 and respectively σ n1+1 , . . . , σ n1+n2 be the real and the complex embeddings of K. We consider the Cartesian ring

E = σ 1 (O K ) × • • • × σ n1+n2 (O K ). An E-ideal is a sub-Z-lattice Λ of E which is such that ∀x ∈ E, xΛ ⊂ Λ.
We define

g : G → {E-ideals} x → g(x)E.
Definition 35 (Ex. 5.3 of [START_REF] Eisenträger | Long version of the submission to STOC 2014 for A quantum algorithm for computing the unit group of an arbitrary degree number field[END_REF])

Set H = ⊗ i∈N C|i⟩, H Q = ⊗ Q i=0
C|i⟩ and π Q : H → H Q the projection on the first Q qubits. We define the straddle encodings of parameter ν, str ν : R → H, str m,ν : R m → H m and f : {lattices of R m } → H m as follows:

-| str ν (x)⟩ = cos( π 2 t)|k⟩ + sin( π 2 t)|k + 1⟩, where k = ⌊x/ν⌋, t = x/ν -k; -| str m,ν (x 1 , . . . , x m )⟩ = ⊗ m i=1 | str ν (x i )⟩; -| str lattice,m,ν (L)⟩ = γ -1/2 x∈L e -π∥x∥ 2 /s | str m,ν (x)⟩ with γ = x∈L e -2π∥x∥ 2 /s 2 .
Note that computing str lattice,m,ν up to an error τ requires O(mν log τ ) qubits. In Appendix A we propose an alternative function f which can be used for totally real K and doesn't use the straddle encoding.

Finally, one defined f as follows:

f : G g -→ {E-ideals} | str⟩ ---→ {quantum states} = H m Q . ( 3
)
The following result is the conjunction of several results from [START_REF] Eisenträger | Long version of the submission to STOC 2014 for A quantum algorithm for computing the unit group of an arbitrary degree number field[END_REF].

√ n n-1 2ν √ m
, where c is an explicitly computable constant. In particular, ε < 1/4, r < λ 1 (L)/6 and

log 2 Lip(f ) = O m 2 + m log D .
Proof. Note first that if K = Q or is quadratic imaginary then m = 0 and there is nothing to be computed. Also note that n/2 -1 ≤ m ≤ n -1 so we can interchange O(m) and O(n) in the asymptotic complexity.

By [START_REF] Eisenträger | Long version of the submission to STOC 2014 for A quantum algorithm for computing the unit group of an arbitrary degree number field[END_REF]Th 5.5] f is an (r, ∞, ε)-oracle hiding the lattice 5 )-oracle hiding the same lattice.

L = log O * K with r = (s √ n) n-1 2ν √ n and ε ′ = 3/4. By [22, Th D.4] f is a-Lipschitz with a = √ πns 4ν + 1. By [22, Lem E.1] f 5 := f ⊗ f ⊗ f ⊗ f ⊗ f is an (5 Lip(f ), r, (ε ′ )
In particular, (ε ′ ) 5 = 243/1024 < 1/4 satisfies the requirements of the CHSP solver (see Def 22).

The condition r < λ 1 (L)/6 is satisfied as

λ 1 (L) ≥ 1/2 by [22, Lem B.3] and r = O s √ n n-1 2 4n(s √ n) 2n ≤ 1 2s n-1 ≤ 1 6 • 2 n √ D < 1 12
.

Finally, we have

log 2 Lip(f ) = O(ms) = O(m 2 + m log D).
Corollary 37 Let K be a number field of discriminant D and unit rank m. For any error bound τ > 0. There exists a quantum algorithm of time poly(m, log D, log τ ) using a number of qubits

N qubits = O(m 5 + m 4 log D) + O(m log τ -1 )
which, for a set of units µ, ε 1 , . . . , ε m such that µ is a root of unity and the other have infinite order and

O * K ≃ µ Z/ω × ε Z 1 × • • • × ε Z m ,
the algorithm outputs σ i (log(σ i (ε j )) 1≤i≤m,1≤j≤n + τ i,j with τ i,j ∈ R such that |τ i,j | ≤ τ .

Proof. By Theorem 36, there exists a function f which hides Log O * K and which is an (a, r, ε)-oracle such that r ≤ λ 1 (L)/6 and ε < 1/4. By Theorem 33 there exists a polynomial-time algorithm which uses a number of qubits as in Equation (2).

In the CHSP solver one takes stores the values of f on Qm qubits, so the O(N f ) = O(Qm). We are left with estimating Q. For this, the main part is Lemma 21:

O(log(1/λ * 1 )) = log 2 (∥B L ∥) = O(m + 1 m log D).
We used the fact that L admits an LLL-reduced basis, which is enough to bound 1/λ * 1 , but this cannot be computed because we have no basis of L until the end of the CHSP algorithm. We inject this in Equation ( 2) and obtain the announced value.

Given Log O * K , we are left with computing µ, ε 1 , . . . , ε m . Let ω be the number of roots of unity of K and recall that ω divides D. By multiplying the time by log D, we can enumerate the divisors of D, so we can assume that we know ω. By Dirichlet's Theorem, an m-tuple such that Vol(Log(ε j )) = R and a root of unity of order ω, form a basis of the unit group. 9Remark 38 10 The analytic class number formula states that Rh = √ D 1+o (1) .

Very little is known on the distribution of h but no conjecture, e.g. the Cohen-Lenstra heuristic, is contradictory with the fact that h = 1 and

R = √ D 1+o(1)
for a proportion of 1 -o(1) of the number fields. Hence, max i (∥log

ε i ∥) ∼ R 1/m
and the unit group is fully determined only when log τ = Ω( √ D). In that case CHSP doesn't compute the full unit group in polynomial-time.

Note however that in the case of classical algorithms there is no algorithm which computes a partial information on the regulator without fully computing it (see for instance [START_REF] Buchmann | A subexponential algorithm for the determination of class groups and regulators of algebraic number fields[END_REF]). So the algorithm studied in this article suggests a quantum advantage in the case of unit groups. The large number qubits used by the present algorithm is in contrast with Shor's algorithm, which requires 2m + O(1) qubits in the case of factorization and discrete logarithms and 7m + O(1) in the case of elliptic curve discrete logarithms. The paragraph "Conclusion and Research Directions" at the end of [19, Sec 1] states that, even if the complexity in log D is ignored and one uses approximation techniques in the quantum Fourier transform, the algorithm requires Ω(m 3 ) qubits. We refer to Appendix B for an informal discussion about the security levels one can propose in the case of quantum algorithms.

Exploiting automorphisms

In this section we tackle the case of cyclotomic fields without using the cyclotomic units. Instead we use the fact that K has Galois automorphisms.

The main impact of this section is to reduce the practical cost of the Buchmann-Pohst step (which is non-quantum). Indeed, this step consists in applying LLL to a lattice L which has more algebraic structure: it is a Z[ζ k ]-module for an integer k. From an asymptotic point of view, Fieker and Stehlé [START_REF] Fieker | Short bases of lattices over number fields[END_REF] proved that, if one is to find a new Z[ζ k ]-basis of L which is shorter in a sense to be specified later, one has the best asymptotic complexity up to a polynomial factor if one follows the steps:

u λ = e,...,e k (σ e1 1 (u) • • • σ e k k (u)) ce 1 ,...,e k .
Lemma 39 Let G := Aut(F/Q) and σ ∈ G of order k.

1. Then O * F is an Z[ζ k ]-lattice. 2. If k is not of the form k = 2 ε p ei i with ε ∈ {0, 1} and p i ≡ 1 (mod 4) then O * F is a O Q(i √ d) -lattice for some divisor d of k. Proof. 1. If σ ∈ G, every Z[G]-lattice is a Z[σ]-lattice.
In order to prove that Φ k is the minimal polynomial of the endomorphism associated to σ,

let u ∈ O * F and set v = u Φ k (σ) . Then v σ-1 = u σ k -1 = u/u = 1 and further σ(v) = v. But σ ∈ Aut(F/Q), so v ∈ O * F Q = ±1 ∈ (O * F ) tors . Equivalently, Φ k (σ)(u) ∈ (O * F ) tors and Φ k is an annihilating polynomial of σ. Since it is irreducible, it is the minimal polynomial of σ. But ζ k has the same minimal polynomial, so Z[σ] ≃ Z[ζ k ]. 2. It is a classical result that, if one sets p * = (-1) p-1 2 p for a prime p, then Q( √ p * ) ⊂ Q(ζ p ). When k ′ | k one has Q(ζ k ′ ) ⊂ Q(ζ k ).
Hence if k is divisible by 4 or a prime p ≡ 3 (mod 4), one can take d = 4 or d = p in the statement of the lemma.

Norm-Euclidean rings O K . Recall that Z[i] = Z[ζ 4 ] and O Q(i √ 3) = Z[ζ 3 ] are norm-Euclidean: let k = 3 or 4, in order to divide a ∈ Z[ζ k ] by b ∈ Z[ζ k ] one rounds each coordinate of a/b ∈ Q[ζ k ]
and denotes the result by q, and then one sets r = a -bq; if [START_REF] Napias | A generalization of the LLL-algorithm over euclidean rings or orders[END_REF] showed that the LLL algorithm extends naturally to the norm-Euclidean rings Z[i] and

N K/Q (r) < N K/Q (b) for all a, b we say that Z[ζ K ] is norm-Euclidean. Napias
Z[ζ 3 ].
Definition 310 (norm-Euclidean ring, Prop 1.2.5 of [START_REF] Camus | Méthodes algorithmiques pour les réseaux algébriques[END_REF], Def 2 of [START_REF] Kim | Lattice reductions over euclidean rings with applications to cryptanalysis[END_REF]) The Euclidean minimum of a number field K is

M K := max x∈K min y∈O K N K/Q (x -y).
In particular, when K is imaginary quadratic,

M K = max x∈C min y∈O K |x -y| 2 . If M K < 1 we say that K is norm-Euclidean.
Example 2 (Prop 1.2.4 of [START_REF] Camus | Méthodes algorithmiques pour les réseaux algébriques[END_REF],Prop 3 of [START_REF] Kim | Lattice reductions over euclidean rings with applications to cryptanalysis[END_REF]). The following fields are norm-Euclidean: [START_REF] Banaszczyk | New bounds in some transference theorems in the geometry of numbers[END_REF][START_REF] Banegas | Concrete quantum cryptanalysis of binary elliptic curves[END_REF][START_REF] Barbulescu | Improving NFS for the discrete logarithm problem in non-prime finite fields[END_REF][START_REF] Daniel J Bernstein | Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies[END_REF][START_REF] Biasse | Quantum algorithms for attacking hardness assumptions in classical and post-quantum cryptography[END_REF][START_REF] Biasse | On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in Q(ζpn )[END_REF][START_REF] Biasse | On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in Q(ζ 2 k )[END_REF][START_REF] Buchmann | A subexponential algorithm for the determination of class groups and regulators of algebraic number fields[END_REF][START_REF] Castagnos | Linearly homomorphic encryption from[END_REF][START_REF] Cohen | A course in computational algebraic number theory[END_REF][START_REF] Duursma | Speeding up the discrete log computation on curves with automorphisms[END_REF]

-Q(ζ k ) for k ∈ {1,
, 24}; -Q(i √ d) for d ∈ {1, 2, 3, 7, 11}. Definition 311 (O K -LLL-reduced basis) Let K = Q(i √ d
) be an imaginary quadratic field. We identify K with its embedding in C such that √ -d is mapped to a complex number of positive imaginary part.

We consider the dot product ⟨•, •⟩ of C m and we set ∥x∥

= ⟨x, x⟩, which is a norm. Let b 1 , b 2 , . . . , b m be independent in C m . We say that L := ⊕ m j=1 Z[ζ k ]b j is a Z[ζ k ]-lattice and {b j } is a basis. Let {b * 1 = b 1 , b * 2 , . . . , b * m } be the Gram- Schmidt orthogonalization of {b j } with respect to the dot product. We set µ i,j = ⟨b i , b * j ⟩/ b * j 2 . We say that {b j } is O K -LLL-reduced with respect to M K < δ < 1
if the following two conditions hold:

1. ∥µ i,j ∥ ≤ M K for 1 ≤ j < i ≤ m; (size reduced) 2. ∥b * i ∥ 2 + ∥µ i,i-1 ∥ 2 b * i-1 2 ≥ δ b * i-1

. (Lovász condition)

In two contemporary works Kim and Lee [START_REF] Kim | Lattice reductions over euclidean rings with applications to cryptanalysis[END_REF] and Camus [START_REF] Camus | Méthodes algorithmiques pour les réseaux algébriques[END_REF] extended LLL to all norm-Euclidean rings Z[ζ k ] and O Q(i √ D) . In particular, when K is a norm-Euclidean quadratic imaginary field, [START_REF] Camus | Méthodes algorithmiques pour les réseaux algébriques[END_REF]Th. 1.3.8] states that any O K -reduced basis b 1 , . . . , b m of L is such that

∥b j ∥ ≤ 1 δ -M K j-1 (det L) 1/m . A direct application of O K -LLL is the O K variant of
B ← c m K D 1/m ; C ← (B/µ) m γ 1/2 m ; M ← (k √ m/2 + √ k)C; q ← ⌈log 2 ( √ mk + 2) M 2 (k-1
)/2 /µ ⌉ 2: the the OK -LLL-reduction of the following matrix on the left to obtain the matrix on the right

         ⌊ g12 q ⌋ • • • ⌊ g k 2 q ⌋ 1 . . . 1          ⇝         c1 • • • c k m1 • • • m k         3: return c k-m+1 , c2, . . . , c k
of the matrix in Algorithm 4 are bounded by M . We use the upper bound of the norm of an O K -reduced basis of [14, Prop 1.3.8] instead of [38, (1.12)] to obtain the equivalent of [START_REF] Buchmann | Computing a lattice basis from a system of generating vectors[END_REF]Eq (9)]:

∥ c j ∥ ≤ 2 (k-1)/2 M 1 ≤ j ≤ k -m. (4)
For any vector

( c, m) ∈ ⊕ k j=1 Z(c j , m j ) such that m = (m (1) , . . . , m (k) ) is not a relation of b 1 , . . . , b k , i.e. m ̸ ∈ L * , i.e.
k j= m (j) b j ̸ = 0. Then, the arguments in the proof of [13, Th 3.1] can be copied in a verbatim manner to obtain:

∥ c j ∥ > 2 (k-1)/2 M 1 ≤ j ≤ k. (5)
Since Equations ( 4) and ( 5) are contradictory for 1 ≤ j ≤ k -m, the only possibility is that m ∈ L * . We do the same transformations on the matrix with b j instead of b j and call c j the vectors which replace c j in this case. What we have proved is that

c 1 = c 2 = • = c k-m = 0.
Since the transformations done in the LLL algorithm on the columns of the matrix are reversible, they preserve the rank of any subset of rows of the matrix. The rank of the first m rows of this matrix is dim

L = m. Since c 1 = c 2 = • = c k-m = 0, the vectors c k-m+1 , . . . , c k form a basis of L. LLL over Z[i √ d]
as a practical improvement The constant hidden in the big Oh of implementation is (inverse) proportional to log δ, which (inverse) proportional to log(δ-M K ). Hence the difference is of only a few percentages. The dependence of the time in the rank is quartic, so we replace a number of operations of highprecision real numbers by 2 4 = 16 times less complex numbers at the same level of precision. Finally, using the Karatsuba trick, a multiplication of complex numbers costs 3 multiplications of real numbers, so the overall gain is a factor 16/3 ≈ 5.33. An implementation [START_REF] Elbaz | An extension of the fplll library to hermitian lattices[END_REF] of Z[i √ d]-LLL shows that the reduction of an O K -lattice is ≈ 5 times faster when its algebraic structure is used when compared to forgetting it and using only the underlying structure of Z-lattice:

they used O K = Z[i],
the coordinates of the basis vectors have 512 bits and δ = 0.99 both over Z and Z

[i]. 11
Consequences in cryptography. Given our current contribution, the speed-up due to automorphisms is 5.33.

It is an open question to extend it to a larger class of O K -rings (e.g. [START_REF] Lee | An LLL algorithm for module lattices[END_REF] investigate if LLL can be extended to arbitrary

O K by solving CVP instances in dimension [O K : Z].
). If Buchmann-Pohst can be extended, the best speed-up that one can target is [O K : Z] 3 . Indeed, the dependence of LLL in the dimension is quartic whereas the cost of the arithmetic over O K is quadratic or quasi-linear if fast arithmetic is used The speed-up due to the automorphisms is polynomial in the number of automorphisms. This is a familiar situation because a similar speed-up happens for automorphisms in the case of classical algorithms for factorization, discrete logarithms in finite fields and discrete logarithms on elliptic curves (see e. g. [START_REF] Joux | The number field sieve in the medium prime case[END_REF]Sec 4.3], [START_REF] Barbulescu | Improving NFS for the discrete logarithm problem in non-prime finite fields[END_REF]Sec 5.3]). For instance, the attacks in [START_REF] Duursma | Speeding up the discrete log computation on curves with automorphisms[END_REF] against ECDSA using endomorphisms of the curve achieved a polynomial speed-up in an algorithm of exponential complexity. The community reacted by suggesting to use elliptic curves with endomorphisms as their effect was now considered to be benign, e.g. [START_REF] Robert | Faster point multiplication on elliptic curves with efficient endomorphisms[END_REF]. In a similar manner, if the security of the class group of a given degree and determinant is considered sufficient, we suggest to use fields with automorphisms in order to speed-up the protocol, e.g. it has been done by XTR in cryptosystems based on discrete logarithms in finite fields [START_REF] Arjen | The XTR public key system[END_REF].

A new algorithm using cyclotomic units

When K = Q(ζ m ) for an arbitrary integer m we define the group of cyclotomic units to be the subgroup C of K * generated by -1, ζ m and ζ j m -1 with j = 1, 2, . . . , m -1, intersected with the group of units O * K . We follow the notations of [START_REF] Cramer | Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time[END_REF]Sec. 3], in particular m and k don't have the same meaning as in the other sections. Factor m = p α1 1 p α2 2 • • • p α k k and, for each index i, put m i = m/p αi i . For j = 1, . . . , m -1 we set

v j = 1 -ζ j m , if for all i we have m i ∤ j, 1-ζ j m 1-ζ m i m
, otherwise for the unique i such that m i | j.

Unconditional results

Lemma 41 (Theorem 4.2 in [START_REF] Kučera | On bases of the Stickelberger ideal and of the group of circular units of a cyclotomic field[END_REF]) The lattice M := Log C admits the system of generators {b j = Log(v j ) | j = 1, 2, . . . , m -1}.

Lemma 42 (Lemma 3.5 in [START_REF] Cramer | Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time[END_REF]) For any integer j ∈ {1, 2, . . . , m -1} we have 1 -

ζ j m 2 = O( √ m). Hence ∥B M ∥ 2 = O( √ m).
Q ≪ m log(m log 1 η )) + log 1 δλ * 1 (L) + log(Lip(f )) ≪ (m log m + m log log k) + log m + m 2 + m log D ≪ m log m + m log log D + log m + m 2 + m log D ≪ m 2 + m log D ≪ m 2 log m.
This is to be compared to the O(m 5 + m 4 log D) qubits used by number fields in general (Cor 37) and O(m 5 log m) used by cyclotomic field if the Algorithm 3 were used without taking profit of the cyclotomic units (Ex 1).

Remark 44 Our improvement can be used whenever the lattice of units has a sublattice admitting a short basis and this is not limited to the cyclotomic fields and, more generally, abelian fields. For instance, Kihel [START_REF] Kihel | Groupe des unités pour des extensions diédrales complexes de degré 10 sur Q[END_REF] proposed a family of fields with dihedral Galois group which have a full-rank subgroup of units which are short. Although one expects a speed-up in all these cases, the cyclotomic case is even more special. Indeed, the parameter δ ≤ ∥B M ∥ /λ * 1 (L) depends in a large extent on the index [L : M ]. By [START_REF] Lawrence | Introduction to cyclotomic fields[END_REF]Ex 8.5] (see also [START_REF] Cramer | Recovering short generators of principal ideals in cyclotomic rings[END_REF]Th 2.8]), in the case of cyclotomic fields of prime conductor, [L : M ] = h + (m). By Conjecture 1 this is small, so the impact of the full-rank subgroup is more important in this case.

Consequences of a recent conjecture for cyclotomic fields

One denotes h(m) the class group of Q(ζ m ), h + (m) the class group of its maximal real subfield, i.e.

K := Q(ζ m + ζ -1
m ), and one sets h -(m) = h(m)/h + (m). A folklore conjecture states that h -(m) is large but easy to compute whereas h + (m) is small but hard to compute. A recent work compiled existing conjectures and pushed further the numerical computations, so one can give a precise form to the folklore conjecture.

Conjecture 1 (Assumption 2 in [START_REF] Cramer | Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time[END_REF]). For all integers m, h + (m) ≤ poly(m) for a fixed polynomial poly.

Consequence of the conjecture : class number in real cubic fields without quantum computers Marie-Nicole Gras [START_REF] Nicole | Méthodes et algorithmes pour le calcul numérique du nombre de classes et de unités des extensions cubiques cycliques de q[END_REF] proposed an algorithm to compute class numbers of cyclic cubic fields in polynomial time with respect to a bound on h. If m is the conductor of a cyclic cubic field, then Conjecture 1 implies that h is polynomial in m. Note also that Schoof [START_REF] Schoof | Class numbers of real cyclotomic fields of prime conductor[END_REF] proposed an algorithm for Q(ζ m ) + with prime m which is faster when a small bound on h + (m) is known.

Reduction of unit group computation to HSP

Theorem 45 Under Conjecture 1 the unit group of K = Q(ζ m ) + and its class group can be computed by an HSP algorithm in polynomial time and space.

Proof. Let N = poly(m)! and note that Conjecture 1 implies that O * K ⊂ C 1/N . Let m ′ = φ(m)/2-1 and let ε 1 , . . . , ε m ′ be a basis of C/⟨ζ m , -1⟩. Note that it can be computed using the HNF algorithm from the vectors v j of Lemma 41. Since K is totally real, its only roots of unity are ±1. For any c ∈ C, we call vectorization of c and denote vect(c) the unique (m ′ + 1)-tuple in (e 0 , e 1 , . . . , e m

′ ) ∈ Z/2Z × (Z/N Z) m ′ such that c = (-1) e0 m ′ j=1 ε ej j . We set f : Z/2Z × (Z/N Z) m ′ → canonical representations of Kummer extensions (e 0 , e 1 , . . . , e m ′ ) → K(ζ N , N (-1) e0 m ′ j=1 ε ej j )) (6)
We claim that the period of f is

period(f ) = {vect(u) | u ∈ (O K ) * }.
Indeed, let (e j ) and (z j ) be such that f (e 0 , . . . , e m ′ ) = f (e 0 + z 0 , . . . , e m + z m ′ ) and set ε = (-1) e0 j ε ej j and ζ = (-1) z0 j ε zj j . We have

K(ζ N , N √ ε) = K(ζ N , N √ εζ). Let d := [K(ζ N , N √ ε) : K(ζ N )].
Then the criterion of isomorphism of Kummer extensions [34, page 58]

states that N √ ζ belongs to K(ζ N ). But N √ ζ ∈ R and the maximal real subfield of K(ζ N ) is K, so N √ ζ ∈ O * K . Conversely, if N √ ζ ∈ O * K it is direct that (z 0 , . . . , z m ′ ) is a period of f .
Finally, to compute the complexity of the algorithm, we write a = P(b) for a = b O(1) and a = polylog(b) for a = (log b) O (1) . By [START_REF] Yu | Quantum measurements and the abelian stabilizer problem[END_REF], the cost of the HSP is polylog(N ). Since, for any n, n! ≤ n n , we have time = polylog(N ) = P(poly(m) log(poly(m))) = P(P(m)) = P(m).

Conclusion and open questions

1. The unit group algorithms follow a parallel path to those of other problems like the class group e.g Buchmann's algorithm computes the two groups together and the quantum algorithm for class groups [START_REF] Biasse | On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in Q(ζpn )[END_REF] is a generalization of the one of Hallgren et al [START_REF] Eisenträger | Long version of the submission to STOC 2014 for A quantum algorithm for computing the unit group of an arbitrary degree number field[END_REF]. It is interesting to have a precise estimation of the number of qubits for class groups depending on the bound on the class number, on the computation of discrete logarithms in the class group etc.

2. The idea of a small dual basis can be generalized: a) to all abelian fields; b) to Galois fields with simple group of automorphisms and known units e.g. [START_REF] Kihel | Groupe des unités pour des extensions diédrales complexes de degré 10 sur Q[END_REF]. 3. The possibility of exploiting automorphisms of arbitrary order depends on the possibility of a Buchmann-Pohst algorithm for O K -lattices. One might explore such an algorithm which reduces the size of the norms on average but can locally increase them. 4. The quantum algorithms being probabilistic, the output is not certified. Can one do a classical algorithm to prove that a given set of units generate a subgroup which is ℓ-saturated? 5. The technology of quantum computers is very new and it is not known how many physical qubits correspond to a given number of logical ones. Have the gates used by a HSP algorithms less errors and hence require less errorcorrection? A precise analysis goes beyond the scope of this article.

A An alternative function hiding the units

We place ourselves in the case where K is totally real. As before we call n its degree. Let P be a polynomial which defines K and let α 1 , . . . , α n be the n roots of P in R. Let We claim that the set of periods of f form a lattice Λ such that

2 Log O * K ⊂ Λ ⊂ Log O * K .
Indeed, let ε be in O * K and set (x 1 , . . . , x n ) = Log(ε 2 ). Then w -1 (e x1,...,e xn ) is the representative of ε 2 in the normal basis of K. The coordinates are all integers because ε 2 is in O K = Z[x]/⟨P ⟩. Similarly, w -1 (e -x1 , . . . , e -xn ) is the representative of ε -2 in the normal basis. Its coordinates are integers because ε -2 ∈ O O * K . Conversely, let (x 1 , . . . , x n ) be such that f (x 1 , . . . , x n ) = (0, . . . , 0) and let ε = w -1 (e x1 , . . . , e xn ). Since f (x 1 , . . . , x n ) = 0, the coordinates of ε in the normal basis are integers, so ε ∈ O K . Similarly, ε -1 ∈ O K , so ε is a unit.

Finally, given Λ, one solves a linear system over Z/2Z to find Log O * K . Since K is totally real, its roots of unity are ±1 and Log O * K completely determines O * K .

B A discussion on quantum security levels

The NIST post-quantum challenge [START_REF]Submission requirements and evaluation criteria for the postquantum cryptography standardization process[END_REF] is willingly open on the definition of the computational resources on a quantum computer: "Here, computational resources may be measured using a variety of different metrics (e.g., number of classical elementary operations, quantum circuit size, etc.)" A study conducted by Mosca et al. [START_REF] Mosca | quantum threat timeline report[END_REF] revealed that part of the experts consider that on the medium term one should not consider attacks which uses billions of qubits but one should protect against attacks which use hundred qubits. A similar situation happens in the case of classical algorithms: in 2015 the recommendations of the standardisation agencies (NIST, ANSSI, etc) was to use 2048-bit RSA keys. However, in [START_REF] Adrian | Imperfect forward secrecy: How Diffie-Hellman fails in practice[END_REF] the authors made a precise estimation that RSA 1024 can be broken with their implementation of NFS on a million cores and they made a study that 98% of a sample of million+ servers use RSA 1024. Moreover, more than 30% were supporting RSA 768 which had been broken since 2009.

It is then necessary to be more precise on the quantum resources. We propose a classification on the time complexity and the number of qubits, as in Table 1 (for a review of the quantum attacks on the various public-key primitives see e.g. [START_REF] Biasse | Quantum algorithms for attacking hardness assumptions in classical and post-quantum cryptography[END_REF]). In this light, a verifiable delay function [START_REF] Wesolowski | Efficient verifiable delay functions[END_REF] based on the class group of a number field of high-degree and non-cyclotomic is more secure than RSA.

Fig. 1 :

 1 Fig. 1: Illustration of Algorithm 2.

  Finally, B M and its SNF [16, Sec. 2.4.4] have the same determinant, which equals [L : M ]. Hence, the last step computes [L : M ] in polynomial time.

Theorem 36 (

 36 Theorems 5.5, D.4 and B.3 of [22]) Let K be a number field of degree n, discriminant D, unit rank m and regulator R. Let L := Log O * K which is the hidden period of the function f of Equation (3). Set s = 3 • 2 2n √ nD and ν = 1/(4n(s √ n) 2n ). Then f 5 = ⊗ 5 f is an (r, a, ε)oracle with ε = 243/1024, Lip(f ) = a = √ πns 4ν + 1 and r = s

Example 1 .

 1 1. If K = Q(ζ n ) with prime n then m = (n -1)/2 and log 2 D = (m -2) log 2 m. If one applies Algorithm 1 without taking notes that it is a very particular, the algorithm uses O(m 5 log m) qubits. 2. If K is a Kummer extension, i.e. K = Q( n √ D) for some integer without powers D, then O(log disc K) = O(log D) and the number of qubits is O(n 5 + n 4 log D). The value of n and D are independent. When n is fixed, i.e; the case of real quadratic fields, the number of qubits is O(disc K). When n ∼ log D, the number of qubits is (log D) 5 /(log log D) 4 .

1 .

 1 forget the Z[ζ k ]-module structure; 2. reduce the basis of the underlying Z-lattice; 3. compute again the Z[ζ k ]-module structure. From a practical point of view though, we shall explain that it is faster to work directly with the Z[ζ k ]-module structure. The structure of Z[G]-lattice. In the following, a lattice which has a structure of R-module for some ring R is called a R-lattice. When G := Aut(K/Q), the group of Galois automorphisms, is abelian, as it is the case for cyclotomic fields, O * K /(O * K ) tors has a structure of Z[G]-lattice. Indeed, for σ ∈ G and u ∈ O * K we set σ • u = σ(u) and for set σ 1 , . . . , σ k ∈ G of ring generators of Z[G], and any λ = e1,...,e k c e1,...,e k σ e1 1 • • • σ e k k we set

  Buchmann-Pohst algorithm, that we propose in Algorithm 4. Theorem 312 (adaptation to O K -lattices of Th 3.1 in [13]) Algorithm 4 is correct and terminates in O (k + m) 6 (m + log(D 1/m /µ)) operations on a classical computer. Proof. The proof is a verbatim translation of the correctness proof in the case of Z-lattices. By Equation 3.3, if b 1 , . . . , b m is a reduced basis of a lattice such that det L ≤ D, then max(∥b 1 ∥ , . . . , ∥b m ∥) ≤ B. This is used in the proof of [13, Prop 2.2] to show that the successive minima of the lattice generated by the columns Algorithm 4 Buchmann-Pohst over O K Input: a OK -lattice L ⊂ C m given by approximations g1, . . . , g k ∈ C m of g1, . . . , g k ∈ C m which OK -span L; a lower bound µ of λ1(L); an upper bound D on det L Output: approximations of a basis b1, . . . , bm over OK of L 1:

Theorem 43

 43 Algorithm 1 computes a basis of the unit group of Q(ζ m ) in poly(m) time and uses O(m 2 log m) qubits. Proof. The only quantum step of Algorithm 1 is the dual lattice sampler, whose parameters are δ = ∥B L ∥ /λ * 1 (L) and η = 1/k 2 where k = log 2 ( √ m Lip(f )) + log 2 (det L)) is given in step 1 of the algorithm. In this section m is not necessarily equal to the rank m ′ of Z[ζ] * but O(m ′ ) = O(m) so that we use m and m ′ interchangeably. By Lemma 32, the sampler used O(Qm) qubits with Q as below. We write a ≪ b for a = O(b). We use Th 36: log Lip(f ) ≪ m 2 +m log D and then k ≪ m 2 +m log D. We also use Lemma 42: log 1/(δλ * 1 (L)) ≪ log(1/ ∥B M ∥) ≪ log m and log D = (m -2) log m ≪ m log m.

w

  : {P ∈ R[x] | deg P ≤ n -1} → R n P → (P (α 1 ), . . . , P (α n )).Clearly, w is a linear isomorphism. Assume that disc(f ) is squarefree and then O K = Z[x]/P . We definef : R n → (R n [x] mod Z n [x]) × (R n [x] mod Z n [x]) (x 1 , . . . , x n ) → (w -1 (e x1, . . . , e xn ), w -1 (e -x1 , . . . , e -xn )) mod Z n [x] 2 .

  O(m 5 log m) qubits high degree CGP superpolynomial space isogenies

  Apply the Buchmann-Pohst algorithm on ( ỹ1, . . . , ỹk ) and obtain ( ỹ′

			19,
		Appendix B.3 Th 4]
	4:	pass	▷ compare to Algorithm 1
	5: end for
	6:

1 , . . . , ỹ′ m ) so that CVP( ỹi, L * )i=1,m is a basis of L * ▷ Step 2 -Classical 7: Output the rows of (B -1 ) t where B has rows ũ′ i . ▷ Step 3 -Classical

Table 1 :

 1 Classification of cryptographic primitives w.r.t. the resources of quantum attacks: factorization, discrete logarithms, elliptic curve (EC) discrete logarithms, class group of orders of imaginary quadratic fields (IQC), supersingular isogenies, lattices, error correction cryptosystems and class group (CGP) computations.

The norm operator used in the analysis of the Buchmann-Pohst algorithm[START_REF] Koen De Boer | On the quantum complexity of the continuous hidden subgroup problem[END_REF], Appendix B] is ∥•∥ ∞,1 .

The complexity of the CHSP solver depends on log 1/η and not on η itself. Hence the contribution of η is hidden in the Õ notation.

We used here a different proof than in[START_REF] Eisenträger | Long version of the submission to STOC 2014 for A quantum algorithm for computing the unit group of an arbitrary degree number field[END_REF] where one reduces the case of CHSP defined on arbitrary abelian groups to the case of CHSP over R m .

A similar speed-up was obtained in the case of Z[ζ k ]-LLL in [32]: an example took 20 s over Z[ζ k ] compared to 75 s over Z.

⋆ The first author has been funded by the Hybrid quantum initiative (HQI) of the France 2030 program.