View of Generalized division polynomials

(1)

GENERALIZED DIVISION POLYNOMIALS

TAKAKAZU SATOH

Abstract

LetEbe an elliptic curve with complex multiplication by the ringOFof integers of an imaginary quadratic fieldF. We give an explicit condition onα∈OFso that there exists a rational function ψαsatisfying divψα=

P∈Ker[α][P]−NF/Q(α)[O] where [α] is the multiplication byαmap.

We give an algorithm to computeψαbased on recurrence formulas among these functions. We prove that the time complexity of this algorithm isO(NF/Q(α)^2+ε)bit operations under an FFT based multiplication algorithm asNF/Q(α)tends to infinity for the fixedE.

1. Introduction

Letkbe a perfect field. It is known that for an elliptic curveE/kandn∈N there exists a rational functionψn onEsatisfying div(ψn)=

P∈E[n][P]− n²[O], whereO is the point at infinity. See e.g. Silverman[10, Exercise 3.7]

for char(k)=2, 3, Koblitz[7] for char(k)=2. IfEis given by the Weierstrass model, such functions are polynomials of coordinate functions and they are called division polynomials.

Now letE : Y² = X³+aX+bbe an elliptic curve admitting complex multiplications by the ringOF of integers of an imaginary quadratic fieldF wherea and bare algebraic integers. Put K := F (a, b). In this paper, we generalize division polynomials for someα ∈OF −Z. Our goal is to give a deterministic algorithm to compute generalized division polynomials and to estimate its bit complexities. More specifically, in Corollary 2.6, we prove that a rational functionψαonEsatisfying div(ψα)=

P∈Ker[α][P]−NF/Q(α)[O] exists if and only if eitherNF/Q(α)is an odd integer or 2|α(inOF). We call such an element ofOF unbiased. Then, with a suitable normalization, we derive the relation

(1.1) ψ_β²ψα+γψα−γ −ψ_α²ψβ+γψβ−γ =ψα+βψα−βψ_γ²

forα, β, γ ∈OF provided all indexes appearing in (1.1) are unbiased (Corol- lary 3.7). Choosingγ carefully, we obtain recurrence formulas which gives an efficient algorithm to compute generalized division polynomials. Since our

Received February 14, 2003.

(2)

generalized polynomials only exist for unbiased elements inOF, it is important to construct recurrence formulas with unbiased elements. In Corollary 4.3, we prove thatψαis a polynomial of coordinate functions with coefficients inOK, the ring of integers ofK. Chooseω ∈ OF satisfyingOF = Z+ωZ. (Later in (2.2), we specifyω explicitly.) Definen+mω := max(|n|,|m|). Note NF/Q(α)=O(α²). Using integrality ofψα, we can estimate the growth rate of the coefficients ofψα to beO(α²logα)in Theorem 6.4. Combining these results, we obtain, as our main result, an estimate for the time complexity (measured by the number of bit operations) to computeψα:

Theorem. Let µ be a constant such that the number of bit operations used for multiplication of twonbit integers isO(n^µ). Assume thatα∈OF is unbiased. Then, we can computeψα withO((α⁴logα)^µ)bit operations.

In order to avoid technical difficulties, we limit ourselves to the case where End(E)is the maximal order ofF. Under this restriction, End(E)is a Dedekind domain and, in particular, every non-zero ideal has a prime ideal decomposi- tion.

Generalized division polynomials are closely related to the problem of find- ing the explicit form of complex multiplications. Stark[12] obtained the following algorithm to compute explicit complex multiplication. Let℘be the Wei- erstrass℘-function associated toE. For a givenα ∈OF, his algorithm finds polynomialsu,vwith coefficients inKsuch that℘ (αz)=u(℘ (z))/v(℘ (z)) by the continued fraction approximation. Fromv, it is possible (in theory) to obtainψα. (For example,vis a constant multiple ofψ_α²ifNF/Q(α)is odd.) Al- though the growth rate of the number of arithmetic operations inKto obtainv is of polynomial order w.r.t.NF/Q(α), the time complexity w.r.t. bit operations is not known. Straightforward implementation suggests that its space complexity grows exponentially asNF/Q(α)tends to the infinity. Hence, Stark’s algorithm is infeasible in practice.

A better method is to perform Stark’s algorithm once forω. Assume that α := m+nω ∈ OF is given. Since the mtimes map and the ntimes map are expressed in terms of ordinal division polynomials, we obtain an explicit formula for complex multiplication byα. This is what was done by Abel [1] for the caseOF = Z[√

−1 ]. (Of course, no computational complexity analysis is given in this 19th century paper.) This method performs several arithmetic operations overK(X)whose time complexities w.r.t. bit operations are difficult to estimate because they involve greatest common divisor computations over K[X].

Although our main interest is an efficient algorithm to compute generalized division polynomials, some topics related to (1.1) have independent interests.

Durst [5] obtained (1.1) in the case whereγ in (1.1) is restricted to be a unit

(3)

and whereEis of the formY² = X³+b. Chudnovsky and Chudnovsky [4]

mentioned this relation in the context of elliptic curve primality and factoriz- ation tests, but no further relation than Durst [5] is given. As to integrality, in case that the class number ofF :=Q(√

−d )is one and thatd≥7, Joux and Morain [6, §2] proved that_d¹ψ^√_−d(Hdin their notation) is a polynomial of the X-coordinate function with coefficients inZ. This is better than Corollary 4.3 by a factor ofd. It is an open problem that for whichF orαa similar property holds. As to the space complexity, we note that McKee [8] gave a slightly better estimate than ours for ordinal division polynomials.

