Hanen Souissi
email: hanensouissi9@gmail.com

Leila Mejrissi

Hela Habli

Maarib Alsahhaf

Brahim Oujia

Xavier Florent

Gadéa

Ab initio diabatic and adiabatic calculation for the francium hydride FrH

Explicitly ab-initio diabatic and adiabatic calculations of potential energy curves (PECs) of the states 1,3 Ʃ + , 1,3 Π, and 1,3 Δ of francium hydride FrH have been carried out with several approaches. We determined for both representations, the Permanent and Transition Dipole Moment (PDM and TDM) and the vibrational levels. The calculation was based on the Configuration Interaction (CI) method, which includes the Effective Core Potentials (ECP) and Core Polarization Potentials (CPP). The FrH system is considered as an effective two-electron system, permitting calculation of structural and electronic properties with Full Configuration Interaction (FCI). For the diabatisation method, we perform an efficient diabatization approach, which depends on the variational effective Hamiltonian theory (VEH) and a dynamic overlap matrix. This work finishes the diabatic and adiabatic ab-initio spectroscopic investigations of all the alkali hydrides series. In addition, we present our adiabatic results of FrH by comparing it with the other alkali hydrides systems (Li-Cs)H. This study is essential for a wide range of theoretical and experimental work.

I-Introduction

Many theoretical l-24 and experimental 25-31 researchers have studied the alkali-metal hydrides for many years. The investigation of the chemistry compounds in the early universe and the resolution of the abundances of these compounds in stellar atmospheres needed a thorough understanding of the cross sections for many collisional processes 17 . For example, inelastic collisions between alkali-metal atoms (Li and Na) and hydrogen 32,33 , radiative charge transfer

between alkali-metal atoms and H +34 , neutralization collisions between H -and alkali ions 35,36 or dissociative recombination 37 . Adopting the ideas of ref. 38 concerning the manipulating molecules via combined laser and static fields, alkali-metal hydrides could be a beneficial for such experiments.

Interestingly, the francium is the heaviest alkali-metal atom. Further, the francium exists only thirty grams in the earth crust. It is the longest-lived isotope lasts only 20 minutes and it is the most unstable element of the first 103 in the periodic table. The francium gives a sensible test of the influence of Quantum and relativistic Electro-dynamic effects on the atomic composition 39 . In addition, the francium is also a very good compound for examining feeble interactions in atoms, for example atomic Parity Non-Conservation (PNC) [40][41][42] . One of the most important discoveries of the 1939s was the francium by Perey of the curie institute located in Paris by observing the β decay of 223 Fr in the natural actinium radioactive decay chain 43 . All its isotopes have short half-lives (maximum 21.8 min, for 223 Fr), that is why this element was the second-most rare natural compound on earth after astate 'At' [START_REF] Adolff | Francium (Atomic Number 87), the Last Discovered Natural Element[END_REF][45] . It was not until 1978 that the group guided by Sylvan Liberman at ISOLDE in CERN manage to find the D2 resonant line of the spectrum of Fr, leading the way for many spectroscopic investigations. Meanwhile, the evolution of tunable lasers had allowed the trapping and cooling of alkali atoms involving resonance light in combination with magnetic fields, indeed all the parts obligatory for cooling and trapping francium were there at Stony Brook in the early 1990s [START_REF] Adolff | Francium (Atomic Number 87), the Last Discovered Natural Element[END_REF] . Indeed, this rarity is due to its transient existence, as a decay product of actinium 46 . The main cause of the order of the francium of the least studied element is the experimental difficulties 40, 47 . The francium is never found outside nuclear facilities or research laboratories, being potentially dangerous because of its intense radioactivity and its natural occurrence in uranium mineral but at any one time, there is one francium atom per one billion atoms of uranium 48 . When the rats were injected with francium, it concentrated in the bladder, gut, kidneys, saliva and liver. In those rats with cancer, it also concentrated in the tumor, raising hopes that francium might have medical uses in treating this disease. For reasons given below, this was a forlorn hope 49 .

The topic of this work is to investigate the electronic, vibrational and dipolar electric properties for the francium hydride system including: (i) the PECS of several symmetries 1,3 Σ + , 1,3 Π, and 1,3 Δ and their spectroscopic constants (R e : Equilibrium distance, D e : Well depth, T e : Transition energies, ω e χ e : Anharmonic constant, ω e : vibrational constant and B e : rotational constant). (ii)

The vibrational properties. (iii) The PDM and TDM functions.

As we know that there are no previous experimental studies have yet been published for the FrH molecule and there is two theoretical adiabatic studies have been examined by Hill et al. 1 and Noro et al. 2 using the new correlation consistent (cc) basis sets. So, this method is based on Pseudo-Potential (PP) Hamiltonian, which is contracted from double to quintuple Zeta quality.

Moreover, for these alkali-metal, the Gaussian-type function sets have been contracted by application the two approach which are the exact 2-component (X2C) scalar relativistic Hamiltonians 50-55 and third-order Douglas-Kroll-Hess (DK3) approximation 56 . In addition, we compare our results with the other alkali hydrides systems (Li-Cs)H 3-7 . In 2006, Aymar et al. 49 have studied the electronic structure of Fr 2 , FrRb and FrCs molecules and their cations. Then, in 2008, J. Deiglmar et al. 57 have studied the Fr 2 molecule. These results are useful for further theoretical and experimental researches in spectroscopy or collision fields. This work is outlined as follows: Section II introduces our methodology based on ab-initio diabatic and adiabatic calculation. In Section III, we present the molecular diabatic and adiabatic PECs, their spectroscopic constants together and the vibrational level properties. In section IV, we give our numerical data of the permanent and transition dipole moments (PDM and TDM) for both representation. Section V contains the conclusions.

II-Ab inito calculations 1. Calculation Details

Many studies have focused on the electronic structure by using ab initio method of alkali-metal hydrides 3,7,13, 14 . In this calculation, the polarizable core of Fr + is substituted by a semi-empirical pseudo-potential put forward by Barthelat and Durand 58, 59 , completed by both approach Core Polarization Potentials and Effective Core Potentials. The semi-local form of the Fr core is taken from the paper studied by M. Aymar et al. 49 . In this framework, the electronic properties were investigated first at the Self-Consistent Field (SCF) based on Full Configuration Interaction (FCI) applicated the Toulouse package code 3-7, 13, 14, 60-79 . Moreover, the interaction between the polarizable core Fr + with the hydrogen nucleus and the valence electrons is treated using the core polarization potential V CPP given by Müller et al. 80 which is written as:

(1)

        f f V CPP ' 2 1
Where is the γ core's dipole polarizability and represents the electrostatic field proposed 𝛼 𝛾  f by the other cores on the γ and the valence electron:

(2)

     i c l i l i i R R Z R F R R f             ' ' 3 ' 3 ) , (
is the core-electron vector, the vector is the core-core and is the cut-off

i R   ' R ) , ( 1    i R F
operator corresponding to the operator expression of Foucault et al. 81 , which is written as follows:

(3) Furthermore, the cut-off radius is given by a function of (l) according to:

(4)         lm lm R F R F l l m i l i         0 1 ) , ( ) , (
is a spherical harmonic in the center of the γ core.

 lm  lm

In this framework, the core polarizability of the francium is taken from Ref. 82 where α Fr =20.38

. The optimized cut-off parameters are ρ s = 3.1629, ρ p = 3.027 and ρ d = 3.1068 Bohr.

3 0 a

To have a best representation of the atomic levels (7s, 7p, 6d, 8s, 8p, 7d, 9s and 9p) of the Fr atom, we optimized a large Gaussian-Type Orbital (GTO) basis set 8s/6p/5d (see Table S1 in the supporting information). While for the hydrogen atom, we have re-optimized the basis set studied by Zrafi et al. 7 to be (7s/3p/2d). Therefore, we have improved the variation between our result and the experimental one, which is less than 47 cm -1 for 1s level (see Table S2 in the supporting information).

Our selection of the basis set globally ameliorates the investigated francium atomic level energies compared with preceding works like the work of Aymar et al. 49 on the francium atom.

In Table S3, we display the atomic spectrum of Fr of our work and those of Aymar et al. 49 which are compared with the experimental ones [START_REF] Yu | Reader J and NIST ASD Team[END_REF] . The analysis of the experimental and our theoretical energies shows a good concordance between them [START_REF] Yu | Reader J and NIST ASD Team[END_REF] where the largest difference is 88 cm -1 . We display in Table S4, our energies of the asymptotic limits with the experimental ones, which dissociate bellow the ionic limit (Fr + + H -). This limit is described as IP Fr -EA H where IP Fr (=32848 cm -1 ) is the ionization potential of the francium and EA H (=6083 cm -1 ) is the electronic affinity of hydrogen. Our values are in very good accord with the experimental data. In addition, we can see in Table S4 that the relative errors between the experimental and theoretical energies do not exceed 0.094 %.

                 i i i R R R F ; 1 ; 0 ) , (

New Journal of Chemistry Accepted Manuscript

Diabatic Calculation Details

We used here the same method used for full alkali hydride series (LiH 3 , NaH 4 , KH 5 , RbH 6 , CsH 7 ), the alkaline earth hydride (CaH +65 ) and mixed alkali (KLi 70 and RbLi 72 ). The strategy of the diabatisation method is to determine theoretical approximation of the non-adiabatic coupling between the pertinent adiabatic states and to make it disappear by a suitable unitary transformation relative to Variational Effective Hamiltonian theory (VEH) [START_REF] Gadea | [END_REF] . In the actual performance of the VEH at each distance the target space (adiabatic states, Ψi) and the model space (reference states, ) need to be exactly defined now.

i 

The model space noted S 0 is crossed by n orthogonal vectors . The associated

{|𝑅 𝑖 〉, 𝑖 = 1,…𝑛}
projector is P o :

𝑃 𝑆 0 = 𝑃 0 = ∑ 𝑛 𝑖 = 1 |𝑅 𝑖 〉〈𝑅 𝑖 |
In this work we choose the large inter-atomic distance interval used in the adiabatic work where all inter-atomic interaction disappears.

The target space S is clearly formed by the "n" adiabatic functions "Ψi" at inter-atomic distance "R" and the projector "P":

𝑃 = ∑ 𝑛 𝑖 = 1 |𝛹 𝑖 〉〈𝛹 𝑖 |
Moreover, the projection matrix of the model space vectors on the target space is made unitary by symmetrical orthogonalization 13, 84-87 as in the des cloiseaux formulation of VEH approach.

First, we used an effective overlap matrix A that defined as following:

A ij = ⟨R i │P 0 Ψ j ⟩ = ⟨Ψ i │⟩
Then, the n diabatic states (D i ) are orthonormal linear combinations of the "n" adiabatic states, which the matrix formulation is written as:

, U ' U=𝟙 U ij = ⟨Ψ 𝑖 │D 𝑗 ⟩
Since the matrix diagonal of the electronic Hamiltonian (H) in the adiabatic representation be noted as: It is "de-diagonalised" in the diabatic representation where H is now written U ' E U.

E = ⟨ Ψ i │ H │ Ψ j ⟩ = E i δ ij (5) (6) (7)
As mentioned in the paper of Romero et al. 86 , in all dibatisation procedures, the interference between a molecular orbital at a specified point (named R) and another specified point (named R 0 ) plays a key role. Moreover, the overlap matrix A depends on the movement of the atoms when passing from R to R 0 . The choice of the lower half diagonal section from one distance and the superior section from the another distance for a diatomic molecule, related to fix the common origin of coordinates in one of the atoms precisely at the heavier and assuming a diagonal 𝟙 matrix in each of the diagonal blocks. In a way to reduce the remaining coupling between the quasi-diabatic states, from A the unitary adiabatic-diabatic transformation matrix U is making as:

U = A (A ′ A) - 1 2
The Hamiltonian "H" in the diabatic basis is obtained as:

⟨D│H│D⟩ = U ′ EU = (A ′ A) -1 2 A ′ E A (A ′ A) -1 2

III-Results and interpretation 1. Adiabatic and diabatic PECs and their Spectroscopic constants

In our study, we realize an adiabatic and diabatic calculation of the francium hydride by employing the pseudo-potential for the Fr core supplemented by CPP, ECP, FCI and the method of diabatisation. We investigated the PECs for various states of 1,3 Ʃ + , 1,3 Π, and 1,3 Δ symmetries beneath the ionic limit (Fr + + H -) for both representations. These curves are shown in Figures 1234567for a large number of grid points with R varying from 2.5 to 200 a.u. The PECS are investigated by FCI, which have been used to derive the spectroscopic constants of whole the states via Nvib program (The program is restricted to the harmonic expression of the vibrational problem (i.e. just the quadratic force field)). The obtained spectroscopic parameters are reported in Table 1.

Table 1. Spectroscopic constants for 1,3 Σ + , 1,3 Π and 1,3 Δ states of FrH.

States R e (a.u.) D e (cm -1 ) T e (cm -1 ) ω e (cm -1 ) ω e χ e (cm -1 ) B e (cm -1 ) The adiabatic PECS for the 1 Ʃ + molecular states of FrH are graphically depicted in Figure 1.

(a) 1 Σ + States X 1 Σ + A 1 Σ + C 1 Σ + 2 nd min D 1 Σ + 2 nd min E 1 Σ + 2
These curves have the same shape like those of LiH 3 , NaH 4 , KH 5 , RbH 6 and CsH 7 . Therefore, the potential well of the ground state was practically profound at a short inter-nuclear distance R e =4.43a.u, which has a depth D e =14041 cm -1 . The first excited state A 1 Σ + presents a flat potential well explained by the largeness of the avoided crossing between the repulsive section of the X 1 Σ + curve at the short distance and the attractive part of A 1 Σ + about R= 17 a.u. In addition, the next excited state (C 1 Σ + ), shows two minimum; the first is at about R= 5.65 a.u., and the second is at about R= 14.14 a.u., following the neutral-ionic avoided crossing with For the most excited states, we can note that the appearance of double and triple wells. We can see that the D, E and F states shows double minima: The first one at a short distance that could be corresponding to an avoided crossing between neutral-neutral states, and the second at large distance corresponding to the ionic-neutral states and only the G 1 Σ + have a triple minima.

A 1 Σ + . F 1 Σ + 2 nd min G 1 Σ + 2
(c) 1,3 Π States B 1 Π b 3 Π 1 1 Π 1 3 Π 2 1 Π 2 3 Π 3 1 Π 3 3 Π 6.

New Journal of Chemistry Accepted Manuscript

H 1   G 1   F 1   E 1   R (a.u.) Energy (a.u) D 1   C 1   A 1   X 1   Fr(9p)+H(
As far as we know, the theoretical values are obtainable only for the ground state studied by Hill and al. 1 and Noro et al. 2 . The MOLPRO procedure of ab initio programs was used for all computation in their works. As seen in Table 2, we have listed the two available theoretical spectroscopic constants, which are studied with a different basis. Notably, our results correlate with Hill et al. 1 data for the basis of cc-pV5Z-PP for D e , where the difference less than 75cm -1 .

Moreover, we can see that the equilibrium distances R e got by Noro et al. 2 for the basis of wCVQZ-DK3 is larger than our results around 0.4 a.u. We list in Table 3 the positions of some avoided crossings, which were located in the PECS with the corresponding main energy difference for the FrH. Similarly to the alkali hydrides series 3-7 , these crossings corresponding to the excitation or charge transfer efficiency between the Fr and H atoms and the presence of numerous avoided crossings at a short and a long distance come from the unusual undulating behavior of (-1/R). In this framework, these crossings are accountable for the particular behaviors of PECs such as the presence of multiple wells as for G 1 Σ + and the appearance of a wave feature in PECs. We plotted the PECS for the ground state X 1 Σ + for all the alkali-metal hydrides XH systems (where X=Li, Na, Cs, Rb, and Fr) that are given in Figure 2, which are similar to the origin of energies attached to the limit X+H(1s). In addition, their spectroscopic constants are presented in Table 4 with the accessible work found in the litterature 16, 88, 89 . As we can see in Figure 2 and Table 4, the profound wells are corresponding to the LiH Note that for alkali metal atoms (Li-Cs), the smaller ionization potential (43 487, 41 449, 35 009, 33 691, and 31 406 cm -1 ) is related to the heavier alkali atom and has the larger electron affinity (experimental values are 4984, 4403, 4043, 3920 and 3803 cm -1 for Li, Na, K, Rb and Cs, respectively 90 ). Whereas, the ionization potential IP (Fr) = 32 848 cm -1 exceeds the IP(Cs) by 1442 cm -1 and the EA (Fr) 91 = 3678 cm -1 (see also 92 ) is larger by only 117 cm -1 than the one of Cs, nearly half-way between IP (Cs) and IP (Rb). Clearly, the mean error for the ionization potentials is 9 cm -1 and for excitation energies 20 cm -1 . Especially for the heavier atoms, the electron affinities are less accurate, with errors from 4 to 9% for K, Rb, and Cs 90 .

New Journal of Chemistry Accepted Manuscript

The PECS for all the 1 Σ + states of the francium hydride have the same shape with the other alkali-metal hydrides (Li-Cs) H 3-7 .

In Figure 3, we have drawn the adiabatic potential curves for the eight 3 Σ + states into the ionic limit Fr + +H -. The first state a 3 Σ + presents a shallow well at a remarkable large distance (R e =10.63 a.u.), while the higher states (c, d, e and f) 3 Σ + show two minima, the first one is between R= 5 a.u and 6

a.u, the other one at large distance has as origin the existence of the ionic-neutral avoided crossing. The different avoided crossing positions are given in see an avoided crossing between f 3 Σ + and g 3 Σ + states at R e =6.9 a.u. which explains the appearance of the double well depth for the f 3 Σ + state.

Moving to the diabatic representation, we have displayed in Figures 4 and5 the diabatic PECs for the 1,3 Σ + states, which are named as D 1-9 and d 1-8 , respectively. As we can see in Figure 5, the diabatic PECs of the 3 Σ + states have the same interpretation of the diabatic PECs of the 1 Σ + states. We note that the first diabatic ionic curve d 1 (Fr + H -) has a well depth at the distance R= 10.8 a.u. and crosses the states 7p, 6d, 8s, 8p and 7d at about 8 a.u, 7.5 a.u, 6.8 a.u, 6.8 a.u and 6 a.u, respectively. As mentioned in the alkali hydride series 1-5 , we found that the interaction of the singlet states is strong with the possible charge transfer states, which are usually not present in triplet states. Furthermore, we can see that the lower 3 Σ + diabatic states present a strong repulsive behavior at short distances like for 1 Σ + ones. We note that, we observe the diabatic crossings between two successive states of 3 Σ + like d 1 -d 2 are almost the same positions than the related 1 Σ + ones.

1.2.

The symmetries 1,3 Π and 1,3 Δ For Π symmetry, the adiabatic PECS of 10 1,3 Π for the francium hydride are presented in Figure 6 and their spectroscopic constants are displayed in Table 1 (c). Like for alkali-metal hydride 1-5 , the 3 Π potential energy curves are a little deeper than 1 Π ones. Indeed, these states reach speedily to their asymptotic limit at around R=20a.u. Moreover, the 1 Concerning the Δ symmetry, we have graphed the PECS of 1,3 Δ states in Figure S1 (Supporting Information) and their spectroscopic parameters are listed in Table 1

(d).

As usually observed for alkali-metal hydride 3-7 , the 1 Δ and 3 Δ PECS, which tend rapidly to the same limit, are nearly degenerated. Obviously, the first states 1 1,3 Δ have roughly the same value of the potential depth (De 1 = 460cm -1 and De 2 = 471 cm -1 for 1 1 Δ and 1 3 Δ, respectively).

We have drawn in the diabatic representation the PEC S for the symmetries 1,3 Π in Figures 7 and for nearly avoided crossing in the adiabatic PEC S . To sum up, the diabatic curves have not a strong variation for the adiabatic one.

Adiabatic and diabatic electric dipole moments

2.1.

Adiabatic and diabatic Permanent Dipole Moment

The adiabatic PDM from the symmetries 1,3 Σ + , 1,3 Π are reported in the slopes around the crux of the dipole. Whereas, we have seen the same behavior in the other alkali-metal hydride series 3-7 whether, the avoided crossings in the potential energies curves and the crossings in the PDM figures were produced by the ionic curve.

  F 1   E 1   Permanent Dipole Moment (a.u.) R (u.a) D 1   C 1   H 1   G 1   F 1   E 1   Permanent Dipole Moment (a.u.) R (a.u) D 1   Figure 8.
Permanent dipole moment for the 1 Σ + states for the FrH with zoom for the PDM at short distance.

The important consequences of these crossings concern the efficiency of the charge transfer or the excitation, for instance, neutralization cross sections essentially relied on these crossing series, therefore, their important field for charge transfers in many astrophysical conditions 31, 93-95 . This physical property has been shown in the alkali hydride series in the same symmetries 3-

7

.

The Permanent Dipole Moment figures for 3 Σ + , 1,3 Π and 1,3 Δ are shown in Figures 9 and10.

Let us begin by the PDM curves for 3 Σ + symmetry; Figure 9 indicates the significant variations at short distances before 20a.u. These functions are not negligible and have considerable influence on higher excited states.

New Journal of Chemistry Accepted Manuscript

Permanent Dipole Moment (a.u.) Then, they increase and vanish at a large distance. For instance, h 3 Σ + and g 3 Σ + states present maxima (μ max = -11.58a.u. and -3.73a.u.) respectively, at the distance R= 5.9 a.u. and 13.5a.u, respectively. Then it slowly decreases. These positions correspond to the avoided crossing in their potential energies curves. The PDM curves of symmetry 1,3 Π show an important variation at short distances and tend rapidly to zero (see Figure 10). Permanent Dipole Moment (a.u.)

2   B         1   1   b   Figure 10
. Permanent dipole moment for the 1,3 Π states for the FrH.

In the Supporting Information (Figure S3), we observe that PDM functions of 1 Δ are identical to the 3 Δ ones, which explains the degeneracy in their PECs.

Concerning the diabatic representation, the curves of the PDM are displayed in Figures 11 and 12 for 1,3 Σ + states. As shown for the all alkali hydride series (LiH, NaH, KH, RbH and CsH) 3-7 , the diabatic PDM curves allow important information on these molecules. As we can see in Figure 11, we obtain a straight line, while the neutral diabatic dipole of the states decreases rapidly to zero when R increases. Interestingly, this simple shape reflecting the physics expected for the PDM of the various diabatic states is in uniformity with basic electrostatic considerations and gives strong support to the diabatisation method used.

Adiabatic and diabatic TDM

It is attractive to exemplify the curves of the TDM in the adiabatic and diabatic representations, which help us to make the information for future photo-association experiments. The adiabatic curves have been presented in the Figures 12 and13 for 1 Σ + and 3 Σ + , respectively, and they have been investigated for the first time.

G 1   H 1   F 1   G 1   E 1   F 1   D 1   E 1   C 1   D 1   C 1   E 1   A 1   C 1   X 1   A 1   R (a.u)
Transition Dipole Moment (a.u) We observe in the Figures 12 many peaks that are corresponding to the avoided crossings in the PECS at these distances. To explain more, the D-E TDM present a peak around 30 a.u.

which corresponds to the avoided crossing between D and E electronic states. In addition, the large peak is detected for the E-F TDM curves, which correspond to the crossing of the E-F PECS at the distance 60 a.u. Interestingly, when the peak is higher and less wide, the avoided crossing was less compared to the A-C case. Similarly, the same remark is found in the work of the other alkali-metal hydride 3-7 . We have also conveyed in Figures 13 and 14 the TDM curves for symmetry 1,3 Σ + . Noteworthy, most of the TDM curves do not have a peak, which is related to the repulsive shape in their PECS and the lack of the avoided crossing. Furthermore, the (g-h) 3 Σ + present clearly a peak at R= 6.9 a.u, which corresponds to the position of the avoided crossing between g and h states in their PECS. In general, the corresponding avoided crossings in the PECs are then displayed around the large internuclear distances and the related maximum values in the TDM functions. Moreover, the most significant transitions which are between two successive states, for example, the transitions between (F-G) 1 Σ + and (G-H) 1 Σ + states are more important than the others.

New Journal of Chemistry Accepted Manuscript

Indeed, for the first time, we have investigated the diabatic curves of the TDM for the first state 1 Σ + , which are showed in Figures S4 (Supporting Information). Furthermore, the diabatic curves show smoother variations of their physical characteristics at a short inter-nuclear distance while the adiabatic states present strong variations; it is difficult to pursue their physical acumen with a very limited number of states. As mention before, the avoided crossing in the adiabatic curves can be showed as peaks in their curves of TDM.

At large distances, the diabatic representation drops to zero and does not have any variation, while, in the adiabatic representation their variation continue to R=60 a.u.

Vibrational levels of FrH

In this section, we have studied the spacing of the vibrational level for 1,3 Σ + , 1,3 Π and 1,3 Δ symmetries, for the first time. We have interpolated the vibrational levels by least-squares method (Numerov Program), which is written as following:

2 ) 2 1 ( ) 2 1 ( ) (      v v R V E e e e e v

  

The NUMEROV program is prepared to determine the spectroscopic constants ω e and ω e χ e from vibrational energy levels G v . The equilibrium distance R e and B e are deduced at the minimum of the V(R) potential. Since the vibrational wave functions can be calculated at the (12) same moment for the two different electronic states, we can also get the quantities to represent the vibronic transition like an oscillator strength.

As shown in Figure 15, the adiabatic PECS for the (X, C, D) 1 Σ + and their vibrational levels are plotted with their spacing's (G ʋ -G ʋ-1 ) awarding to the vibrational levels' number ʋ. Therefore, X 1 Σ + shows a deep potential well, which contains 27 vibrational levels. For the first vibrational levels, we observe a linear behavior reflecting an anharmonic form like Morse in their PECS. The spacing's become smaller and disappear at the dissociation limit (Fr (7s) + H(1s)). The same remark is applicable to the states that have a single well depth. The spacing for the C 1 Σ + shows a sudden variation that indicates the presence of a second well. Then, we can see a slow variation from ʋ=3 to ʋ=5 considering that the second well is wider. It is worth noting that, accidental quasi-degeneracy appears one time (ʋ= 4, 5) and related to states, which are suitable to different wells. The D 1 Σ + state has 41 vibrational levels which begin with an abrupt behavior up to ʋ=29 then, a sudden change emerges from ʋ=30 to ʋ=33 reflecting a second wide anharmonic well.

In Figure 16, we have traced the vibrational level spacing for the other states of symmetries

G 1   F 1   E 1   v G v -G v-1 (cm -1 )
Figure 16. Vibrational level spacing for (E, F and G) 1 Σ + states of FrH.

We listed in Table 5 and 6, the vibrational levels for other states of 3 Σ + , 1,3 Π and 1,3 Δ symmetries, which have a fewer vibrational level number. Therefore, that is explained by the repulsive shape in their potential curves. The most of these spacings are constant and linear;

this is correlated with the anharmonicity of the potential wells. As we can see in Table 5, the vibrational level of symmetry 3 Σ + does not exceed eight levels and shows a linear behavior that is reflected the simple wells in their PECs. The same analysis for the symmetries 1,3 Π and 1,3 Δ (see Table 6). More clearly, the vibrational levels of 1 Δ are roughly identical to the one for 3 Δ that is related to the degeneracy in their PECs. In summary, the spacing vibrational levels are investigated here for the first time for all symmetries and present important information considering the shape of the PECS.

New Journal of Chemistry Accepted Manuscript

Table 6. Vibrational-Level Spacing (G v+1 -G v ) of 1.3 Π and 1.3 Δstates (in cm -1 ).

V B 1 Π 1 1 Π 2 1 Π 3 1 Π b 3 Π 1 3 Π 2 3 Π 3 3 Π 1 1 Δ 1 3 Δ 2 1 Δ 2 3 Δ 1

IV Conclusion

This study is an investigation of the diabatic and adiabatic electronic properties of FrH molecule, including PECs for all symmetries 1,3 Σ + , 1,3 Π and 1,3 Δ, vibrational level spacing and the PDM and the TDM functions. The adiabatic calculation method is carried out in the Born-Oppenheimer approximation. The pseudo-potentials and the Full Configuration Interaction methods are applied here. Moreover, we have studied a diabatic study for this molecule FrH using the theory of the variational effective Hamiltonian combined to an active overlap matrix.

The most striking result to emerge from the data is that the 1 Σ + states show a significant series of avoided crossing. We observe that the highly potential part is related to the Fr + +H -ionic state similarly to the XH systems where X= Li, Na, K, Rb, Cs 3-7 . These curves have the same behavior with the PECS of the other alkali-metal hydride. The PECs for the 1,3 Π symmetries present a similar shape and for 1 Δ and 3 Δ are roughly identical.

The diabatic survey produces huge acumen into the strong interactions between the adiabatic states. From our results, we can see the ionic-neutral crossings at intermediate and large distances, exactly in the 1 Σ + states. Moreover, the PDM functions show the appearance of (-R) curve for the ionic limit (Fr + +H -). The various crossings in PECs result from the unusual shapes with multiplicity wells that are related to the linear behavior in PDM curves and the peaks in TDM curves. More clearly, the PDM curves reproduce by piece the (-R) function like a linear behavior of the ionic state (Fr + +H -) and pass through forming nodes between successive pieces when combined. The important consequences of these crossings are for the photo-association and spontaneous emission or the radiative charge exchange 31, 94 . In fact, the PDM functions give a direct explanation of the ionic character of the electronic wave function for FrH. These new results are very important for further theoretical and experimental researches, for example in spectroscopy 96 or collision 97-101 fields.

These diabatic results can be applied to calculate the vibronic shifts and radiatives as well as non-radiative lifetimes 102-110 . In addition, inelastic collision cross sections studies could be made for instance for the process of charge transfer, which can be interesting for many fields in physics or maybe in astrophysics.

New Journal of Chemistry Accepted Manuscript

Published on 24

 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM. View Article Online DOI: 10.1039/C9NJ06391A

9 )

 9 New Journal of Chemistry Accepted ManuscriptPublished on 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM.

Published on 24

 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM.

Figure 1 .

 1 Figure 1. Adiabatic PECs 1 Σ + dissociating below the ionic limit Fr + + H -.

Published on 24

 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM. View Article Online DOI: 10.1039/C9NJ06391A

1 and NaH 2 Figure 2 .

 22 Figure 2. X 1 Σ + adiabatic potential energy curves for XH (X= Li, Na, K, Rb, Cs and Fr).

Figure 3 .

 3 Figure 3. Eight adiabatic 3 Σ + potential energy curves for the FrH molecule.

Figure. 4 .

 4 Figure.4. Diabatic 1 Σ + potential energy curves dissociating below the ionic limit Fr + H -.

Figure. 5 .

 5 Figure.5. Diabatic 3 Σ + potential energy curves dissociating below the ionic limit Fr + H -.

Figure 6 . 1 , 3 Π

 613 Figure 6. 1,3 Π adiabatic potential energy curves for the FrH molecule.

the 1 , 3 Δ

 13 symmetry in Figure S2 (Supporting Information). Interestingly, the Singlet and Triplet states of Π and Δ symmetries are practically degenerate. As we can see in the

Figures 6 -

 6 Figures 6-7 and S1-S2, the curves of Π and Δ symmetries show smooth variations and are quite similar in their behavior. However, we observe that the wells of the diabatic representation are somewhat less deep than the adiabatic ones. There are no avoided crossing that can be seen in the adiabatic PEC S , which is related to the small non-adiabatic interaction. Except for the first diabatic state of the Π symmetry crosses the second at around R= 5 a.u. is because of the

Figure. 7 .

 7 Figure.7. Diabatic 1,3 Π potential energy curves dissociating below the ionic limit Fr + H -.

Figures 8 -

 8 10 and for1,3 Δ Symmetry in FigureS3(Supporting Information). In fact, the PDM gives a direct picture of the ionic character in 1 Σ + of the electronic wave function. This physical property has been shown in the alkali hydride series in the same symmetries [1-5]. Taken the work of the calcium hydride ion (CaH + )65 , the comportment of their PDM significantly can be a support for the identification of the various adiabatic electronic states below Ca 2+ +H -and Ba 2+ +H -, respectively. As we can see in Figure8, the PDM functions of 1 Σ + states vary slowly at the short internuclear distances, which is shown in the zoom of this figure whereas at large distances, they present abrupt variations. We notice that one after one; each adiabatic state leads to a maximum and after that drops to zero. In addition, these curves reproduce by piece the (-R) function like a linear behavior of the ionic state (Fr + +H -) and pass through forming nodes between successive pieces when combined. Moreover, the avoided crossings are very weak that explain the sharpness ofNew Journal of Chemistry Accepted ManuscriptPublished on 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM. View Article Online DOI: 10.1039/C9NJ06391A

Published on 24

 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM.

Figure 9 .

 9 Figure 9. Permanent dipole moment for 3 Σ + as a function of the internuclear distance for the FrH.

Figure. 11 .

 11 Figure.11. Permanent dipole moment for the 1 Σ + diabatic states of FrH.

Figure. 12 .

 12 Figure.12. Permanent Dipole Moment for 3 Σ + diabatic states of FrH.

Figure 13 .

 13 Figure 13. Transition dipole moment for selected excited states for symmetry 1 Σ + .

Published on 24 Figure 14 .

 2414 Figure 14. Transition dipole moment for selected excited states for symmetry 3 Σ + .

Figure 15 .

 15 Figure 15. Vibrational spacing (left) and potential energy curves (right) for (X, C and D) 1 Σ + states of FrH.

Published on 24

 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM. View Article Online DOI: 10.1039/C9NJ06391A New Journal of Chemistry Accepted Manuscript Published on 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM. View Article Online DOI: 10.1039/C9NJ06391A

New Journal of Chemistry Accepted Manuscript Published

  on 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM.

							View Article Online
							(10)
							(11)
		4.43	14041	0	802	1.34	0.31
		7.31	9842	19572	211	4.04	0.07
		5.65	2566	28433	47	1.34	0.01
		14.14	2278	_	_	_	_
		6.06	588	34197	94	0.74	0.03
		18.07	3214	_	_	_	_
		5.76	1302	37156	22	0.80	0.01
	nd min	14.32	3383	_	_	_	_

DOI: 10.1039/C9NJ06391A 1.1. 1 Ʃ + Symmetry

Table 2 .

 2 Main spectroscopic constant for the ground state of the molecules FrH.

	Basis sets	R e (a.u.)	D e (cm -1 )	ω e (cm -1 )
	This work	4.43	14041	802
	Dzp 1	4.943	-	833
	Tzp 1	4.858	-	902
	Qzp 1	4.849	-	901
	cc-pVDZ-PP 1	5.157	11171	811
	cc-pVTZ-PP 1	5.119	13378	836
	cc-pVQZ-PP 1	5.128	13955	833
	cc-pV5Z-PP 1	5.134	14116	828
	CBS 1	5.142	14228	823
	wCVDZ-DK3 2	4.941	10710	846
	wCVTZ-DK3 2	4.854	12892	885
	wCVQZ-DK3 2	4.840	13455	893

Table 3 .

 3 Avoided crossing positions and energy difference between two states.

	States	Positions (a.u.)	ΔE (cm -1 )
	X 1 Σ + / A 1 Σ +	10.5	6575.5
	A 1 Σ + / C 1 Σ +	17	1512.18
	C 1 Σ + / D 1 Σ +	21	531.57
	D 1 Σ + / E 1 Σ +	10.5/29.5	2558.20/219.40
	E 1 Σ + / F 1 Σ +	9/60	425.78/12.07
	F 1 Σ + / G 1 Σ +	8.3/81.5	302.22/63.36
	G 1 Σ + / H 1 Σ +	15.5	1799.033
	d 3 Σ + / e 3 Σ +	7.5	1437.12
	e 3 Σ + / f 3 Σ +	8.3	2958.29

New Journal of Chemistry Accepted Manuscript Published

  on 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM.

	f 3 Σ + / g 3 Σ +	6.9	277.85	View Article Online DOI: 10.1039/C9NJ06391A
	g 3 Σ + / h 3 Σ +	5.9	426.66

Table 4 .

 4 Main spectroscopic constant for the ground state of the XH molecules (X= Li, Na, K, Rb, Cs and Fr).

	Molecules	References	R e (u.a.)	D e (cm -1 )
	LiH	Ref 3 Ref 17	3.003 3.002	20350 20167
		Ref 4	3.507	15489
	NaH	Ref 88	3.572	15970±403
		Ref 17	3.54	15671
		Ref 5	4.19	14365
	KH	Ref 88	4.265	14776
		Ref 17	4.168	14500
		Ref 6	4.40	13940
	RbH	Ref 88	4.53	14599±565
		Ref 17	4.395	14099
		Ref 7	4.47	14 879
		Ref 88	4.78	14809
	CsH	Ref 16	4.7	15083
		Ref 90	4.71	14791
		Ref 17	4.464	15019
	FrH	This work	4.43	14041

Table 3 .

 3 As an example, we can

New Journal of Chemistry Accepted Manuscript Published

  on 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM.

	View Article Online
	DOI: 10.1039/C9NJ06391A

Journal of Chemistry Accepted Manuscript Published

  on 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM. about 5.15 a.u and the potential depth De equals to 1620 cm -1 . It should be noted that all the states of Π symmetry have a single well depth.

	View Article Online
	DOI: 10.1039/C9NJ06391A

3

Π have the deepest well New at

  Published on 24 February 2020. Downloaded by LA TROBE UNIVERSITY on 2/25/2020 9:12:46 PM.

	View Article Online
	DOI: 10.1039/C9NJ06391A

Table 5 .

 5 Vibrational level spacing (G v+1 -G v ) of (a, c, f, h and I) 3 Σ + states (in cm -1 ).

	V	a 3 Σ +	c 3 Σ +		f 3 Σ +		h 3 Σ +	i 3 Σ +
		Energy	Spacing	Energy	Spacing	Energy	Spacing	Energy	Spacing	Energy	Spacing
	0	-89.99		-18.56		-482.68		-439.75		-585.79
	1	-51.45	38.54	-5.02	13.54	-288.90	193.78 -251.17 188.58 -397.58 188.21
	2	-20.45	30.99	-0.40	4.62	-162.70	126.2	-130.91 120.26 -245.11 152.47
	3	-8.06	12.4			-74.53	88.17	-69.31	61.6	-128.77 116.34
	4	-1.63	6.43			-12.01	62.52	-43.22	26.08	-45.79	82.99
	5							-15.67	27.56	-11.17	34.62
	6									-0.82	10.35
	7									14.48	15.3
	8									31.44	16.96

  143.14 105.71 153.21 152.23 184.66 270.24 164.22 177.01 136.38 138.73 152.87 153.71

	2	113.25 73.01	121.01 120.47 156.93 258.03 131.41 135.66 100.79 103.35 120	120.02
	3	81.69	46.98	87.54	88.87	119.05 235.04 93.86	92.15	69.37	70.54	85.38	85.5
	4	56.7	24.32	60.61	61.63	86.34	203.64 62.31	62.64	41.72	43.05	57.42	57.46
	5	34.8	11.87	35.38	33.13	59.26	170.79 39.67	42.87	20.95	21.74	31.85	32.01
	6	21.09		19.34	16.71	34.76	135.57 23.13	30.41	11.05	11.53	18.36	18.42
	7	10.27				18.46	101.88 12.55	22.89
	8					10.42	67.21
	9						24.82
	10						12.79

Acknowledgments

This research was funded by the Deanship of Scientific Research at Princess Nourah Bint Abdulrahman University through the research The Fast-track Research Funding Program.

New Journal of Chemistry Accepted Manuscript

Published on 24


Andreas Enge
email: enge@lix.polytechnique.fr

THE COMPLEXITY OF CLASS POLYNOMIAL COMPUTATION VIA FLOATING POINT APPROXIMATIONS

Keywords:

We analyse the complexity of computing class polynomials, that are an important ingredient for CM constructions of elliptic curves, via complex floating point approximations of their roots. The heart of the algorithm is the evaluation of modular functions in several arguments. The fastest one of the presented approaches uses a technique devised by Dupont to evaluate modular functions by Newton iterations on an expression involving the arithmetic-geometric mean. Under the heuristic assumption, justified by experiments, that the correctness of the result is not perturbed by rounding errors, the algorithm runs in time

for any ε > 0, where D is the CM discriminant, h is the degree of the class polynomial and M (n) is the time needed to multiply two n-bit numbers. Up to logarithmic factors, this running time matches the size of the constructed polynomials. The estimate also relies on a new result concerning the complexity of enumerating the class group of an imaginary quadratic order and on a rigorously proven upper bound for the height of class polynomials.

Motivation and results

The theory of complex multiplication yields an efficient approach to the construction of elliptic curves over a finite field having a given endomorphism ring of discriminant D, as long as |D| is not too large. Exploiting the link between the endomorphism ring of an elliptic curve and its number of points, it is possible to efficiently obtain curves with specific properties. Applications include primality proving [START_REF] Atkin | Elliptic curves and primality proving[END_REF], the construction of classical, discrete logarithm based elliptic curve cryptosystems and of identity based cryptosystems [START_REF] Miyaji | New explicit conditions of elliptic curve traces for FR-reduction[END_REF][START_REF] Dupont | Building curves with arbitrary small MOV degree over finite prime fields[END_REF][START_REF] Paulo | Constructing elliptic curves with prescribed embedding degrees[END_REF][START_REF] Brezing | Elliptic curves suitable for pairing based cryptography[END_REF].

The classical approach to effective complex multiplication is to compute minimal polynomials of special, algebraic values of modular functions on the upper complex halfplane (more details are provided in Section 2). The complexity of this algorithm remains a shady issue; one of the reasons a serious analysis has not been undertaken so far are the purported numerical difficulties with the computations with complex floating point numbers, an issue that actually does not arise in practice (cf. the short discussion at the end of Section 7).

In [START_REF] Couveignes | Action of modular correspondences around CM points, Algorithmic Number Theory -ANTS-V[END_REF] the authors present an algebraic generalisation of the complex multiplication algorithms to p-adic fields, that yields the same minimal polynomials. Besides ruling out any possible numerical instabilities, they obtain a complexity of O(|D| 1+ε ), which is better than a straightforward implementation of the complex approach, and asymptotically optimal (up to logarithmic factors) due to the size of the constructed objects.

The present article thus has two goals. First, it provides an accurate account of the complexity of different algorithms for class polynomial computation via floating point approximations. Second, it shows that asymptotically optimal algorithms exist also in the complex setting, with a complexity that is linear (up to logarithmic factors) in the output size. These new algorithms are presented in Sections 6.3 and 6.4, and the faster one achieves the following: Theorem 1.1. Let f be a fixed modular function that is a class invariant for a family of discriminants D of class numbers h = h(D). Then the algorithm of Section 6.4, which computes a floating point approximation to the class polynomial for f , runs in time O h(log 2 h + log n) M (n)

when executed with complex floating point numbers of n = n(D) bits precision, where M (n) is the time needed to multiply two such numbers as detailed in Section 3.1.

The floating point precision n required to carry out the computations is clearly bounded from below by the height of the class polynomial. The following theorem provides a rigorously proven upper bound on the heights, that is close to experimental findings. A bound of the same shape is given in [1, §3.3] as a heuristic, and the gist of the proof appears already in [34, §5.10] and [START_REF] Schoof | The exponents of the groups of points on the reductions of an elliptic curve, Arithmetic Algebraic Geometry[END_REF]Section 2]. In practice, one observes that rounding errors do not disturb the result. It suffices to take n as an approximation of the height plus a few guard digits to be able to round the floating point approximation of the class polynomial to the correct polynomial with integral coefficients. A rigorous error analysis, however, appears to be out of reach. So Theorems 1.1 and 1.2 can be brought together only in the form of a heuristic, assuming that the computations with floating point numbers of n bits yield an approximation of the class polynomial that is correct on essentially n bits.