The rest of this paper is organized as follows. After giving some notation, we introduce the notion of unbiasedness in Section 2 and prove some basic properties. In Section 3, generalized division polynomials are defined and we prove the recurrence formula (1.1). Section 4 is devoted to the proof of the integrality of generalized division polynomials. Section 5, which is of different nature from the preceding sections, considers the space complexity on arithmetic operations onOK. Finally in Section 6, we prove our main result Theorem 6.6.

Notation. LetEbe an elliptic curve given by (1.2) Y²=X³+aX+b

with algebraic integersaandb. TheX-coordinate function andY-coordinate function are denoted by ξ andη, respectively. The point at infinity ofE is denoted byO. We useτ := −ξ/ηas a local parameter atO unless otherwise noted. Throughout this paper, we assumeEadmits complex multiplication by the ringOF of integers of an imaginary quadratic fieldF. PutK:=F (a, b). Forα ∈ OF, there is a unique endomorphism [α] ∈ End(E) satisfyingτ ◦ [α]=ατ+O(τ²). The map [·] is a ring isomorphism (see e.g. Silverman[11, Prop. II.1.1]). For an idealᑾofOF, we put

E[ᑾ] := {P ∈E: [α]P =O for all α ∈ᑾ}.

It is proven in Silverman[11, Prop. II.1.4] thatE[ᑾ] is a freeOF/ᑾmodule of rank 1. In particular, #E[ᑾ] = N(ᑾ)whereN(·)is the norm of an ideal.

By a prime ideal, we mean a non-zero prime ideal. The principal ideal ofOF

generated byα ∈ OF is denoted byαF. For simplicity, we writeE[αF] asE[α]. ForA ∈ Eandf ∈ K(E), we denote the order of zero off atA by ord_Af, whereas for a prime idealᒍof a Dedekind domainRandα ∈R, we understand ord_ᒍaas an additiveᒍ-adic valuation ofa. These two usages of ord are clearly distinguished by context.

(4)

Acknowledgements. Universitet i Tromsø (Norway), Aarhus universitet (Denmark), and Institut National de Recherche en Informatique et en Auto- matique (France) are gratefully thanked for their hospitality and for good re- search environments. The author would like to thank Professor François Mo- rain at École Polytechnique for valuable discussion.

2. Unbiased Ideals

In this section, we introduce the notion of unbiased groups and unbiased ideals.

Then we obtain some basic properties of unbiased ideals.

Deﬁnition2.1. A finiteAbelian groupGis said to beunbiasedif

g∈Gg=0.

Note that unbiasedness depends only on the isomorphism classes of Abelian groups.

Lemma2.2. LetGbe a finite Abelian group.