O |D| log 3 |D| M |D| log 2 |D| ⊆ O |D| log 6+ε |D| ⊆ O h 2+ε
for any ε > 0.

Notice that up to logarithmic factors, this complexity corresponds to the output size of the algorithm, namely the size of the class polynomials. Notice also that the correctness of the output can be verified by a probabilistic, Monte-Carlo type algorithm; namely one may check that the reductions of the class polynomial modulo sufficiently many suitable primes p yield elliptic curves over F p with complex multiplication by O D . Indeed, the main application of class polynomials is to compute elliptic curves over finite fields with given complex multiplication, and in this situation it can be verified independently that the curves are correct.

As an ingredient for the proof of Theorem 1.1 we obtain in Section 5 the following result for computing class groups of imaginary quadratic orders: • under GRH by a deterministic algorithm in time

O (h log log |D|M (log |D|)) .
Again the algorithm is essentially optimal in its output size.

Complex multiplication and class polynomials

2.1. The basic approach. For proofs of the following facts on complex multiplication of elliptic curves see, for instance, [START_REF] Cox | Primes of the form x 2 + ny 2 -Fermat, class field theory, and complex multiplication[END_REF].

Let us first consider the situation over the complex numbers. Let D < 0 be an imaginary quadratic discriminant, and

O D = 1, D+ √ D 2 Z the (not necessarily maximal) order of discriminant D in K = Q( √ D). The ideal class number of O D is denoted by h = h D . By Siegel's theorem [42], log h log |D| → 1 2 (|D| → ∞), so that |D| ∈ O(h 2+ε ) and h ∈ O(|D| 1/2+ε
) for any ε > 0. There are h isomorphism classes of elliptic curves over C having complex multiplication by O D , that is, curves with O D as endomorphism ring. Namely, let j : H = {z ∈ C : ℑ(z) > 0} → C denote the absolute modular invariant, and let

τ i = -Bi+ √ D 2Ai run through the roots in H of the reduced quadratic forms [A i , B i , C i ] = A i X 2 + B i X + C i of discriminant D = B 2 i -4A i C i ,
representing the ideal classes of O D ; then the jinvariants of the elliptic curves are given by the j(τ i ). Moreover, these j(τ i ) are algebraic integers; in fact, they generate the so-called ring class field K D for O D , the Galois extension of K whose Galois group is isomorphic to the class group of O D (the isomorphism being given by the Artin map). The minimal polynomial of the j(τ i ) over K, H D (X) = h i=1 (X -j(τ i )), has in fact coefficients in Z and is called a class polynomial. In the special case that D is a fundamental discriminant, the ring class field K D is also called the Hilbert class field of K.

Let now F q = F p m be a finite field of characteristic p. Suppose that p splits in K = Q( √ D) and that p ∤ D; then p is unramified in K D . If furthermore q may be written as 4q = U 2 + DV 2 with U , V ∈ Z, then the inertia degree of the prime ideals above p in K D divides m. The reductions of the complex elliptic curves with complex multiplication by O D modulo any of these prime ideals thus live in F q . By Deuring's reduction and lifting theorems [START_REF] Deuring | Die Typen der Multiplikatorenringe elliptischer Funktionenkörper[END_REF]Einleitung,par. 5], these h curves are precisely the elliptic curves over F q with complex multiplication by O D . They may be obtained as follows: Compute the class polynomial H D ∈ Z[X] and reduce it modulo p. It splits completely over F q , and each of its roots is the j-invariant of an elliptic curve over F q with the desired endomorphism ring.