(1) Assume that G = G1 ⊕G2 where gcd(#G1,#G2) = 1. Then G is unbiased if and only if bothG1andG2are unbiased.

(2) The groupGis unbiased if#Gis odd.

(3) Assume that#Gis even. ThenGis unbiased if and only ifGcontains a subgroup isomorphic toZ/2Z⊕Z/2Z.

Proof. (1) Observe

g∈G

g =

g1∈G1

g2∈G2

(g¹, g²)=

#G²

g1∈G1

g¹,#G¹

g2∈G2

g²

.

Hence “if part” is obvious. To prove converse, note that(#G²)a=0 fora∈G¹ impliesa=0 since #G2is prime to #G1. Thus,G1is unbiased. Unbiasedness ofG2follows from the same way.

(2) Since

g∈Gg=

−g∈G−g= −

g∈Gg, we have

(2.1) 2

g∈G

g=0.

Multiplying ^#^G+₂ ¹ ∈Z, we have the assertion.

(3) Due to (1) and (2), we may assume thatGis isomorphic toZ/2ⁿ¹Z⊕· · ·⊕

Z/2ⁿ^rZwherer ∈ Nandn1, . . . , nr ∈ N. By a straightforward computation, we see that the latter group is unbiased if and only ifr ≥ 2. Assume thatG contains subgroup which is isomorphic toZ/2Z⊕Z/2Z. ThenGcontains at least three elements of order two. HenceG cannot be cyclic, which means

(5)

r ≥2. ThereforeGis unbiased. On the other hand, in case ofr ≥2, the group Z/2ⁿ¹Z⊕ · · · ⊕Z/2ⁿ^rZcontains a subgroup isomorphic toZ/2Z⊕Z/2Z. So doesG.

Deﬁnition2.3. We say an idealᑾofOFisunbiasedifᑾis the zero ideal or E[_ᑾ] is an unbiased subgroup ofE. An elementαofOF is said to beunbiased if the principal ideal generated byαis unbiased.

Lemma2.4. Let_ᑾand_ᑿbe ideals ofOF. The following properties hold:

(1) E[ᑾ+ᑿ]=E[ᑾ]∩E[ᑿ].

(2) If_ᑾ+ᑿ=OF, thenE[ᑾ]⊕E[ᑿ]is isomorphic toE[ᑾᑿ]under the map ϕdefined byϕ(P, Q):=P +Q.

Proof. (1) Obviously, E[ᑾ+ᑿ] ⊂ E[ᑾ] andE[ᑾ+ᑿ] ⊂ E[ᑿ]. Hence E[_ᑾ+ᑿ] ⊂ E[_ᑾ]∩E[_ᑿ]. Letγ ∈ ᑾ+ᑿ. Takeα ∈ ᑾandβ ∈ ᑿsatisfying α+β =γ. Then for anyP ∈E[ᑾ]∩E[ᑿ] it holds that [γ]P =([α]+[β])P = O, which impliesP ∈E[ᑾ+ᑿ].

(2) LetP ∈E[ᑾ] andQ∈E[ᑿ]. SinceOFis commutative,P+Q∈E[ᑾᑿ].

We proveϕ is surjective. By the assumptions, there existα ∈ ᑾand β ∈ ᑿ such thatα+β = 1. For anyA∈ E[_ᑾᑿ], we have A= [β]A+[α]Awith [β]A ∈ E[ᑾ] and [α]A ∈ E[ᑿ]. Therefore, ϕis surjective. Then ϕ must be injective because #E[ᑾᑿ]=N(ᑾᑿ)=#E[ᑾ]#E[ᑿ].

Theorem2.5. Let_ᑾbe an ideal ofOF. Then_ᑾis unbiased if and only if either2F|ᑾ(i.e.2F ⊃ᑾ) orN(ᑾ)is odd.

Proof. The assertion clearly holds for the zero ideal. In what follows, we assume thatᑾis not the zero ideal. The if part is a direct consequence of Lemma 2.2. To prove converse, we have to show thatᑾis a biased ideal if 2|N(ᑾ)and 2F ᑾ. We consider the following three cases.

(i) In case that 2 remains prime inOF: Any ideal ofOF with even norm is divisible by2F, hence there is nothing to prove.

(ii) In case that 2 ramifies: Let2F =ᒍ². Then, there exists a non-negative integereand an idealᑿwhose norm is odd such thatᑾ =ᒍ^eᑿ. But ife = 0, then N(ᑾ) is odd and if e ≥ 2, then 2F|ᑾ. Therefore e = 1 and hence E[_ᑾ]=E[_ᒍ]⊕E[_ᑿ]. Moreover, #E[_ᒍ]=2 and #E[_ᑿ] is odd. SinceE[_ᒍ] is biased,E[ᑾ] is also biased.

(iii) In case that 2 splits: By the similar observation as above,ᑾdecomposes asᑾ = ᒍêᑿwheree ≥ 1,ᒍis one of prime ideals dividing2F andᑿis an ideal of odd norm. Therefore,E[ᑾ]= E[ᒍê]⊕E[ᑿ]. Since 2 splits, we have E[_ᒍê]∼=OF/ᒍê ∼=Z/2êZ. HenceE[_ᒍê] is biased and so isE[_ᑾ].

Corollary2.6. Letα∈OF. Thenαis unbiased if and only if either2|α inOF orNF/Q(α)is odd.

(6)

Corollary2.7.Let_ᑾand_ᑿbe unbiased ideals. Then_ᑾᑿis also unbiased.

Corollary 2.8. Let d be a square free positive integer such that F = Q(√

−d ). Put

(2.2) ω:=







√−d (−d ≡2,3 mod 4),

−1+√

−d

2 (−d ≡1 mod 4). Letmandnbe integers.

(1) In case ofd≡1 mod 4,m+nωis unbiased except form≡n≡1 mod 2.

(2) In case ofd ≡2 mod 4,m+nωis unbiased except form≡ 0 mod 2 andn≡1 mod 2.

(3) In case ofd ≡3 mod 8, any element ofOF is unbiased.

(4) In case ofd≡7 mod 8,m+nωis unbiased if and only ifn≡0 mod 2.

Proof. This corollary follows from Theorem 2.5 and the fact thatNF/Q(m+

nω)=m²+n²dford ≡1,2 mod 4 andNF/Q(m+nω)=m²−mn+¹^+d₄ n² ford ≡3 mod 4. Note 2 ramifies in case of (1) and (2), remains prime in case of (3), and splits in case of (4).

Remark2.9. The condition2F|ᑾcannot be replaced by 4|N(ᑾ). Indeed, letd≡7 mod 8 and letᒍbe a prime ideal dividing2F. Then, the idealᒍ²is biased and its norms is 4.

3. Generalized Division Polynomials

First we introduce generalized division polynomials and prove recurrence formulas among them. Our definition is straightforward analogue of a definition of ordinal division polynomials (see e.g. Cassels [3, Formulary]). For simplicity, we writeNF/Q(α)asN(α)forα ∈OF. To begin with, we recall a condition on a divisor which comes from a rational function. LetD:=_n

i=1ai[Pi] be a divisor on an elliptic curveE. Then there exists a rational functionf onE whose divisor isDif and only if_n

i=1ai = 0 and_n

i=1aiPi = O (see e.g.

Silverman [10, Cor. III.3.5]). Therefore, for a finite subgroupGofD, there exists a rational functionf onEsatisfying div(f )=

P∈G[P]−#G[O] if and only ifGis an unbiased group. Similarly, forα ∈OF − {0}, there exists a rational functionf onEsatisfying

(3.1) div(f )=

P∈Ker[α]

[P]−N(α)[O]

(7)

if and only ifαis an unbiased endomorphism. However, a divisor determined a rational function only up to constant multiple. We specify this constants as follows.

Deﬁnition3.1. Letα ∈ OF be a non-zero unbiased element. Define the α-th division polynomialψα by divψα =

P∈Ker[α][P]−N(α)[O] and the normalization condition

(3.2) ψα =(−1)^N(α)−¹ατ^−N(α)+¹+ · · ·.

We also define an auxiliary functionψ˜α for any α ∈ OF by conditions divψ˜α =

P∈Ker[α]2[P]−2N(α)[O] andψ˜α = α²τ⁻²^N(α)+²+ · · ·. Since (2.1) holds for any finite group, such function exists and it holds thatψ˜α =ψ_α² for unbiasedα. By convention, we putψ0:=0 andψ˜0:=0.

Example 3.2. For the curve Y² = X³+5X, we seeψ2+√

−1 is a constant multiple ofξ²+2−√

−1 by straightforward computation (or Stark’s algorithm). Sinceξ =τ⁻²−5τ²+O(τ⁶), we have

ψ2+√

−1=(2+√

−1)ξ²+5

=(2+√

−1)τ⁻⁴−15−10√

−1+O(τ⁴).

Remark3.3. In caseα ∈ N, ourψα coincides with the notation used in [10, Exercise 3.7]. For a unitεofOF, we seeψε=ε(a constant function).

Lemma 3.4. Let α be an unbiased element. In case that N(α) is odd, ψα ∈ K[ξ] and deg_ξψα = (N(α)− 1)/2. Otherwise, _η¹ψα ∈ K[ξ] and deg_ξ ¹_ηψα

=(N(α)−4)/2.

Proof. Since Ker[α] is defined over K (recall K ⊃ F), there is f ∈ K(E)satisfying (3.1). Noting ξ ∈ K((τ))and η ∈ K((τ)), we see thatf is expanded asa−N(α)+1τ^−N(α)+¹+ · · ·witha−N(α)+1 ∈ K. Threfore, there exists a constantc ∈ K^× satisfying ψα = cf, which impliesψα ∈ K(E). Since [−1](Ker[α])=Ker[α], there exists constantcsatisfyingψα◦[−1]= cψα. Noteτ ◦[−1] = −τ. Therefore ψα ◦[−1] = ψα for odd N(α) and ψα◦[−1]= −ψαfor evenN(α). Since [−1] is the unique non-trivial element of Gal(K(E)/K(ξ)), we seeψα ∈ K(ξ)for oddN(α)and ¹_ηψα ∈ K(ξ)for evenN(α). However they are regular outside of{O}. Hence we see they are polynomials ofξ. The assertions on degree follows from ord_Oξ = −2.

Lemma3.5. Letαandβbe non-zero unbiased elements ofOF. Then ψαβ =(ψα ◦[β])·ψ_β^N(α).

(8)

Proof. Since char(K)= 0, every endomorphism is separable, hence un- ramified (Silverman [10, III.4.10(c)]). By a straightforward computation, we see divψαβ =div (ψα ◦[β])·ψ_β^N(α)

. Indeed,

divψαβ =

P∈Ker[α]◦[β]

[P]−N(αβ)[O]

=[β]^∗

P∈Ker[α]

[P]

−N(αβ)[O]

=[β]^∗(divψα+N(α)[O])−N(α)N(β)[O]

=div([β]^∗ψα)+N(α)

P∈Ker[β]

[P]

−N(α)N(β)[O]

=div(ψα◦[β])+N(α)divψβ.

Thus there exists a constantc∈K^×satisfyingψαβ =c(ψα◦[β])·ψ_β^N(α). By definition,

ψαβ =(−1)^N(αβ)−¹αβτ^−N(α)+¹+ · · · while

ψα =(−1)^N(α)−¹ατ^−N(α)+¹+ · · · ψα◦[β]=(−1)^N(α)−¹α(βτ+ · · ·)^−N(α)+¹

=(−1)^N(α)−¹αβ^−N(α)+¹τ^−N(α)+¹+ · · · ψ_β^N(α)=((−1)^N(β)−¹βτ^−N(β)+¹+ · · ·)^N(α)

=(−1)^{N(αβ)−N(α)}β^N(α)τ−N(αβ)+N(α)+ · · ·. Hencec=1.

The proof of the next proposition is more or less the same as the proof for the ordinal division polynomials and is already outlined in Cassels [3, Formulary].

However, in case thatα andβ ∈ OF satisfiesα+βF + α−βF = OF, the functionψα+βψα−β have a double pole. We need to handle (at least) this case separately, which is omitted in [3].

Proposition3.6. Letαandβbe non-zero elements ofOF such thatα+β andα−βare unbiased. Then

ξ◦[α]−ξ◦[β]= −ψα+βψα−β

ψ˜αψ˜β .

(9)

Proof. The assertion is obvious in case ofα = ±β. Assumeα = β and α= −βand consider the functionϕdefined by

ϕ:=(ξ◦[α]−ξ◦[β]) ψ˜αψ˜β

ψα+βψα−β. We show thatϕhas no pole. It is expanded as

((α⁻²−β⁻²)τ⁻²+ · · ·)(α²τ⁻²^N(α)+²+ · · ·)(β²τ⁻²^N(β)+²+ · · ·) ((−1)^N(α+β)−¹(α+β)τ^−N(α+β)+¹+ · · ·)

·((−1)^{N(α−β)−}¹(α−β)τ^{−N(α−β)+}¹+ · · ·) at the point at infinity. Noting

(3.3) N(α+β)+N(α−β)=2N(α)+2N(β), we see thatϕis expanded as

(3.4) ϕ= −1+O(τ)

atO. ForP ∈E[α]−E[β], we have ord_P(ξ◦[α]−ξ◦[β])= −2, ord_P(ψ˜α)= 2, ord_P(ψ˜β) = 0, ord_P(ψα+β) = ord_P(ψα−β) = 0. Thus ord_Pϕ = 0. The similar argument applies forP ∈E[β]−E[α]. LetP ∈E[α]∩E[β]− {O}

and letVP be the translation byP map (i.e.VP(A)=P +A). Observe ξ ◦[α]◦V−P =α⁻²(τ◦V−P)⁻²+ · · ·.

Butτ◦V−P is a local parameter atP and [α]◦V−P =[α]. The same formula holds forβ. Usingα= ±β, we see ord_P(ξ◦[α]−ξ◦[β])= −2. On the other hand, ord_P(ψ˜α)= 2, ord_P(ψ˜β)= 2, ord_P(ψα+β)=1 and ord_P(ψα−β)=1.

Hence ord_Pϕ =0.

Now we consider a possible pole of ϕoutside ofE[α]∪E[β]. It comes fromψα+βψα−β, hence it lies inE[α+β]∪E[α−β]−{O}. We consider three sub-cases. In caseP ∈E[α+β]−E[α−β], we have [α](P ) = −[β](P ), which impliesξ([α](P )) = ξ([β](P )). By definition, ord_Pψα+β = 1 and ord_P ψα−β = 0. Hence ord_Pϕ ≥ 0. The same is true forP ∈ E[α−β]− E[α + β]. Finally, assume P ∈ E[α + β]∩E[α− β] and P = O. By the former condition, 2[α](P ) = O and 2[β](P ) = O. However, we have assumed [α](P ) = O and [β](P ) = O. Thus [α](P ) and [β](P ) are non- trivial 2-torsion points ofE. Since

ξ([α](A−P ))=ξ(−[α](A−P ))=ξ([α](−A)+[α](P ))

=ξ([α](−A)−[α](P ))=ξ([α](−A−P ))

(10)

for allA∈E, we see thatξ◦[α]◦V−Pis an even function and that the expansion ofξ◦[α] atPwith respect to the local parameterτ◦V−Pconsists of even degree terms. The same holds for [β]. Therefore, ξ([α](P )) = ξ([β](P )) means ord_P(ξ◦[α]−ξ◦[β])≥2. On the other hand, ord_Pψα+β =ord_Pψα−β =1.

Consequently, ord_P ϕ≥0.

Sinceϕ has no poll at all, it is a constant function and its value is−1 by (3.4). This completes the proof.

Corollary3.7. Letα,β,γ be elements ofOF such thatα±β,β±γ, γ ±αare unbiased. Then

ψ˜βψα+γψα−γ − ˜ψαψβ+γψβ−γ =ψα+βψα−βψ˜γ.

Proof. Again, the assertion is trivial forαβγ =0. Otherwise, this follows from Proposition 3.6 and the identity(ξ◦[α]−ξ◦[γ])−(ξ◦[β]−ξ◦[γ])= ξ◦[α]−ξ ◦[β].

Letωbe as in (2.2). Forα∈F, we put (3.5) α:=max(|s|,|t|) wheres,t ∈Qare uniquely determined byα=s+tω.

Proposition3.8. Letα ∈OFbe unbiased. Then, there exist seven unbiased elementsβ1, . . . , β6∈OF,δ∈ {1,2, ω,1+ω,1−ω,1+2ω}andt ∈ {0,1,3} satisfying the following conditions:

(1) ψα =(ψ_β²₁ψβ2ψβ3−ψ_β²₄ψβ5ψβ6)/ψ_δ^t (2) βi ≤ ¹₂α +2for alli

Explicitly, the following formulas holds foru∈OF: In case ofd≡3 mod 4,

(3.6)

ψ2u=ψu(ψ_u−² 1ψu+2−ψ_u+² 1ψu−2)/ψ2, ψ²u+1=ψ_u³ψu+2−ψ_u+³ 1ψu−1,

ψ²u+ω =(ψ_u³ψu+2ω−ψ_u+ω³ ψu−ω)/ψ_ω³,

ψ2u+1+ω =(ψ_u³ψu+2+2ω−ψ_u+³ 1+ωψu−1−ω)/ψ1³+ω. Letu=m+nωwithm, n∈Z. In case ofd≡7 mod 8, (3.7)

ψ²u=ψu(ψ_u−² 1ψu+2−ψ_u+² 1ψu−2)/ψ² (n: even),

ψ²u=(ψ_u−ω² ψu+1+ωψu−1+ω−ψ_u+ω² ψu+1−ωψu−1−ω)/ψ²ω (n: odd), ψ²u+1=ψ_u³ψu+2−ψ_u+³ 1ψu−1 (n: even),

ψ²u+1=(ψ_u−ω² ψu+2+ωψu+ω−ψ_u+² 1+ωψu+1−ωψu−1−ω)/ψ¹+2ω (n: odd).

(11)

In case ofd ≡1 mod 4, in addition to (3.7), we have (3.8)

ψ2u+ω=(ψ_u³ψu+2ω−ψ_u+ω³ ψu−ω)/ψ_ω³ (m: even),

ψ2u+ω=(ψ_u−² 1ψu+1+2ωψu+1−ψ_u+² 1+ωψu−1+ωψu−1−ω)/ψ_ω³ (m: odd).

Similarly, in case ofd≡2 mod 4, we have (3.7) and (3.9)

ψ2u+1+ω =(ψ_u³ψu+2+2ω−ψ_u+³ 1+ωψu−1−ω)/ψ1³+ω (m≡nmod 2), ψ2u+1+ω =(ψ_u+ω³ ψu+2−ω−ψ_u+³ 1ψu−1+2ω)/ψ1³−ω (m≡nmod 2).

Proof. Recurrence formulas (3.6)–(3.9) are immediate consequence of Co- rollary 3.7, which implies the existence ofβ¹, . . . , β⁶,δandt. Unbiasedness ofβ1, . . . , β6andδfollows from Corollary 2.8. Finally, the assertion (2) is a consequence of the inequality

x+y ≤ 1

22x+z +y− z 2

for anyx, y, z∈F.

4. Integrality of Division Polynomials

LetT be an indeterminate. For an unbiased elementα∈OF, define6α(T )∈ K[T] by

ψα =6α(ξ) (NF/Q(α)is odd), 1

ηψα =6α(ξ) (NF/Q(α)is even).

In this section, we prove that6α ∈ OK[T]. For a nonzero idealᑾofOF, we

put 7ᑾ(T ):=

P∈E[_ᑾ]−{O}

(T −ξ(P )).

As before, we write7αF as7α forα∈OF. Note (4.1) div7ᑾ(ξ)=2

P∈E[_ᑾ]

[P]−N(ᑾ)[O]

and hence

(4.2) 7α(T )=

α⁻²6α(T )² (NF/Q(α)is odd), α⁻²C(T )6α(T )² (NF/Q(α)is even).

(12)

Here,C(T ):=T³+aT +bwitha,bdefined in (1.2). Let_ᑪbe a prime ideal ofOKlying above a prime idealᒍofOF. Recall thatᑪ-adic valuation has the standard extension toK(T ) in the sense of Zariski and Samuel[13, §IV.13], namely,

ord_ᑪ n

i=0

αiTⁱ

:= min

0≤i≤nord_ᑪαi

onK[T]. In order to prove6α(T )∈OK[T], it is suffice to prove ord_ᑪ7α(T )≥ −2 ord_ᑪα

for any prime idealᑪ. The fact that #E[m]=m²form∈Ncause a difficulty to the proof of the above formula. LetAbe an torsion point ofEof orderp^m. Then, as is well known (see e.g. Silverman [10, Th. VII.3.4]),

(4.3) ord_ᑪξ(A)≥ −2 ord_ᑪp p^m−p^m−¹. This inequality implies, for example,

ord_ᑪ7p(T )≥ −2p²−1 p−1 ord_ᑪp

which is insufficient for our purpose. This problem might be solved by the sharper inequality obtained by Oshikawa [9, Th. 4] with fine arguments on hight of the formal group associated the reduction ofEatᑪ(including bad reductions). Here we employ an another method. We utilize the fact that 6n(T ) ∈ OK[T] for n ∈ N. (This is well known. See e.g. Silverman [10, Exercise 3.7]. Recall that in (1.2), we assumed that a and b are algebraic integers.)

For a prime idealᒍof the Dedekind domainRand a non-zero idealᑾof a subring ofR, we denote by ord_ᒍᑾthe largest integeresuch thatᒍ^edividesRᑾ. Lemma4.1.Let_ᒍbe a prime ideal ofOF and_ᑪa prime ideal ofOKlying above_ᒍ. Let_ᑾbe an ideal ofOF and pute := ord_ᒍᑾ. Then, ord_ᑪ7ᑾ(T ) = ord_ᑪ7ᒍ^e(T ).

Proof. There exists an idealᑿof OF such thatᑾ = ᒍ^eᑿ. RecallE[ᑾ] = E[_ᒍ^e]⊕E[_ᑿ] by Lemma 2.4. Thus

(4.4) ord_ᑪ7ᑾ(T )=

P∈E[_ᒍ^e], Q∈E[_ᑿ] P=O orQ=O

ord_ᑪ(T −ξ(P +Q))

(13)

We show ord_ᑪξ(P+Q)≥0 forQ=O. Letu∈ᑿ−ᒍ. PutA:=P+Qand assume ord_ᑪξ(A) <0. Hence,Abelongs to the group of points of the formal group associated toEover theᑪ-adic completion ofKatᑪ. Letr ∈ ᒍ^e be arbitrary. Since End(E)is commutative, [u][r]A=[u][r]P +[r][u]Q= O. However, uis a ᑪ-adic unit and thus [r]A = O. This implies A ∈ E[ᒍ^e].

Hence,Q= P −A ∈ E[_ᒍ^e], which contradicts toQ = O by Lemma 2.4.

Therefore, ord_ᑪ(T −ξ(P +Q)) = 0 forQ= O and the right hand side of

(4.4) is

P∈E[ᒍ^e]−{O}

ord_ᑪ(T −ξ(P ))=ord_ᑪ7ᒍ^e(T ).

Proposition4.2.Let_ᑾ be a non-zero ideal ofOF. Then, ord_ᑪ7ᑾ(T ) ≥

−2 ord_ᑪᑾfor a prime ideal_ᑪofOK.

Proof. Put ᒍ := OF ∩ᑪ ande := ord_ᒍᑾ. Letp be the prime number belonging toᒍ. By the preceding lemma, we have only to prove

(4.5) ord_ᑪ7ᒍ^e(T )≥ −2eord_ᑪᒍ. We consider three cases:

In case thatpsplits: we have ord_ᑪᒍ = ord_ᑪp andE[ᒍê] ∼= Z/pêZ. For 1≤m≤ e, there are exactlyp^m−p^m−¹points inE[ᒍê] whose order isp^m. By (4.3),

ord_ᑪ7ᒍ^e(T )=

P∈E[_ᒍ^e]−{O}

min(0,ord_ᑪξ(P ))

≥ e m=1

(p^m−p^m−¹)−2 ord_ᑪp

p^m−p^m−¹ = −2eord_ᑪᒍ. In case thatpremains prime: Noting (4.2) and6p^e(T )∈OK[T], we have

ord_ᑪ7ᒍê(T )= −2 ord_ᑪpê+2 ord_ᑪ6pê(T )≥ −2eord_ᑪᒍ.

In case thatp ramifies: Assume first thateis even. Then,ᒍ^e = p^e/²F and assertion follows the same argument as above. Letebe odd. In case ofe=1, we haveE[ᒍ] ∼= Z/pZand (4.5) holds by the same reason as the split case.

Now assumee ≥ 3 and putn:= (e−1)/2 andq := pⁿ. As is well known ξ◦[q] = ξ−ψq+1ψq−1/ψ_q²(which can also be proved by Proposition 3.6).

Then, by a similar proof to Lemma 3.5, we have

7ᒍ^e(ξ)=q²^(p−¹⁾7ᒍ(ξ◦[q])7q(ξ)^p=q⁻²7ᒍ(ξψ_q²−ψq−1ψq+1)ψ_q².

(14)

Thus,

7ᒍ^e(T )=

q⁻²7ᒍ(Gq(T ))6q(T )² (p=2), q⁻²7ᒍ(Gq(T ))C(T )6q(T )² (p=2), where

Gq(T ):=

T 6q(T )²−C(T )6q−1(T )6q+1(T ) (p=2), T C(T )6q(T )²−6q−1(T )6q+1(T ) (p=2).

Because6i(T )∈OK[T] for anyi ∈N, the polynomialGq(T )also belongs toOK[T]. Thus,

ord_ᑪ7ᒍ^e(T )≥ −2 ord_ᑪq+ord_ᑪ7ᒍ(T )= −2eord_ᑪᒍ.

Corollary 4.3. Let α ∈ OF be unbiased. Then6α(T ) ∈ OK[T] and ψα ∈OK[ξ , η].

5. Space Complexity for Polynomial Arithmetic Operations

We estimate space complexities for arithmetic operations onOK[T] whereT is an indeterminate. Estimates for additions, subtractions and multiplication are simple. However, divisions give rise to a difficulty. For an integernand its divisorm, the bit size of the quotient n/mis not greater than that ofn. Such a property does not holds forOK[T]. In order to clarify an obstacle, let us consider the integer ringZ[√

2 ] of therealquadratic fieldQ(√

2). Then,

√2− 1 is a unit and (√

2−1)ⁿ divides 1 for any n ∈ N. But bit size of 1/(√

2−1)ⁿis, in any sense, unbounded asntends to infinity because finitely many bits can represent finitely many elements inZ[√

2 ]. This suggests that we need to utilize the fact thatF is an imaginary quadratic field in order to bound the space complexity. Our method is based on the fact that the bit size of α ∈ OK is not that different fromLK(α) := max_ilog₂NF/Q(ai)where α=

iaiθⁱ withK=F (θ).

First we note a technical lemma whose proof is given in Appendix. Although it looks like an abstract nonsense, such an abstraction is necessary because it is used twice in subsequent proofs with different coefficient rings. LetR be an integral domain. For polynomialsf andg ∈R[T] we denote by quo(f, g) (resp. rem(f, g)) the quotient (resp. remainder) of the divisionf/g in k[T] wherekis the field of fractions ofR.

Lemma5.1. LetRbe an integral domain. LetL∈Map(R,R∪ {−∞})be a map satisfying the following conditions.

(5.1) L(0)= −∞.

(15)

(5.2) There exists a constantc1≥0such thatL(α±β)≤max(L(α), L(β))+

c¹for allα, β ∈R.

(5.3) There exists a constantc2≥0such thatL(αβ)≤L(α)+L(β)+c2for allα, β ∈R.

For such a mapL, we defineL˜ ∈Map(R[T],R∪ {−∞})by (5.4) L˜

n i=0

aiTⁱ

:= max

0≤i≤nL(ai).

Then, for polynomialsf, g ∈R[T], the following inequalities hold.

(a) L(f˜ ±g)≤max(L(f ),˜ L(g))˜ +c¹.

(b) L(fg)˜ ≤ ˜L(f )+ ˜L(g)+c1min(degf,degg)+c2. (c) Assumeg=0and

(5.5) L(lc(g)α)≥L(α)

for allα ∈R. Assume alsoquo(f, g)∈R[T]. Putc3 := max(L(g)˜ + c1+c2,0)andδ:=max(degf −degg,−1). Then, we have

(5.6) L(˜ quo(f, g))≤ ˜L(f )+δc3

and

(5.7) L(˜ rem(f, g))≤ ˜L(f )+(δ+1)c3.

We now consider the computational complexity of arithmetic operations on OK[T]. Letω be as in (2.2). Put ν := [K : F] and take θ ∈ K satisfying K =F (θ). Later, we requireθ to be an element ofOK, but for nowθ is not necessarily an algebraic integer. LetH be the monic minimal polynomial of θoverF. It is important to constructKas a simple extension overF, not that overQ. DefineLF ∈Map(F,R∪ {−∞})andLK ∈Map(K,R∪ {−∞})by

LF(α):=

log₂NF/Q(α) (α=0)

−∞ (α=0) and

LK

ν−1 i=0

aiθⁱ

:= max

0≤i<νLF(ai),

respectively. LetL˜F be the extension ofLF toF[T] as was done in (5.4).

(16)

Theorem5.2. Forα, β ∈Kandc∈F, we have LK(cα)=LF(c)+LK(α), LK(α+β)≤max(LK(α), LK(β))+2, LK(αβ)≤LK(α)+LK(β)+(ν−1)(L˜F(H)+4).

Proof. Put P := {f ∈ F[T] : deg(f ) < ν}. Determine A and B ∈ PF by α = A(θ) and β = B(θ), respectively. By definition, LK(α) = L˜F(A)andLK(β) = ˜LF(B). Since T is mapped toθ by the mapF[T] → F[T]/HF[T] ∼= K, we have LK(α + β) = ˜LF(A + B), LK(αβ) = L˜F(rem(AB, H ))and LK(cα) = ˜LF(cA). On the other hand, it is obvious thatLF satisfies (5.1) and (5.3) withc2=0. By (3.3), we have

LF(α+β)≤max(LF(α), LF(β))+2

for α, β ∈ F, which shows that LF satisfies (5.2) with c1 = 2. Hence Lemma 5.1 is applicable toLF and the first two assertions are proved. Since H is monic, the condition (5.5) forL = LF andg = H is clearly satisfied.

Thus, the last assertion follows from Lemma 5.1.

Corollary5.3. LetL˜K ∈Map(K[T],R∪ {−∞})be the extension ofLK

as in (5.4).

(a) There exists a constantc4 > 0such thatL˜K(f +g) ≤ max(L˜K(f ), L˜K(g))+c4for allf, g∈K[T].

(b) There exists a constantc5>0such thatL˜K(fg)≤ ˜LK(f )+ ˜LK(g)+ (min(degf,degg)+1)c⁵for allf, g∈K[T].

(c) Let g ∈ K[T] and assumelc(g) ∈ OF. Then, there exist a constant c6> 0(depending ong) such thatL˜K(quo(f, g))≤ ˜LK(f )+δc6and that L˜K(rem(f, g)) ≤ ˜LK(f )+ (δ+1)c6 for all f ∈ K[T] where δ:=max(degf −degg,−1).

Proof. The corollary is an immediate consequence of Lemma 5.1 and Theorem 5.2.

From now on, we assume θ ∈ OK and put D := [OK : OF[θ]]. We representα∈OKas aν-tuple(α0, . . . , αν−1)∈O_F^νwhereα=_ν−1

i=0αiθⁱ/D. Eachu∈ OF is represented as a pair of integers(m, n)determined byu = m+nωwhereωis defined as (2.2). On the other hand, we putSF(m+nω):= log₂(max(|m|,1))+log₂(max(|n|,1))+6 andSK(α):= _ν−1

i=0SF(αi). The valueSF(u)is considered to be the bit size to storeu ∈ OF (not including length ofmandn) by the data structure described as above.

(17)

Theorem5.4. There exist constantsc7>0andc8>0satisfying 1

2LK(α)−c7≤SK(α)≤νLK(α)+c8

for all non-zeroα ∈OK.

Proof. Let u := m+nω with m, n ∈ Zand α := _ν−1

i=0αiθⁱ/D with αi ∈ OF. Apparently, NF/Q(u) ≤ (d +3)max(m², n²). Hence, there is a constantc9such that log₂NF/Q(u)≤c9+2SF(u)for allu∈OF. Thus,

LK(Dα)= max

0≤i<νLF(αi)≤c9+2 max

0≤i<νSF(αi)≤c9+2SK(α).

The left hand side is not less thanLK(α) sinceD ∈ N. Conversely, m² ≤

4

3NF/Q(u)andn² ≤ ⁴₃NF/Q(u). These are obvious ford ≡ 3 mod 4 (recall F =Q(√

−d)). In case ofd≡3 mod 4, they follow from NF/Q(m+nω)=

m− n

2 2

+ d

4n²= d+1 4

n− 2 d+1m

2

+ d d+1m². andd ≥3. Hence, there exists a constantc10such thatSF(u)≤LF(u)+c10

for allu∈OF − {0}. We haveLF(αi)≤LK(α)+log₂Dfor all 0≤i < ν. Thus,

SK(α)≤

αi=0

(LF(αi)+c¹⁰)+6#{i:αi =0}

≤ν LK(α)+log₂D+c10+6 . This concludes the proof.

Using the above results, we have, for example, SK(αβ) ≤ 2ν(SK(α)+ SK(β))+O(1) forα, β ∈ OK − {0}. However, this is insufficient for our purpose. In the next section, we work withLK as much as possible and use Theorem 5.4 only once during the proof on a space complexity.

6. Complexity to Compute Generalized Division Polynomials

We give time and space complexities to compute6α(T )asαtends to infinity.

Recall that E is a fixed elliptic curve Y² = C(X) where C(T ) = T³ + aT +b (cf. (1.2)). We keep notation in the previous sections. Forf (T ) := _n

i=0αiTⁱ ∈ OK[T], we put σ (f ) := max0≤i<nSK(αi). Throughout this section, letµbe a constant such that the number of bit operations to multiply twonbit integers isO(n^µ)and that the number of arithmetic operations of a coefficient ring to multiply two polynomials of degree less thannisO(n^µ). In