Class invariants.

Unfortunately, H D has very large coefficients (see the discussion in Section 4), so that its computation requires a high precision to be accurate. In practice, one may often gain a constant factor for the required number of digits by using instead of j modular functions f that are invariant under Γ 0

(N ) = a b c d ∈ Sl 2 (Z) : N |b for some positive integer N ; that is, f az+b cz+d = f (z)
for any such matrix a b c d . Under suitable conditions on the discriminant D and suitable normalisations of the τ i , derived from Shimura's reciprocity law, the singular values f (τ i ) are still elements of the class field K D [START_REF] Schertz | Die singulären Werte der Weberschen Funktionen f, f 1 , f 2 , γ 2 , γ 3[END_REF][START_REF] Gee | Class invariants by Shimura's reciprocity law[END_REF][START_REF] Gee | Generating class fields using Shimura reciprocity, Algorithmic Number Theory -ANTS-III[END_REF][START_REF]Weber's class invariants revisited[END_REF]; we then call f a class invariant and the minimal polynomial

H D [f ](X) = h i=1 (X -f (τ i ))
again a class polynomial. The first such class invariants are given by Weber's functions f, f 1 , f 2 , γ 2 and γ 3 [START_REF] Weber | Elliptische Funktionen und algebraische Zahlen[END_REF].

Two parameterised families of class invariants are exhibited in [START_REF] Enge | Constructing elliptic curves over finite fields using double eta-quotients[END_REF], where N is the product of two primes and

H D [f ] ∈ Z[X]
, and [START_REF]Further investigations of the generalised Weber functions[END_REF], where N is prime and H D [f ] has coefficients in the maximal order of Q( √ D). Again, these class polynomials split completely after reduction in F q . The corresponding elliptic curves may be recovered from some polynomial relationship between f and j: If the modular curve X 0 (N ) has genus 0, then j is sometimes given by a rational formula in f ; otherwise it has been suggested in [START_REF] Enge | Constructing elliptic curves over finite fields using double eta-quotients[END_REF] to look for a root of the modular polynomial Φ(f, j) after reducing modulo p and specialising in the value found for f in F q . (Both cases require that all coefficients be rational to make sense modulo p, which holds for all exhibited class invariants.)

Complexity of arithmetics

This section discusses the well-known complexity of the basic multiprecision and polynomial arithmetic underlying the computations.

3.1. Multiprecision floating point arithmetic. Let M (n) be the bit complexity of multiplying two n-bit integers. Using Schönhage-Strassen multiplication [START_REF] Schönhage | Schnelle Multiplikation großer Zahlen[END_REF], one has M (n) ∈ O(n log n log log n). With Fürer's algorithm [START_REF] Fürer | Faster integer multiplication[END_REF], one has M (n) ∈ n log n 2 O(log * n) , where log * n is the number of times the logarithm function has to be applied to n before the result drops below 1. So with either algorithm, M (n) ∈ O n log 1+ε n for any ε > 0.

The four basic arithmetic operations and the square roots of real floating point numbers of precision n have a complexity of O(M (n)), the inversion and square roots being realised by Newton iterations as explained in Lemmata 2.2 and 2.3 of [START_REF] Brent | Fast multiple-precision evaluation of elementary functions[END_REF]. The same article shows that exp, sin and the constant π can be computed in O(log n M (n)).

Thus, the four basic operations on complex floating point numbers of precision n can be executed in time

O(M (n)). Letting c = a+ √ a 2 +b 2 2
for a > 0, one obtains

√ a + bi = c + b 2c in time O(M (n)).
Finally, the complex exponential may be reduced to the real exponential and the real sine and cosine functions and is thus computed with complexity O(log n M (n)). The following algorithm ([27, Algorithm 10.3]) obtains a monic polynomial of degree h from its roots by organising the computations in a binary tree.

Algorithm 3.1 (Poly_from_roots). Input: h ∈ N and x 1 , . . . , x h ∈ C Output: binary tree T k,i = X -x (i-1)2 k +1 • • • X -x min(i 2 k ,h) for k = 0, . . . , t = ⌈log 2 h⌉, i = 1, . . . , 2 t-k ; in particular, the root T t,1 = (X -x 1 ) • • • (X -x h ) (1) for i = 1 to h T 0,i ← X -x i (2) for i = h + 1 to 2 t T 0,i ← 1 (3) for k = 1 to t for i = 1 to 2 t-k T k,i ← T k-1,2i-1 • T k-1,2i (4) return T
If the needed roots of unity are precomputed, the algorithm has a complexity of O(h log 2 h M (n)). Notice that the roots of unity of order 2 ⌈log 2 h⌉ suffice to carry out all the FFTs in Algorithm 3.1. By Section 3.1, computing a primitive root of unity takes O(log n M (n)), all others can be obtained by successive multiplications in O(h M (n)). Thus, the total complexity of Algorithm 3.1 becomes

O((h log 2 h + log n)M (n)).
One of the asymptotically optimal algorithms for class polynomials relies on a related technique of symbolic computation (see [27, §10.1]). Let f (X) be a polynomial of degree d over C that is to be evaluated in h different arguments x 1 , . . . , x h . The key observation for doing so fast is that f

(x i ) is nothing but f (X) mod X -x i .
So the first step of the algorithm is the construction of the binary tree T k,i as in Algorithm 3.1, containing products of more and more of the X -x i . Then a matching tree R k,i = f mod T k,i is computed in the converse order, from its root to its leaves, such that the leaves contain the desired values of f .

Algorithm 3.2 (Multi_eval). Input: h ∈ N, f ∈ C[X] and x 1 , . . . , x h ∈ C Output: f (x 1 ), . . . , f (x h ) (1) T ← Poly_from_roots (h, x 1 , . . . , x h ) (2) t ← ⌈log 2 h⌉, R t,1 ← f mod T t,1 (3) for k = t -1 downto 0 for i = 1 to 2 t-k R k,i ← R k+1,⌊ i+1 2 ⌋ mod T k,i (4) return R 0,1 , . . . , R 0,h
A division with remainder of a polynomial of degree d by a polynomial of degree d ′ has the same complexity as multiplying polynomials of degree bounded by d ([27, §9.1]). The algorithm first computes an inverse modulo some power of X by Newton iterations and obtains the quotient with one multiplication; the remainder then requires another multiplication. So after the first reduction of f modulo the product of all the X -x i , the complexity of Algorithm 3.2 on n-bit numbers is the same as that of Algorithm 3.1. Including the first reduction, it is given by

O((d log d + h log 2 h + log n)M (n)).

The height of class polynomials

The running time of the algorithms working with floating point approximations depends crucially on the precision n. To be able to round the approximated class polynomial to a polynomial over the integers (Z or the maximal order of an imaginary-quadratic number field), n has to be at least the bit size of the largest coefficient, or otherwise said, the logarithmic height of the polynomial. In this section, we prove Theorem 1.2 by developing an explicit upper bound without hidden constants for the height of the class polynomial for j. The result is of independent interest; for instance, it allows to bound the precision also for the p-adic algorithms, which yields a proof of correctness for their output.

As shown in [START_REF] Enge | Comparing invariants for class fields of imaginary quadratic fields[END_REF], the height of class polynomials for a different f changes asymptotically by a constant factor, depending on the degrees in f and j of the modular polynomial connecting the two functions. So this section proves an asymptotic bound of O |D| log 2 |D| for the height of any class polynomial. To obtain a more explicit bound for invariants other than j, the techniques of this section may be used with the necessary adaptations.

Let us first give the intuitive basis for the bound. Since the values of j are usually large, more often than not the largest coefficient of the class polynomial is its constant one. Then approximating j(τ ) = q -1 + 744 + ∞ ν=1 c ν q ν by the first term, q -1 , one obtains a heuristic estimate for the height as

π |D| [A,B,C] 1 A ,
where the sum is taken over all reduced primitive quadratic forms of discriminant D. This heuristic estimate is very well confirmed by experimental findings, see [START_REF] Enge | Comparing invariants for class fields of imaginary quadratic fields[END_REF].

Turning this idea into an explicit bound is mainly a matter of computations that are sketched in the following.

The reducedness of the quadratic forms is equivalent to the τ -values lying in the standard fundamental domain F for the action of Sl 2 (Z) on H, (4.1)

F = z ∈ H : |z| > 1, - 1 2 ≤ ℜ(z) < 1 2 ∪ z ∈ H : |z| = 1, - 1 2 ≤ ℜ(z) ≤ 0 . Then |q| ≤ e 2πi 1+ √ -3 2 = e -π √ 3 . The upper bound c ν ≤ e 4π √ ν √ 2ν 3/4 of [8] then yields |j(τ ) -q -1 | ≤ 744 + ∞ ν=1 e 4π √ ν √ 2ν 3/4 e -π √ 3 ν = k 1 = 2114.566 . . .
for τ in the fundamental domain F , so that

|j(τ )| ≤ |q -1 | + k 1 ≤ k 2 |q -1 | with k 2 = 1 + k 1 e -π
√ 3 = 10.163 . . . Let the A i be numbered in increasing order. Then the logarithm of the absolute value of the coefficient in front of X j is bounded above by

log h j h-j i=1 (k 2 |q -1 i |) ≤ log 2 h k h 2 h i=1 |q -1 i | ≤ log(2k 2 )h + π |D| h i=1 1 A i , independently of j.
The next step consists of estimating

h i=1 1
Ai . It is proved in [41, Lemma 2.2] that h i=1 1 Ai ∈ O(log 2 |D|).
We shall derive a bound that makes the involved constants explicit. Consider the number of possible B for a given A. This number is certainly bounded above by the number of B ∈]-A, A] that satisfy B = D mod 2 and B 2 -D 4 = 0 mod A. Assuming the worst case that the quadratic equation has a root modulo each prime divisor of A and considering the cases of odd and even A separately, one obtains an upper bound on the number of B of 2 • 2 ω(A) ≤ 2τ (A), where ω(A) denotes the number of prime factors of A and τ (A) its number of divisors. Hence,

h i=1 1 A i ≤ 2 |D| 3 A=1 τ (A) A ,
and this sum may be bounded by standard techniques from analytic number theory. We use the estimates

(4.2) log N + γ ≤ N n=1 1 n ≤ log N + γ + 1 2N
with Euler's constant γ = 0.577 . . . and

(4.3) N n=1 log n n ≥ log 2 2 + N +1 3 log t t dt ≥ 1 2 log 2 N -k 3 with k 3 = 1 2 (log 2 3 -log 2) = 0.256 . . . We have 2 N A=1 τ (A) A = 2 N A=1 1≤m,n:mn=A 1 mn = 2 1≤m,n:mn≤N 1 mn = 2 N m=1 1 m ⌊N/m⌋ n=1 1 n ≤ 2 N m=1 1 m log N m + γ + 1 2 N m ≤ log 2 N + 4γ log N + 2γ 2 + log N + γ N + 2k 3 + N m=1 1 m N m by (4.
2) and (4.3) Using (4.2), the last term of this sum can be bounded by

N m=1 1 m N m ≤ ⌊ N 2 ⌋ m=1 1 m N m -1 + N m=⌊ N 2 ⌋+1 1 m ≤ 2 N m=⌈ N 2 ⌉ 1 m ≤ 2 log 2 + 1 N
Combining the inequalities, the height of the class polynomial is bounded from above by (4.4)

k 5 h + π |D| log 2 N + 4γ log N + log N + γ + 1 N + k 4 with N = |D| 3 , k 4 = 2k 3 + 2 log 2 + 2γ 2 =

Class group enumeration

Computing the class group of O D by enumerating all reduced primitive quadratic forms of discriminant D is a step of the algorithm that can be neglected in practice.

In the new algorithms of Sections 6.3 and 6.4, however, its theoretical complexity risks to come close to that of the crucial parts. One has to determine all coprime To find the square root of D modulo A, the prime factorisation of A is required, and the most convenient approach is to enumerate the A in factored form. To this purpose, one needs the primes up to So Chinese remaindering is the dominant step of this algorithm for class group enumeration, and the first bound of Theorem 1.4 is proved.

[A i , B i , C i ] such that |B i | ≤ A i ≤ C i , B i > 0 if

5.3.

Generating the class group by primes. Another possible approach is to start with a set of prime forms generating the class group. According to [4, p. 376], under GRH a system of generators is given by the forms having a prime A-value bounded by 6 log 2 |D|, and these can be computed in time polynomial in log |D|. Let p 1 , p 2 , . . . denote these generators. One may enumerate the powers of p 1 in the class group by composing and reducing quadratic forms until reaching the order e 1 of p 1 such that p e1 1 = 1. Next, one computes the powers of p 2 until p e2 2 lies in the subgroup generated by p 1 , constructed in the previous step; then all combinations p a1 1 p a2 2 with 0 ≤ a i < e i are added to yield the subgroup p 1 , p 2 . One continues with the powers of p 3 until p e3 3 falls into this subgroup, and so forth. If all computed elements are stored in a hash table or simply in a matrix indexed by A and B, looking them up takes negligible time. The running time of the algorithm is dominated by O(h) computations in the class group, each of which takes O(log log |D| M (log |D|)) by [START_REF] Schönhage | Fast reduction and composition of binary quadratic forms[END_REF]. This proves the second bound of Theorem 1.4.

5.4.

From class groups to N -systems. When working with a class invariant other than j that is not invariant under Sl 2 (Z), but only under Γ 0 (N ) for some N > 0, the representatives of the class group need to be normalised to obtain a coherent set of algebraic conjugates. Such a normalisation is, for instance, given by an N -system as defined in [START_REF]Weber's class invariants revisited[END_REF]. It has the property that gcd(A i , N ) = 1 and B i ≡ B 1 (mod 2N ) for 1 ≤ i ≤ h and may be obtained by applying suitable unimodular transformations to the original [A i , B i , C i ]. The coefficients of these transformations are defined modulo N , so that for fixed N , trying all possibilities requires a constant number of arithmetic operations per form and increases the size of the A i , B i and C i by a constant factor. Thus, transforming a system of reduced quadratic forms into an N -system requires an additional O(h M (log |D|)), which is covered by the previous enumeration of the forms. (In practice, one would use a more intelligent approach to lower the complexity with respect to N , cf. the constructive proof of Proposition 3 in [START_REF]Weber's class invariants revisited[END_REF].)

Complexity of class polynomial computation

We are now able to provide the generic complexity for class polynomial computation via floating point approximations. Different approaches to evaluating the class invariants lead to algorithms with different overall complexities; these are examined below.

Let n be the precision in bits used for the computations, let h be the class number of O D and denote by E(h, n) the time needed to evaluate the class invariant with precision n in h values. Then the algorithm takes

• O(h 1+ε ) for enumerating the class group according to Section 5; • E(h, n) for evaluating the class invariant and • O((h log 2 h + log n)M (n)) for reconstructing the class polynomial from its roots according to Algorithm 3.1.

The class group computation is indeed negligible since E(h, n) is at least of order hn, which is the time needed to write down the conjugates. So it remains to examine in more detail the quantity E(h, n).

We propose four different algorithms for evaluating modular functions. The first two of them are well-known, the third one is a novel application of the techniques of symbolic computation presented in Section 3.2, and it already allows to obtain the complexity stated in Corollary 1.3. The fourth one gains an additional logarithmic factor for the evaluation phase and yields the slightly more precise statement of Theorem 1.1 without changing the conclusion of Corollary 1.3.

The class polynomial

H D [f ] = h i=1 (X -f (τ i )) is obtained by evaluating the function f in the h different arguments τ i = -Bi+ √ D 2Ai
for an N -system [A i , B i , C i ] (see Section 3.2), where N depends on f and is assumed to be fixed. Since f (z) is modular for Γ 0 (N ), it is invariant under the translation z → z + N and admits a Fourier transform, that is, a Laurent series expansion in the variable q 1/N = e 2πiz/N . Thus, the f (τ i ) may be obtained by first computing the corresponding q 1/N i and then evaluating the q-expansion in these arguments. By Section 3.1, the q i can be computed in time O(h log n M (n)), which will be dominated by the actual function evaluations.

6.1. The naïve approach. The straightforward technique for evaluating the modular function f = ν1 ν=ν0 c ν q 1/N ν consists of a Horner scheme for the polynomial part ν1-ν0 ν=0 c ν+ν0 q 1/N ν and a multiplication by q 1/N ν0 . (Notice that usually ν 0 < 0.) Its complexity is O((ν 1 -ν 0 + log ν 0 )M (n)), the c ν having been precomputed to precision n. Actually, ν 0 is a constant depending only on f ; ν 1 , however, depends not only on the c ν , but also on the desired precision n and on q 1/N and thus on the function argument.

Consider first the classical case of f being j, which is invariant under Sl 2 (Z). We may then assume that the arguments are transformed by a matrix in Sl 2 (Z) into the standard fundamental domain F of (4.1) prior to evaluating j, so that |q| ≤ e -π √ 3 is bounded from above by a constant less than 1. On the other hand, it is shown in [START_REF] Brisebarre | Effective lower and upper bounds for the Fourier coefficients of powers of the modular invariant j[END_REF] that 0

≤ c ν ≤ e 4π √ ν √ 2 ν 3/4 for ν ≥ 1. Thus, it is possible to fix ν 1 ∈ O(n) to obtain a precision of O(n) digits.
The total complexity of evaluating j at h values then becomes

O(hn M (n)),
or

O |D| log 3 |D| M |D| log 2 |D| ⊆ O |D| 3/2 log 6+ε |D| with n ∈ O |D| log 2 |D| and h ∈ O
|D| log |D| according to Section 4. Concerning alternative class invariants, unfortunately the fundamental domain for Γ 0 (N ) with N > 1 contains at least one rational number (called a cusp). In such a cusp, |q| = 1, and the q-expansion usually diverges; in a neighbourhood of the cusp, it may converge arbitrarily slowly. In this case, it is possible to use a different expansion in the neighbourhood by transporting the cusp to infinity via a matrix in Sl 2 (Z). We will not pursue this discussion, since the approach of Section 6.2 provides a faster and simpler solution for all currently used class invariants. 6.2. Using the sparsity of η. Virtually all class invariants suggested in the literature are in some way derived from Dedekind's η-function. This is the case for the

Weber functions f(z) = e -πi/24 η( z+1 2 ) η(z) , f 1 (z) = η( z 2 ) η(z) and f 2 (z) = √ 2 η(2z)
η(z) already examined in [START_REF] Weber | Elliptische Funktionen und algebraische Zahlen[END_REF], the generalised Weber functions w N (z) = η( z N ) η(z) suggested in [START_REF]Further investigations of the generalised Weber functions[END_REF], the double η quotients w p1,p2 (z) =

η z p 1 η z p 2 η(z)η z p 1 p 2
proposed in [START_REF] Enge | Constructing elliptic curves over finite fields using double eta-quotients[END_REF], and even for j. In fact, j is most conveniently computed as j =

f 24 1 +16 f 8 1 3
. The definition of η in [START_REF] Dedekind | Erläuterungen zu den vorstehenden Fragmenten, Bernhard Riemann's gesammelte mathematische Werke und wissenschaftlicher Nachlaß[END_REF] is closely related to the partition generating function:

η = q 1/24 ν≥1
(1 -q ν ); evaluating the product to precision n requires O(n) arithmetic operations. An expression better suited for computation is given by Euler's pentagonal number theorem [START_REF] Euler | Evolutio producti infiniti (1-x)(1-xx)(1-x 3 )(1-x 4 )(1-x 5 )(1-x 6 ) etc. in seriem simplicem[END_REF]:

η = q 1/24 1 + ∞ ν=1 (-1) ν q ν(3ν-1)/2 + q ν(3ν+1)/2 .
Since the occurring exponents are values of quadratic polynomials, the series is very sparse: To reach an exponent of order O(n), only O( √ n) terms need to be computed, and this process can be implemented with O( √ n) multiplications. Recall that any polynomial of fixed degree can be evaluated in an arithmetic progression with a constant number of arithmetic operations per additional value, once the first few values are known; the employed algorithm relies on iterated differences. In the special case of η, the following recursion yields two additional terms of the series at the expense of four multiplications by recursively computing q ν , q 2ν-1 , q ν(3ν-1)/2 and q ν(3ν+1)/2 as follows:

q ν = q ν-1 • q q 2ν-1 = q 2(ν-1)-1 • q 2
q ν(3ν-1)/2 = q (ν-1)(3(ν-1)+1)/2 • q 2ν-1 q ν(3ν+1)/2 = q ν(3ν-1)/2 • q ν

Besides the sparse and regular series expression, the η function has a second crucial property that makes it well suited for computation: It is a modular form of weight 1/2. As such, unlike j, it is not invariant under transformations in Sl 2 (Z). However, its transformation behaviour is explicitly known (cf. [17, §4]) and easily computable. Thus, to obtain η(z) for an arbitrary value of z, one should first transform z into the fundamental domain F , so that the series can be truncated at an exponent of order O(n). Then the evaluation of O( √ n) terms of the η series for O(h) distinct values (the constant being at most 4 for the w p1,p2 mentioned in the beginning of this section) with a floating point precision of O(n) digits can be carried out in time

O(h √ n M (n)), or O |D| 3/4 log 2 |D| M |D| log 2 |D| ⊆ O |D| 5/4 log 5+ε |D| as h ∈ O |D| log |D| and n ∈ O |D| log 2
|D| according to Section 4. It remains, however, to verify that transforming the arguments into the fundamental domain is dominated by the cost of the series evaluation. The arguments being roots of an or z N , corresponding to quadratic forms whose discriminants have absolute values in O(|D|).

N -system [A i , B i , C i ] with A i , |B i | ∈ O(N 2 |D|) = O( |D|),
6.3. Multipoint evaluation. The algorithms of Sections 6.1 and 6.2 compute the values of modular functions one at a time; but for the sake of class polynomial computation, we need the values in many points. For polynomials, Algorithm 3.2 provides a fast way of doing exactly this. And indeed, from a numerical point of view a class invariant can be seen as a polynomial via its truncated q-expansion. Either one considers the function directly as done for j in Section 6.1, or one proceeds via η as in Section 6.2. In both cases, a polynomial of degree O(n) has to be evaluated in O(h) points, which by Algorithm 3.2 can be done in time

O (n log n + h log 2 h)M (n) ⊆ O |D| log 3 |D| M |D| log 2 |D| ⊆ O |D| log 6+ε |D| .
6.4. Newton iterations on the arithmetic-geometric mean. A new approach for evaluating modular functions in single arguments is described in [START_REF] Dupont | Fast evaluation of modular functions using Newton iterations and the AGM[END_REF]. It is based on the arithmetic-geometric mean and Newton iterations on a function involving it. The basic algorithm underlying [START_REF] Dupont | Fast evaluation of modular functions using Newton iterations and the AGM[END_REF]Theorem 4] computes the modular function k ′ , whose square λ satisfies 256 1

-λ + λ 2 3 (λ(1 -λ)) 2 = j.
For an argument with imaginary part bounded by a constant and the precision n tending to infinity, it has a complexity of O(log n M (n)).

During class polynomial computations, the precision and the imaginary part of the arguments are tightly coupled, so that this algorithm is not sufficient to derive the desired complexity result. The modification of [START_REF] Dupont | Fast evaluation of modular functions using Newton iterations and the AGM[END_REF]Theorem 5] obtains the same complexity of O(log n M (n)) uniformly in the argument. If the imaginary part of the argument is of the order of the required precision, then the algorithm of Section 6.2 or even the naïve algorithm of Section 6.1 already yield the desired result with a constant number of arithmetic operations. Otherwise, the argument is repeatedly divided by 2 until its imaginary part is smaller than a constant, which can be compensated by iterations of the arithmetic-geometric mean. Then the previous Newton algorithm converges sufficiently fast.

For other modular functions f , one may have the evaluation of k ′ followed by Newton iterations on the modular polynomial relating k ′ and f . For fixed f , this phase does not increase the complexity. The approach does not work, however, for η, which is a modular form of weight 1/2 instead of a modular function (of weight 0). The algorithm of [18, Section 7.2] computes first θ 2 00 , a certain modular form of weight 1, as the inverse of the arithmetic-geometric mean of 1 and k ′ , and then η as the twelfth root of λ(1-λ)θ 2 00 /16 by a suitably initialised Newton process. Again, one obtains a complexity of O(log n M (n)) for an evaluation at precision n, uniformly in the argument.

The complexity for evaluating in h arguments then becomes

O(h log n M (n)) ⊆ O |D| log 2 |D| M |D| log 2 |D| ⊆ O |D| log 5+ε |D|
with the estimates of Section 4 for h and n. Taking into account the time needed to compute the class polynomial from its roots by Algorithm 3.1, this proves Theorem 1.1.

Implementation

The algorithms of this article have been implemented using gmp [START_REF] Granlund | gmp -GNU multiprecision library[END_REF] with an assembly patch for 64 bit AMD processors [START_REF] Gaudry | Assembly support for GMP on AMD64[END_REF], mpfr [START_REF] Hanrot | mpfr -a library for multiple-precision floating-point computations with exact rounding[END_REF] and mpc [START_REF] Enge | mpc -a library for multiprecision complex arithmetic with exact rounding[END_REF] for the multiprecision arithmetic and mpfrcx [START_REF] Enge | mpfrcx -a library for univariate polynomials over arbitrary precision real or complex numbers[END_REF] for the polynomial operations. Table 1 provides running times for class numbers between 2500 and 100000, obtained on an AMD Opteron 250 with 2.4 GHz. All timings are given in seconds and rounded to two significant digits. (The computations for class number 100000 have been carried out on a 2.2 GHz machine disposing of more memory, and the running times have been scaled accordingly.) For each class number, the discriminant with smallest absolute value has been chosen. Only the algorithms of Sections 6.2 to 6.4 are taken into account; the naïve approach of Section 6.1 is clearly inferior to the one exploiting the sparsity of η. The chosen class invariant is the double η-quotient w 3,13 , and its values are obtained by precomputing a table for the values of η at the h reduced quadratic forms.

The first lines of the table provide some general information. The precision (1) of the floating point computations is obtained by increasing the estimate of Section 4 by 1% to account for potential rounding errors. As the chosen class invariant is not j, a correction factor depending on the class invariant needs to be used, see Section 4. This factor is correct only asymptotically, which explains why the actual height (2) is a bit smaller than the precision estimate. For j, the two are closer to The second block of lines provides timings for the steps that are independent of the algorithm used for evaluating the modular function. As can be seen, the class group computation (4) is completely negligible. Line [START_REF] Paulo | Constructing elliptic curves with prescribed embedding degrees[END_REF] corresponds to the effort of deriving all values of the class invariant from the tabulated η values (reduction of quadratic forms, multiplication by 24-th roots of unity and computation of the η quotients). The computation of the polynomial from its roots (6) corresponds precisely to Algorithm 3.1, and provides a measure for the complexity of the operations with polynomials. For constructing the largest polynomial of degree 100000, the polynomial FFT has been disabled during the last steps and replaced by Toom-Cook multiplication, since the FFT consumed too much memory; this explains the jump from h = 40000.

The third block contains the timings for evaluating η in the reduced quadratic forms (7) using the sparse series representation as described in Section 6.2, and the total running time for computing the class polynomials using this technique [START_REF] Bröker | Constructing elliptic curves of prescribed order[END_REF]. Line [START_REF] Brisebarre | Effective lower and upper bounds for the Fourier coefficients of powers of the modular invariant j[END_REF] details the time spent in [START_REF] Brezing | Elliptic curves suitable for pairing based cryptography[END_REF] (and also in (10)) for computing the q i ; it essentially measures the complex exponential.

The fourth block represents the corresponding results for the multipoint evaluation approach of Section 6.3, and the last block corresponds to the asymptotically fastest evaluation of Section 6.4, for which an implementation by Dupont has been used. As explained in Section 6.4, the algorithm requires to switch to the sparse series evaluation when the imaginary part of the argument becomes too large. In the implementation, the AGM code is disabled for an imaginary part larger than 5.

Comparing first the evaluation of η as a sparse series or by multipoint evaluation, one notices that the asymptotically faster algorithm is about 5 to 8 times slower on the examples and that it appears to catch up with growing class numbers. However, this happens so slowly that one cannot expect it to beat the algorithm in O |D| 1.25+ε in the foreseeable future for any tractable instance.

The approach using Newton iterations on the AGM is faster than multipoint evaluation, but still hardly beats the asymptotically slower algorithm in O |D| 1.25+ε : The biggest computed example of class number 100000 lies just beyond the crossover point! One notices that the growth rates of the running times of all algorithms, instead of behaving like |D| or |D| 1.25 , come closer to |D| 1.4 or |D| 1.6 . A small part of this can be explained by the rather peculiar choice of discriminants. Taking the first one with a given class number, the precision n is rather large compared to h and |D|, since there are many forms with small A so that the sum

h i=1 1
Ai becomes comparatively large.

However, the major reason for the faster than predicted growth of computing time is that for the floating point arithmetic the range for asymptotically fast algorithms is not yet reached. The threshold for switching to the FFT in gmp on the test machine is set to about 500000 bits; so the examples lie still in the Karatsuba or Toom-Cook range, which accounts for a growth of M (n) of n log 3/ log 2 resp. n log 5/ log 3 instead of n.

A possible improvement of the multipoint evaluation approach consists of conveniently grouping the arguments. For instance, in the example of class number 5000, the function η has to be evaluated in 2501 arguments (corresponding to the two ambiguous forms and 2499 pairs of opposite non-ambiguous forms). Assuming the worst case of |q| ≈ e -π √ 3 , that is almost reached for the largest values of A, one can approximate η by a polynomial of degree 1190. As multipoint evaluation should be most efficient when the number of arguments is about half the degree, it makes sense to perform four evaluations in 625 resp. 626 arguments each. But sorting them by their absolute values, the smaller ones do not actually require such a high degree approximation of η. In the example, an approximation of degree 260, 551, 805 resp. 1190 is sufficient for the four chunks of q. Then the time used for multipoint evaluation drops from 93 s to 64 s. Experimenting with different partitions of the arguments (three resp. five parts of the same size, parts of different sizes adapted to the degree of the approximations, etc.) yields similar results, far from competing with the sparse series evaluation.

Another point to take into account are the space requirements of the algorithms. When each root of the class polynomial is computed separately, only O(hn) bits need to be stored, which is linear in the output size. Multipoint evaluation as described in Section 3.2, however, requires that the tree constructed in Step 1 of Algorithm 3.2 be maintained in memory, so that the occupied space grows by a logarithmic factor to reach O(hn log h). This logarithmic factor could be saved by evaluating in chunks of O h log h arguments, as explained in Lemma 2.1 of [START_REF] Von | Computing Frobenius maps and factoring polynomials[END_REF]. Anyway, the example class polynomial of degree 100000 uses over 5 GB as an uncompressed text file and is computed in about 3 days. This shows that the limiting factor is the memory requirement rather than the running time, as can be expected from algorithms that have a close to linear complexity with respect to their output size.

As a final remark, one notices that the algorithms behave numerically well, even though rounding errors do occur during floating point computations. For the algorithm of Section 6.2, this can be explained by the sparsity of the η series and the fact that all coefficients are +1 and -1. Indeed, if the last few digits of a term are erroneous, these errors propagate to subsequent terms. However, the absolute magnitude of such errors decreases rapidly, so that the wrong digits in later terms actually do not intervene in the additions. (Otherwise said, the computations may as well be carried out with fixed point numbers, and indeed a simulation of fixed point arithmetic using floating point numbers of decreasing precision yields accurate results.) 8. Comparison to other approaches 8.1. Chinese remaindering. In [START_REF] Agashe | Constructing elliptic curves with a known number of points over a prime field[END_REF], the authors suggest an approach for directly computing class polynomials for j modulo a prime p. The basic idea is to derive the polynomial modulo many small primes by enumerating all elliptic curves modulo these small primes and only retaining those having complex multiplication by O D . Then a Chinese remainder technique allows to obtain the class polynomial modulo p.

Unfortunately, it is not sufficient to gather only O(log p) bits of information modulo small primes per coefficient of the class polynomial, although this is the information contained in the final output. In fact, so many small primes are needed that the class polynomial could be reconstructed over Z instead of only modulo p. The complexity derived in Section 3. Thus, it is asymptotically faster to compute the class polynomial over Z using floating point approximations and to reduce it modulo p afterwards. 8.2. p-adic algorithms. Couveignes and Henocq suggest in [START_REF] Couveignes | Action of modular correspondences around CM points, Algorithmic Number Theory -ANTS-V[END_REF] a p-adic approach for computing class polynomials for j. The basic idea is to look for a small prime p and (by exhaustive search) an elliptic curve modulo p with complex multiplication by O D . This curve is then lifted to the p-adic numbers with a high enough precision so that the class polynomial may be reconstructed. Alternatively, they show how to work with supersingular curves. The complexity of their approach is O(|D| 1+ε ), where the exact power of the logarithmic factor has not been worked out. By nature, the algorithm is not affected by rounding errors, and using the explicit bound of Theorem 1.2 its output is certified to be correct.

So the complex and the p-adic approach are both essentially linear in the size of the class polynomials. All variants have been implemented (for more details on the complex implementation, see [START_REF] Enge | Comparing invariants for class fields of imaginary quadratic fields[END_REF]; for the ordinary p-adic algorithm, see [START_REF] Bröker | Elliptic curves with a given number of points, Algorithmic Number Theory -ANTS-VI[END_REF]; for the supersingular one, [START_REF] Lercier | Elliptic curves with complex multiplication[END_REF]), and all seem to work reasonably well in practice. The floating point algorithms are easy to implement with arbitrary class invariants using the results of [START_REF]Weber's class invariants revisited[END_REF]. The p-adic approach with ordinary curves has been made to work with certain class invariants other than j, see [START_REF] Bröker | Elliptic curves with a given number of points, Algorithmic Number Theory -ANTS-VI[END_REF] and [START_REF] Bröker | Constructing elliptic curves of prescribed order[END_REF]Chapter 6]. The considerable overhead involved makes it unclear whether it is competitive with the complex approach.

Theorem 1 . 2 .≤ c 1 N

 121 The logarithmic height of the class polynomial for j for the discriminant D of class number h is bounded above byc 5 h + c 1 N log 2 N + 4γ log N + c 6 + log N + γ + 1 N log 2 N + c 2 N log N + c 3 N + c 1 log N + c 4where N = |D| 3 , γ = 0.577 . . . is Euler's constant, c 1 = √ 3π = 5.441 . . ., c 2 = 18.587 . . ., c 3 = 17.442 . . ., c 4 = 11.594 . . ., c 5 = 3.011 . . . and c 6 = 2.566 . . .. The asymptotic upper bound of O |D| log 2 |D| holds for any other class invariant as well.

Corollary 1 . 3

 13 (heuristic). Taking n ∈ O |D| log 2 |D| in Theorem 1.1 and using the bound on the class number h ∈ O |D| log |D| proved at the end of Section 4, the algorithm of Section 6.4 computes the class polynomial for f in time

Theorem 1 . 4 .

 14 The class group of the imaginary-quadratic order of discriminant D and class number h can be enumerated • unconditionally by a probabilistic algorithm in time O |D| log |D| log log |D|M (log |D|) ;

3. 2 .

 2 Polynomial arithmetic. Concerning operations with polynomials, we assume that a floating point precision of n bits has been fixed and is the same for all input and output polynomials. Multiplying two polynomials of degree d over C by the FFT takes O(d log d) multiplications in C, whence it has a complexity of O(d log d M (n)) once the necessary roots of unity have been computed.

  2.566 . . . and k 5 = log(2k 2 ) = 3.011 . . . Similarly to the argumentation above one shows that (4.5) h ≤ 2 N A=1 τ (A) ≤ 2N (log N + γ) + 1, which also implies h ∈ O |D| log |D| . Combining (4.4) and (4.5) yields the bound of Theorem 1.2.

5 . 1 . 5 . 2 . 4 =

 51524 one of the inequalities is not strict, and D = B 2 i -4A i C i . These conditions imply that A i ≤ |D| 3 . The naïve algorithm. The following trivial algorithm is implemented in the code described in more detail in Section 7: Loop over A and B such that 0 ≤ B ≤ A ≤ |D| 3 and B ≡ D (mod 2) and compute the corresponding C, if it exists. While it can be seen in the figures of Table 1 that this approach takes virtually no time, it carries out O(|D|) arithmetic operations with integers of bit size in O(log |D|) and thus has a complexity of O(|D| M (log |D|)), which is smaller than the bound of Corollary 1.3 only by logarithmic factors. Saving one loop. An asymptotically faster (and again up to logarithmic factors optimal) algorithm is inspired by the theoretical considerations of Section 4. Looping over A in the interval 1 ≤ A ≤ |D| 3 , one solves the congruence B = D mod 2 and B 2 -D 0 mod A, and keeps the form if C = B 2 -D 4A ≥ A. As shown in Section 4, the total number of B to consider is in O( |D| log |D|).

  |D| log |D| log log |D| by[START_REF] Atkin | Prime sieves using binary quadratic forms[END_REF]. All possible A are then computed with an amortised cost of one multiplication per value in total time O( |D| M (log |D|)).For any given A and prime p|A, a square root of D modulo p is computed in O(log p M (log p)) by Cipolla's algorithm[START_REF] Cipolla | Un metodo per la risoluzione della congruenza di secondo grado[END_REF], lifting to a root modulo p e for p e ||A requires an additional O(e M (log p)). For one A, this takes O   p e ||A log(p e ) M (log p)   ⊆ O(log A M (log A)) ⊆ O(log |D| M (log |D|)), or O |D| log |D| M (log |D|) for all A. The roots modulo prime powers have to be recombined by the Chinese remainder theorem to form a candidate B. Organising the computations in a tree with the leaves indexed by the p e ||A, one may use the analogues for numbers of the fast algorithms for polynomials of Section 3.2. The tree has ω(A) ∈ O(log A) leaves and thus a height of O(log log A), and the root contains a number of O(log A) digits, so that one computation of Chinese remainders takes O(log log A M (log A)). This is to be multiplied by the total number of B, which yields an overall complexity of O( |D| log |D| log log |D| M (log |D|)).

  they may be transformed into F by reducing the quadratic forms in time O(h M (log |D|)) (see [12, Prop. 5.4.3]), which is negligible. The same holds for arguments such as z+1 2

  2 of[START_REF] Agashe | Constructing elliptic curves with a known number of points over a prime field[END_REF] isO |D| 3/2 log 10 |D| + |D| log 2 |D| log p + |D| log 2 p ,and already the term depending only on |D| is worse than what is obtained with the algorithms of Section 6.

Table 1 .

 1 Running times each other. M (n) is measured by computing the first 100000 successive powers of π + iγ with Euler's constant γ.

			5000	10000	20000	40000	100000
	|D|	6961631 23512271 98016239 357116231 2093236031
	(1) precision n (bits)	9540	20317	45179	96701	264727
	(2) height (in base 2)	8431	18114	40764	87842	242410
	(3) M (n)	7.3	23	75	230	1080
	(4) class group	0.1	0.1	0.4	1.3	6.8
	(5) conjugates from η	3.4	21	140	890	10000
	(6) poly. from roots	13	93	730	5200	120000
	sparse series
	(7) η		12	98	900	7700	140000
	(8)	of which qi	3.0	22	170	1300	20000
	(9) total time	28	210	1800	14000	270000
	multipoint eval.
	(10) η		93	640	5700	42000	aborted
	(11) total time	110	750	6500	48000
	(10) / (7)	7.8	6.5	6.3	5.5	-
	AGM
	(12) η		32	200	1400	9900	130000
	(13) total time	48	320	2300	16000	260000
	(12) / (7)	2.7	2.0	1.6	1.3	0.93

Acknowledgements. I am grateful to Régis Dupont for letting me use his code to test the fast evaluation of η via the arithmetic-geometric mean. I thank Karim Belabas for pointing out to me the basic idea of Section 4, Pierrick Gaudry and François Morain for numerous discussions and Dan Bernstein, Reinier Bröker, Kristin Lauter and Marco Streng for helpful comments.