自己準同型写像を用いた楕円曲線暗号の効率的なアルゴリズム

(1)

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

伯田, 恵輔

https://doi.org/10.15017/1398315

出版情報：Kyushu University, 2013, 博士（機能数理学）, 課程博士バージョン：

権利関係：Fulltext available.

(2)

Ecient Algorithms for Elliptic Curve Cryptosystems using Endomorphisms

Keisuke Hakuta

Graduate School of Mathematics Kyushu University

A thesis submitted for the degree of

Doctor of Functional Mathematics

(3)

c

i

(4)

This thesis is dedicated to my wife and my sons for their support.

(5)

Acknowledgements

It would not have been possible to write this dissertation without the assistance, patience, and support of many individuals. I would like to express my deepest appreciation to all those who provided me the possibility to complete this dissertation.

I would like to extend my gratitude rst and foremost to Professor Tsuyoshi Takagi for his supervision, guidance and the continuous support during my research at Kyushu University.

Besides my advisor, deepest gratitude are also due to the members of my committee, Professor Hiroyuki Ochiai, Professor Kouichi Sakurai, Associate Professor Yasuro Gon, without whose insightful comments, hard questions, and especially the revision process that has lead to this document, this study would not have been successful.

I would also like to extend my appreciation to Hisayoshi Sato for his immense and continued support, valuable advice, technical and non- technical assistance, and encouragements in a number of ways.

I would like express my gratitude to all the current and former Hi- tachi crypto team: Eriko Ando, Soichi Furuya, Yasuo Hatano, Kota Ideguchi, Shugo Mikami, Kunihiko Miyazaki, Ken Naganuma, Kat- suyuki Okeya, Toru Owada, Hisao Sakazaki, Dai Watanabe, and Masayuki Yoshino, for their support and many technical and non-technical dis- cussions. I also would like express my gratitude to Hirotaka Yoshida for not only his support and many technical and non-technical discus- sions, but also for the English correction of this thesis.

I am grateful for the Hitachi directors who have supported me, in- cluding Kazuo Takaragi, Yasuko Fukuzawa, Seichi Susaki, Takahiro Fujishiro, Masahiro Mimura, and Tadashi Kaji.

(6)

Last but not the least, I would like to thank my family members Tatsumi, Megumi, and Yusuke for encouragement, and my wife Aki, and my sons Sosuke and Rensuke for their endless support, patience and extreme understanding while I have pursued this degree.

(7)

List of Tables

3.1 Forms ofℓ digits ϕ-GNAF representations . . . 25

3.2 Forms ofℓ digits ϕ-rNAF representations . . . 36

3.3 The number of curve operations for each recoding method (q= 3) 41 3.4 The number of curve operations for each recoding method (q≥5) 41 3.5 The number ofFq^m-eld arithmetic operations (bit length of scalar = 192,224,256,384) and total number of multiplications (S = 0.8M, I/M = 8) for each recoding method . . . 42

3.6 Timings of the Finite Field Operations . . . 45

3.7 Timings of Recoding Methods . . . 45

3.8 Timings of Scalar Multiplications on F3-Koblitz Curve K(3,1)-173 (online precomputation case) . . . 46

3.9 Sample Parameters for F3-Koblitz Curves oft = 1 . . . 47

3.10 Sample Parameters for F3-Koblitz Curves oft = 1 . . . 48

4.1 Conversion of the τ-NAF into the τ-MLF (ℓ <6) . . . 70

4.2 Conversion of the τ-NAF into the τ-MLF (ℓ ≥6) . . . 71

5.1 Classication of elliptic curves of the formE_7,b . . . 83

5.2 Classication of elliptic curves of the formE_5,a . . . 89

5.3 Sample Parameters for the elliptic curvesE_5,a/F5 . . . 94

5.4 Sample Parameters for the elliptic curvesE_7,b/F7 . . . 96

5.5 Timings of the Finite Field Operations. . . 98

5.6 Estimate the computational costs of CE test and our test . . . 99

5.7 Values k_j and k_ω such that #S_j ≈2^k^bv,#S_E≈2^k^bv . . . 99

vii

(11)

LIST OF TABLES

5.8 the number of signatures N for which our method is faster than CE test . . . 100

viii

(12)

List of Figures

5.1 A typical IP camera surveillance system . . . 76

ix

(13)

Chapter 1 Introduction and Motivation

1.1 Introduction and Motivation

Nowadays, Information and communication technology (ICT) assists us in many areas of our lives (e.g. business, education, our personal lives, and so on). The role of ICT is becoming more and more important. The number and variety of ICT devices is growing rapidly and dierent types of devices are widely communicated with each other through dierent types of networks. ICT systems, however, may pose security risks such as spoong, tampering, repudiation, information disclosure, etc.

Public key schemes provide encryption, digital signature, and key exchange ca- pabilities. Moreover, some schemes have homomorphic properties, namely, these schemes allow anyone in possession of the public key to perform computations on encrypted data without decrypting it. Many public key schemes are based on the diculties of number-theoretic problems such as integer factoring problem, discrete logarithm problem in nite elds or elliptic curves, problem of solv- ing a multivariate polynomial system over a nite eld. In public key schemes, number-theoretic computations are the dominant operations. For instance, com- puting scalar multiplication (or point multiplication) is the most time consuming operation in elliptic curve cryptosystems (ECC for short). Therefore it is an important task to accelerate number-theoretic computations.

On the other hand, endomorphisms of algebraic varieties play an important

1

(14)

role in modern mathematics. For example, the endomorphisms on an elliptic curve play a central role in the arithmetic study of elliptic curves. Polynomial automorphisms play a key role in several open problems in ane algebraic geom- etry such as Jacobian conjecture, tame generators problem.

This thesis deals with endomorphisms of algebraic varieties. In the cryptographic community, endomorphisms of algebraic varieties are often used not only to improve the eciency of public key schemes, but also to evaluate the security of public key schemes. More precisely, in ECC the Frobenius endomorphism of an elliptic curve is especially attractive because of the fact that the Frobenius endomorphism can be computed very eciently. Roughly speaking, for a given subeld elliptic curve (i.e. an elliptic curve over a nite eld which are actually dened over some subeld), Frobenius expansions are special representations of element in the endomorphism ring as polynomials in the Frobenius endomorphism with cryptographically appropriate integer coecients. For the purpose of improve the performance, it is desirable to construct Frobenius expansions with low Hamming weight (i.e. the the number of nonzero coecients). In addition, theoretical analysis of eciency of Frobenius expansions with low Hamming weight may be important to explore the Hamming weight of other representations.

Frobenius expansions are also attractive for signature verication, especially, in batch verication (a method to verify multiple signatures simultaneously). Frobe- nius expansions are used in order to randomize the verication process and to improve the eciency. To use Frobenius expansions for batch verication, it is necessary to investigate some properties of Frobenius expansions.

The motivation for the results in this thesis comes from the importance to explore some properties of Frobenius expansions.

1.2 Contribution and Organization of the thesis

The rest of this thesis is organized as follows. Section 2 reviews some background. In Section 3, we propose ecient scalar multiplication algorithms for subeld elliptic curves of trace ±1. The results are extensions of Solinas's τ- adic non adjacent form (τ-NAF for short) on Koblitz curves. We also present implementation results of our new algorithms and previous methods.

2

(15)

In Section 4, we derive an explicit lower bound for the length of minimal Hamming weight τ-adic expamsions on Koblitz curves. We also give a new proof of the minimality of the Hamming weight of the τ-NAF on Koblitz curves. Fur- thermore, we classify a minimal lengthτ-adic expansion with minimal Hamming weight except for two special cases.

Finally, in Section 5, we present two ecient batch verication techniques suitable for verifying a limited number of signatures in real-time. Our method can only be applied to elliptic curve based signatures, and uses one of the two special families of elliptic curves.

3

(16)

Chapter 2 Background

This section provides necessary background on elliptic curves and public key cryptography.

2.1 Notation

Throughout this thesis, we use the symbols N,Z,Q,C,Fqto represent the natural numbers, the integers, the rational numbers, complex numbers, and a nite eld with q elements respectively, where q = p^r (r ∼ 1), p = char(Fq). For any eld k, we denote by p = char(k) the characteristic of the eld k. For a eld k, the n-dimensional projective space over k is denoted byPⁿ_k. For a positive integer n, we denote the residue class ring modulo n by Zn=Z/nZ. For a nite set S, we denote the cardinality of S by #S. Denote by Z_>0 the set of positive integers.

For x C, we denote by \x\the absolute value of x. We denote a by ¯a for any natural number a

For any non-zero complex number ψ C√}0, we denote ψ-adic expansion ₋₁

i=0c_iψⁱwithc_i Zby(c₋₁, . . . , c₀)_ψ, and denote the number of non-zeroc_i's by wt((c₋₁,×××, c₀)_ψ). The symbol `±' means a non-zero digit of ψ-adic expansions.

We call the length of the ψ-adic expansion. Let E be an elliptic curve dened over a nite eld Fq, φ : E ⇐E, (x, y)∪⇐ (x^q, y^q) be the q^th-power Frobenius map on E. We put t_m := q^m + 1 #E(Fq^m), t := t₁, and call t_m the trace of E(F_q^m). We can regard φ as a complex number which satises the characteristic

4

(17)

ϕ² tϕ+q=0 Fq^m

E #E(Fq^m) =hn h n P∈E(Fq^m) n A F

E(Fq^m)q^th E(Fq^m)

Ea τ

Ea D:=D2={0,±1}

a∈F2 D={0,±µ}

α Z[τ] α=∑_ℓ−1

i=0biτⁱbi∈D τ α α=∑_ℓ^′₋₁

i=0 ciτⁱ(ci∈D) τ α

τ α ℓτ (α) ℓ (α)

τ τ

D

ℓ >ℓ^′ cℓ^′= cℓ^′+1 = ···= cℓ−1=0 bℓ= bℓ+1 =

···= bℓ^′−1=0 max{ℓ,ℓ^′} ℓ

Sα:={i∈{0,1,...,ℓ 1}|bi̸=0} Tα:={i∈{0,1,...,ℓ 1}|ci̸=0}

k

k E k

P²_k

F(x,y,z) F(x,y,z)=y²z+(a1x+a3z)yz (x³+a2x²z+a4xz²+a6z³) O=(0,1,0)

E/K Z

(K)=0

p

X Fp FX:X →

X OX→ OX a∪→a^p

X

(18)

f:X → Y Fp FY◦f=f◦FX

x∈X FX(x)=x

0 1 {0,1}^∗

(G,E,D)

1ⁿ G

(e,d) G(1ⁿ) α∈{0,1}^∗

E D

Pr[D(d,E(e,α))=α]=1

E D

n (e,d)

G(1ⁿ)

E(e,α) α ∈{0,1}^∗

e D(d,β) β

d

(G,S,V)

(19)

1ⁿ G

(s,v) G(1ⁿ) α∈{0,1}^∗

S V

Pr[V(v,α,S(s,α))=1]=1

S V

n (s,v)

G(1ⁿ)

S(s,α) α

s V(v,α,β)=1 β

α v

α s α

v v

s

(20)

2. Bilinear pairing: Weil pairing and Tate pairing are well known in mathematics. In addition to these pairings, other pairings such as Ate pairing have been proposed to accelerate pairing computation and/or to construct new cryptographic primitives. Endomorphisms on (hyper-)elliptic curves are also used to construct bilinear pairings. For more details, see for instance [27].

3. Map to point hash function: Several public key schemes need a map to point hash function. The function maps a bit string of arbitrary length to a point on an elliptic curve dened over a nite eld. Eciently computable endomorphisms on elliptic curves play a central role in the construction of map to point hash functions.

4. Random point generation: In many public key schemes based on elliptic curves, it requires generation of a random point on an elliptic curve. For a given point P on an elliptic curve E(Fq), the standard method to generate a random point is to choose a random number r and to compute scalar multiplication rP. Some methods have been proposed in order to avoid the direct computation of scalar multiplication. For more details, see for instance [51].

8

(21)

Chapter 3 Ecient Arithmetic on Subeld Elliptic Curves over Small Finite Fields of Odd Characteristic

3.1 Introduction

Elliptic curve cryptosystems (ECC) were proposed in 1985 independently by Vic- tor Miller [56] and by Neal Koblitz [44]. Since ECC provide many advantages, for example, shorter key length and faster computation speed than those of RSA cryptosystems, ECC have been the focus of much attention. In ECC, each proto- col such as ECDH, EC-ElGamal, and ECDSA involves scalar multiplications for given points on an elliptic curve by positive integers. These multiplications have much eect on the eciency of the schemes, and many ecient methods have been proposed.

As one such method, the use of subeld elliptic curves (i.e. elliptic curves over nite elds which are actually dened over some subeld [12]) is especially attractive because by using the Frobenius maps, which is eciently computed, scalar multiplication on subeld elliptic curves can be performed much faster than that on curves over prime elds. Koblitz [46] suggested anomalous binary curves, and Müller [60] extended Koblitz's idea to achieve the Frobenius expansions over small elds of characteristic two. Smart [70] generalized Müller's result to elliptic

9

(22)

d∈Z[ϕ] d=∑_ℓ−1

i=0diϕⁱ q

Fq E ϕ q

E di∈{0,±1,...,±(q 1)/2} t ϕ (q,t)̸=(5,±4),(7,±5) ℓ

ϕ

r r

τ

τ τ

τ

τ w

(23)

τ

ϕ ϕ ϕr

r

{0,±1} {0,±1,...,±(q 1)/2}

τ

r τ

ϕ ϕr 3,5

ϕ ϕr

ϕr

ϕ ϕr

ϕ

ϕ ϕr w

r τ

τ ϕ

ϕ

(24)

ϕr

r

r rα

Dr,α

Dr,α:=

{{0,±1,...,±α} α<r, {0,±1,...,±α}\{±r,±2r,...,±⌊α/r⌋r}

r≥2 r

r

d d=∑_ℓ−1

i=0eirⁱ ei∈Dr,r−1,eℓ−1̸=0 i ei+1ei=0 ei+1ei>0

|ei+1+ei|<r ei+1ei<0 |ei+1|>|ei| ℓ a,b∈Dr,r−1 a,b ab=0 ab>0

|a+b|<r ab<0 |a|>|b| a,b r a,b r

r r r

d d=∑_ℓ−1

i=0eirⁱ ei∈Dr,(r²−1)/2 eℓ−1̸=0

i ei+1ei=0 eℓ=0 r

ℓ a,b∈Dr,(r²−1)/2 ab=0 a,b r a,b r

(25)

r=2 r r

r

d r

r d

d Dr,r−1 Dr,(r²−1)/2

r (r

1)/(r+1) (r 1)/(2r 1)

Fq p q=p^r

p Fq q

Fq Fq

Fq^m E(Fq^m) m≥2 Fq

E

y²+a1xy+a3y=x³+a2x²+a4x+a6,

ai∈Fq q≥ 5 Fq E

y²=x³+ax+b,

a,b∈Fq ϕ q^th E

ϕ:E→ E, (x,y)∪→(x^q,y^q),

(26)

tm :=q^m+1 #E(Fq^m)t:=t1 E(Fq^m) Fq^m

E ϕ

ϕ² tϕ+q=0

dP P

d w

[

DP+(2^w−2 1)AP

] +

[ ℓ

w+1AS+ℓDS

] , AP,DP AS,DS

w

d=(dℓ−1,...,d0)w ∈Z>0

di∈Dw

={0,±1,±3,...,±(2^w−1 1)}

ℓ≤⌈

log₂(d)⌉ +1 P∈E(Fq^m)

dPPi=iP

i∈{1,3,5,...,2^w−1 1}

Q← Oi ℓ 1 0 Q← 2Q

Q← Q+Pdi

Q

d=(dℓ−1,...,d0)ϕ∈Z>0

di∈Dϕ

={0,±1,±2,...,±α}

ℓ≤⌈

2log_q2√

NZ[ϕ]/Z(d)

⌉+4 P∈E(Fq^m)

dPPi=iP i∈{1,2,...,α} Q← Oi ℓ 1 0

Q← ϕ(Q) Q← Q+Pdi

Q ϕ

q

d∈Z[ϕ]

(27)

ϕ

E Fq ϕ q^th E t

ϕ (q,t)̸=(5,±4) (7,±5) d∈Z[ϕ]

d=∑_ℓ−1

i=0ciϕⁱ ci∈{0,±1,...,±(q 1)/2} ℓ≤⌈

2log_q2√

NZ[ϕ]/Z(d)⌉ +4

ℓϕ (d) ϕ d∈Z[ϕ]

dP {iP|i=1,2,...,(q 1)/2}

dP=

(_ℓ−1

∑

i=0

ciϕⁱ )

P=ϕ···ϕ(cℓ−1ϕ(P)+cℓ−2P)+···+c1P) +c0P.

Dϕ={0,±1,±2,...,±α}

α=(q 1)/2 Dϕ=Dq,(q−1)/2

[q 1

q ℓAS+ℓFS

]

(q=3), [

DP+q 5 2 AP

] +

[q 1

q ℓAS+ℓFS

]

(q≥5), FS

5 di< 0

Q← Q P−di(=Q+Pdi) di=0 Q←

Q+Pdi

τ

(28)

τ Ea

F2

Ea:y²+xy=x³+ax²+1, a=0or1.

τ Ea

τ:Ea→ Ea, (x,y)∪→(x²,y²).

τ

τ² µτ+2=0 µ=( 1)^1−a． τ τ d∈Z[τ] d=∑_ℓ−1

i=0eiτⁱ ei∈D2,1,eℓ−1̸=0 ei

τ ℓ

τ d∈Z[τ] τ

τ d D2,1

τ 1/3

Ea:y²=x³ x ( 1)^a/F3 a=0 1

τ

2/5 τ

τ

(29)

cases, it is necessary to know the non-zero densities and the maximum lengths of the proposed methods. In the next section, we will propose two classes of φ-NAF on a family of subeld elliptic curves. In the following, we call these two classes of φ-NAF φ-GNAF and φ-rNAF, respectively.

3.3 Proposed Methods (Two classes of φ -NAF)

In this section, we investigate how to expand two classes of φ-NAF on a family of subeld elliptic curves. We call the family of subeld elliptic curves F_q -Koblitz curves.

Denition 3.5 (Fq-Koblitz curves) Let p be a prime, q = p^r a power of p, and Fq the nite eld with q-elements. Let E be an elliptic curve dened over Fq

which is given by a Weierstrass equation

≡p= 2: y²+xy=x³+ax²+b (a, b Fq),

≡p= 3: y² =x³ +ax²+b (a, b Fq),

≡p∼5: y² =x³+ax+b (a, b Fq).

If the trace of the q^th-power Frobenius map t = ∓1, we call E F_q -Koblitz curve.

In the above denitions, note that for q = 2, F2-Koblitz curves are the above binary Koblitz curves E_a. Since the trace of the Frobenius map τ of E_a is μ = ( 1)^(1−a) = ∓1, F_q-Koblitz curve is a natural generalization of binary Koblitz curve.

In the following, we consider a scalar multiplication for a given integer d and for a given point P E(Fq^m), where q ∼5 and E is a Fq-Koblitz curve. In this case, it satises that

φ²φ+q = 0 (1,1, q)_φ= 0 ,

and by easy calculation, we have

∓φ³+ (q 1)φ²+q² = 0 (∓1, q 1,0, q²)_φ= 0 .

17

(30)

E

Fq Fq^m m≥2

P∈E(Fq^m)(ϕ^m 1)P=O dP=(dmod(ϕ^m 1))P

d Q,d^′∈ Z[ϕ] d=

Q(ϕ^m 1)+d^′ d^′=0 Ψ(d^′)<λΨ(ϕ^m 1) Ψ d

ϕ ϕr

ϕ α=a+bϕ∈Z[ϕ](a,b∈Z) ϕ|α ⇐⇒ q|a.

a∈Z ϕ|a⇐⇒ q|a

ϕ F

q

t=1

d E(Fq^m) ϕ

t=1 ϕ

ϕ d∈Z[ϕ]

q≥7

ϕ E Fq d∈Z[ϕ] ϕ

ϕ d E d=∑_ℓ−1

i=0eiϕⁱ ei∈Dq,q−1

ieℓ−1̸=0 ei+1ei=0

ei+1ei>0 |ei+1+ei|<q ei+1ei<0 |ei+1|>|ei|

(31)

a,b∈Dq,q−1 (a,b)ϕ ab=0 ab >0 |a+b|<q ab <0 |a|> |b|

(a,b)ϕ ϕ (a,b)ϕ ϕ

ℓϕGNAF(d) ϕ d∈Z[ϕ]

d=∑_ℓ−1

i=0eiϕⁱ∈Z[ϕ] ϕ (ei+1,ei)ϕ ϕ

ϕ q=7

d=314 ∈ Z[ϕ] d=

(¯1,3,¯3,2,3,3,¯1)ϕ ϕ d=314 d

(3,¯1)ϕ

ϕ e0=¯1

(3,3)ϕ ϕ

e1=3

(2,3)ϕ ϕ

e2=3

(¯3,2)ϕ ϕ e3=2

(3,¯3)ϕ ϕ

b4=¯3<0 b6=¯1+1=0 b5=3 1=2 e4=¯3+7=4

(0,2)ϕ ϕ

e5=2

ϕ d=(2,4,2,3,3,¯1)ϕ 0

ϕ d

d

ϕ

(32)

ϕ Fq t=1 q≥7 d∈Z[ϕ]

ϕ d

d^′← dmod(ϕ^m 1) ℓ←⌈

2log_q2√

NZ[ϕ]/Z(d)⌉ +4

(cℓ−1,cℓ−2,...,c1,c0)ϕ d^′ b0← c0 b1← c1,bℓ← 0,bℓ+1← 0

i← 0 i≤ℓ bi+1,bi ϕ

bi+2← ci+2,ei← bi

bi>0

bi+2← ci+2 1,bi+1← bi+1+1,ei← bi q bi+2← ci+2+1,bi+1← bi+1 1,ei← bi+q i← i+1

(eℓ+1,eℓ,...,e1,e0)ϕ

ϕ

Dq,q−1

ϕ

ϕ ϕ

b∈Dq,(q+1)/2 b^′∈Dq,(q−1)/2 e∈Dq,q−1

(b^′,e)ϕ ϕ (b,b^′)ϕ ϕ (b,b^′,e)ϕ∪→

{(¯1,c,c^′,e)ϕ:=(¯1,b+1,b^′ q,e)ϕ b^′>0, (1,c,c^′,e)ϕ:=(1,b 1,b^′+q,e)ϕ

(33)

(c,c^′)ϕ (c^′,e)ϕ ϕ

ϕ d∈Z[ϕ] ℓ=ℓϕEXP(d)

d d ϕ

Dq,q−1 ℓ+2

ℓ^′=ℓϕ (d) ℓ=ℓϕ (d)

d=(c,b,b^′,eℓ−4,...,e1,e0)ϕ ei∈Dq,q−1

c∈Dq,(q−1)/2,b∈Dq,(q+1)/2,b^′∈Dq,(q+3)/2 (b^′,eℓ−4,...,e1,e0)ϕ ϕ (b,b^′)ϕ (c,b)ϕ (b,b^′)ϕ ϕ

ℓ^′= ℓ (b,b^′)ϕ ϕ

(c,b,b^′)ϕ∪→(˜c,c^′,eℓ−3)ϕ:=

{(c 1,b+1,b^′ q)ϕ b^′>0, (c+1,b 1,b^′+q)ϕ

(˜c,c^′)ϕ ϕ ℓ^′=ℓ (˜c,c^′)ϕ∪→(a,a^′,eℓ−2)ϕ:=

{(¯1,˜c+1,c^′ q)ϕ c^′>0, (1,˜c 1,c^′+q)ϕ

a=1 ¯1 a^′∈Dq,(q+3)/2 (a,a^′)ϕ ϕ ℓ^′=ℓ+1

(a,a^′)ϕ ϕ ϕ

a=1,a^′<0 a=¯1,a^′>0 (a,a^′)ϕ∪→

{(¯1,0,a^′ q)ϕ a^′>0, (1,0,a^′+q)ϕ a^′<0.

ℓ^′=ℓ+2 ℓϕ (d) ℓϕ (d) □ q=3 5

bi q bi

q (bi+1,bi)ϕ∪→( bi/q,bi+1+bi/q,0)ϕ

bi q bi= ±q

i |bi+1| ≤(q+1)/2 |bi| ≤(q+3)/2 bi+1

q

(34)

Algorithm 4 φ-GNAF on Fq-Koblitz curves of t= 1 (q = 3 or q= 5) Input: d Z[φ]

Output: φ-GNAF of d

1: d →dmod (φ^m 1)

2: →

2 log_q2 N_Z[φ]/Z(d)

+ 4

3: Compute the Frobenius expansion (c₋₁, c₋₂, . . . , c₁, c₀)_φ of d

4: b₀ →c₀, b₁ →c₁, b →0, b₊₁ →0

5: i→0

6: while i≥ do

7: if b_i modq = 0 then

8: b_i+1 →b_i+1 b_i/q, b_i+2 →c_i+2+b_i/q, e_i →0

9: else if (b_i+1, b_i) :φ-admissible pair then

10: b_i+2 →c_i+2, e_i →b_i

11: else if b_i >0 then

12: b_i+2 →c_i+2 1, b_i+1 →b_i+1+ 1, e_i →b_i q

13: else

14: b_i+2 →c_i+2+ 1, b_i+1 →b_i+1 1, e_i →b_i+q

15: end if

16: i→i+ 1

17: end while

18: return (e₊₁, e, . . . , e₁, e₀)_φ

Let φ-GNAF be the set of φ-GNAF of length . We put A = #φ-GNAF, S =

d∈φ-GNAF( w(d)), and C = #}d φ-GNAF \w(d) =, where w(d) means the Hamming weight of d. In other words, C is the number of φ-GNAF with length such that all digits are non-zero. Then the non-zero density of φ-GNAF is dened by

1 lim

→∞S/(A).

φ-GNAF has properties same as GNAF except for the minimality of the Ham- ming weight. Althoughφ-GNAF does not have minimal Hamming weight, asymp- totic average non-zero density of φ-GNAF is same as GNAF. This indicates that the average number of point additions required by the φ-GNAF is smaller than

22

(35)

ϕ d∈Z[ϕ] ϕ

ϕ ℓ

(q 1)/(q+1)+(3q 1)/((q+1)²ℓ)+O(q^−ℓ) q

ϕ (q 1)/(q+1)

ϕ

Dq,q−1

d∈Z[ϕ]

d=∑

eiϕⁱ=∑

e^′_iϕⁱ.

i0 ei=e^′_i 0≤ i≤ i0 1 ei0̸=e^′_i₀ d (d ∑_i₀₋₁

i=0 eiϕⁱ)/ϕⁱ⁰=∑_ℓ−1

i=i0eiϕⁱ⁻ⁱ⁰ d=∑^ℓ−1

i=0

eiϕⁱ=∑^ℓ−1

i=0

e^′_iϕⁱ, e0̸=e^′₀, ℓ

q|(e0 e^′₀) |e0|,|e^′₀|≤q 1

|e0 e^′₀|≤|e0|+|e^′₀|≤2q 2 e0 e^′₀=±q e0 e^′₀=q

e0 e^′₀=q e0,e^′₀∈Dq,q−1 1≤e0≤q 1 (q 1)≤

e^′₀≤ 1 q=(e0 e^′₀)=∑_ℓ−1

i=1(e^′_i ei)ϕⁱ ϕ ϕ ϕ²=∑_ℓ−1

i=1(e^′_i ei)ϕⁱ (e1 e^′₁+1)=(e^′₂ e2+1)ϕ+

∑ℓ−1 i=3

(e^′_i ei)ϕⁱ⁻¹. q|(e1 e^′₁+1) e^′₁∈{e1+1 q,e1+1,e1+1+q}

(36)

Case 1. Suppose that e₁ = e₁+ 1 q. We have (q 1) ≥ e₁ ≥ 0 and 0 ≥ e₁ ≥ (q 1). We assume that (q 1) ≥ e₁ ≥ 1. Then from e₀e₁ > 0, we have e₀ e₁ ≥q 1. By substituting e₀ q for e₀ and e₁ (q 1) for e₁, we obtain e₀ +e₁ ∼ q. On the other hand, since e₀ > 0 and e₁ ∼ 0, we have e₀+e₁ ≥q 1. This is a contradiction. If e₁ = 0, thene₁ =q 1. From e₀ ∼1, we have e₀+e₁ ∼q. This is a contradiction.

Case 2. Suppose that e₁ = e₁+ 1. We have (q 2) ≥ e₁ ≥ q 1 and (q 1)≥e₁ ≥(q 2). We assume that 2≥e₁ ≥q 1. Then 1≥e₁ ≥(q 2). Since e₀e₁ <0, we have e₀+e₁ >0. By substituting e₀ q for e₀ and e₁ + 1 for e₁, we obtaine₀+e₁ = (e₀ q) +e₁+ 1 >0. Thuse₀+e₁ ∼q. On the other hand, by e₀ >0,e₁ >0, we havee₀+e₁ ≥q 1. This is a contradiction. Next, suppose that e₁ = 1. In this case, e₁ = 0. Since e₀e₁ <0, we must havee₁ = 1 > e₀ >0. However there does not exist e₀ which satises the above inequality. This is a contradiction. Suppose thate₁ = 0. In this case, e₁ = 1. By a similar argument as in the case of e₁ = 1, one can obtain that e₁ = 1 > e₀ >0. However there does not exist e₀ which satises the above inequality. This is a contradiction.

Finally, we assume that (q 2)≥ e₁ ≥ 1. Then (q 1) ≥e₁ ≥ 2. Since e₀e₁ >0, we have e₀ e₁ ≥q 1. By substituting e₀ q for e₀ and e₁+ 1 for e₁, we obtain e₀ e₁ = (e₀ q) (e₁+ 1)≥q 1. Thus e₀+e₁ ∼0. On the other hand, by e₀ >0, e₁ <0, we have e₀ +e₁ <0. This is a contradiction.

Case 3. Suppose that e₁ =e₁+ 1 +q. We have 2≥e₁ ≥q 1and (q 1)≥ e₁ ≥ 2. Since e₀e₁ <0, we have e₀+e₁ >0. By substituting e₀ q for e₀ and e₁ + 1 +q for e₁, we obtain e₀ q+e₁+ 1 +q > 0. Hence e₀+e₁ ≥ 0. On the other hand, since e₀ >0and e₁ <0, we have e₀+e₁ <0. This is a contradiction.

This concludes the proof.

(2) At rst, we show that C₊₁ = (q 2)C, C₁ = 2(q 1). We x an element d= (e₋₁, . . . , e₀)_φ ofZ[φ]which is φ-GNAF such that each e_i = 0. For the xed d, we count the number of e which satisfy 1 ≥ \e\≥ q 1, and (e₋₁, . . . , e₀, e)_φ is φ-GNAF. We can assume that e₀ >0. If e₀e >0, e satisfy 1≥e ≥q 1 e₀ and otherwise 1≥e < e₀. Thus we have that the number of eis q 2, hence the recurrence equation for C. It is trivial that C₁ = 2(q 1).

24

(37)

Next, we show thatA and S satisfy the recurrence equations A₁ = 2(q 1), A₂ = 2(q 1)²,A₊₂ (q 1)A₊₁ qA = 0 (∼1), and S₁ = 0,S₂ = 2(q 1),

S₊₂ (q 1)S₊₁ qS = 2(q 1)

1 + 2(q 1) (q+ 1)

q(q 1) q 1

( 1) 1

2 .

Table 3.1: Forms of digits φ-GNAF representations forms #of representations # of 0digits (±0± ××× ) C₁A₋₂ C₁A₋₂+C₁S₋₂ (±00± ××× ) C₁A₋₃ 2C₁A₋₃ +C₁S₋₃ (±000± ××× ) C₁A₋₄ 3C₁A₋₄ +C₁S₋₄

... ... ...

(±0000 ×××0±) C₁A₂ ( 3)C₁A₂+C₁S₂ (±0000 ×××00±) C₁A₁ ( 2)C₁A₁+C₁S₁

(±0000 ×××000) C₁ ( 1)C₁

(±±0± ××× ) C₂A₋₃ C₂A₋₃+C₂S₋₃ (±±00± ××× ) C₂A₋₄ 2C₂A₋₄ +C₂S₋₄ (±±000±××× ) C₂A₋₅ 3C₂A₋₅ +C₂S₋₅

... ... ...

(±±000 ×××0±) C₂A₂ ( 4)C₂A₂+C₂S₂ (±±000 ×××00±) C₂A₁ ( 3)C₂A₁+C₂S₁

(±±000 ×××000) C₂ ( 2)C₂

... ... ...

(±±± ×××±0±) C₋₂A₁ C₋₂A₁+C₋₂S₁ (±±± ×××±00) C₋₂ 2C₋₂ (±±± ×××±±0) C₋₁ C₋₁

(±±± ×××±±±) C 0

In Table 3.1, the symbol `±' means a non-zero digit. We explain how to interpret Table 3.1. The left column stands for forms of digits φ-GNAF, the central column stands for the number of each φ-GNAF corresponding to each form of the left column, and the right column stands for each number of 0 digits corresponding to each form of the left column. From Table 3.1, we can derive

25

(38)

A =

−2 j=1

C_j

_−1−j

i=1

A_i+ 1

+C₋₁+C,

S=

−2 j=1

C_j

_−1−j

i=1

S_i+ ( i j)A_i

+

−1 i=1

( i)C_i.

From these equations, we have the desired recurrence equations, and by ele- mentary calculations, we have A = 2(q 1) q ( 1)

/(q+ 1), and S= 2(q 1)

(q+ 1)²

(2q (q 1)( 1)) 3q 1

q+ 1 (q ( 1))

.

From the equations of A, S, the average number of non-zero digits for digits numbers in Z[φ] is equal to S/A. We put

f() :=

1 S A

q 1

q+ 1 + 3q 1 ((q+ 1)²)

.

Then

f() = q 3 q+ 1 ×

( 1) q ( 1)

. Let us take g() :=q⁻. Since it satises that

f()

g() = q 3

q+ 1 × ( 1) 1 ( q)⁻,

we obtain

f() g()

= q 3

q+ 1 × 1

1 ( q)⁻ ⇐ q 3

q+ 1 (⇐ ∈ ).

Hencef() = O(g()). Thus1 lim_→∞S/(A) = 1 2/(q+1) = (q 1)/(q+1). Hence we have the desired result.

(3) We give a counter example that is an element α Z[φ] that does not have minimal Hamming weight. Let qis a power of odd primep, andα= φ (q 1) Z[φ]. An Frobenius expansion of α with digit set D_q,q−1 is ( 1,1 q)_φ and its Hamming weight is 2. But φ-GNAF of α is (1,0, q 2,1)_φ and its Hamming weight is 3. Therefore φ-GNAF does not have minimal Hamming weight among

all Frobenius expansion with digit set D_q,q−1.

26

(39)

ϕ d∈Z[ϕ]

d ϕ

ϕ

ϕ Fq t=1

d∈Z[ϕ]

ϕ d

d^′:=d0+d1ϕ← dmod(ϕⁿ 1)(d0,d1∈Z) ℓ←⌈

2log_q2√

NZ[ϕ]/Z(d)⌉ +4

Q,b∈Z d0=Qq+bb∈Dq,(q−1)/2

d0← Q+d1 d1← Q i← 1

i≤ℓ+1

Q,a∈Z d0=Qq+a a∈Dq,(q−1)/2

d0← Q+d1d1← Q a,b ϕ

ei−1← b,b← a b>0

ei−1← b q,b← a+1,d0← d0 1 ei−1← b+q,b← a 1,d0← d0+q

(eℓ+1,eℓ,...,e1,e0)ϕ

(i+1)P=P+iP 1≤i≤q 2

ϕ ϕ α=q 1

Dϕ=Dq,q−1

[

DP+q 1

q+1ℓAS+ℓFS

]

(q=3), [

DP+(q 3)AP+q 1

q+1ℓAS+ℓFS

]

(q≥5).

(40)

ϕr F

q

t=1

d E(Fq^m)

ϕ r

t=1 ϕr

ϕr d∈Z[ϕ] q≥7

ϕr E Fq d∈Z[ϕ] ϕ

r ϕr d E d=∑_ℓ−1

i=0eiϕⁱ ei∈Dq,(q²−1)/2 eℓ−1̸=0 ei+1ei=0 i a,b∈Dq,(q²−1)/2

ab=0 (a,b)ϕϕ (a,b)ϕϕ ℓϕrNAF(d) ϕr d∈Z[ϕ]

d=∑_ℓ−1

i=0eiϕⁱ∈Z[ϕ] ϕr (ei+1,ei)ϕ ϕ

ϕr q=7 d=314∈Z[ϕ]

d (¯1,3,¯3,2,3,3,¯1)ϕ ϕr d=314 d

(3,¯1)ϕ

ϕ |3×7 1|=20<24 b3=2,b2=3+3=6,e1= 0,e0=3×7 1=20

(2,6)ϕ ϕ

|2×7+6|=20<24 b5=3,b4= 3+2= 1,e3=0,e2=2×7+6=20

(3,¯1)ϕ ϕ

|3×7 1|=20<24 b7=0,b6= 1+3=2,e5=0,e4=3×7 1=20 (0,2)ϕ ϕ

e6=2

ϕr d=(2,0,20,0,20,0,20)ϕ

0 ϕr

d d

(41)

ϕr d ϕ d

ϕr Fq t=1 q≥7

d∈Z[ϕ]

ϕr d

d^′← dmod(ϕ^m 1) ℓ←⌈

2log_q2√

NZ[ϕ]/Z(d)⌉ +4

(cℓ−1,cℓ−2,...,c1,c0)ϕ d^′ b0← c0 b1← c1,bℓ← 0,bℓ+1← 0,bℓ+2← 0,bℓ+3← 0

i← 0

i≤ℓ+2 bi=0

bi+2← ci+2,ei← 0,i← i+1

|bi+1q+bi|≤(q² 1)/2

bi+3← ci+3,bi+2← ci+2+bi+1,ei+1← 0,ei← bi+1q+bi,i← i+2 bi+1q+bi< (q² 1)/2

bi+3← ci+3+1,bi+2← ci+2+bi+1+(q 1),ei+1← 0,ei← bi+1q+bi+ q²,i← i+2

bi+3← ci+3 1,bi+2← ci+2+bi+1 (q 1),ei+1← 0,ei← bi+1q+bi

q²,i← i+2

(eℓ+3,eℓ+2,...,e1,e0)ϕ

r

(bi+1,bi)ϕ∪→

{(¯b^′_i,bi+1+b^′_i,0)ϕ bi=b^′_iq b^′_i∈Z\{0}, (¯b^′_i+1,b^′_i+1,0,bi)ϕ bi+1=b^′_i+1q b^′_i+1∈Z\{0}.

(42)

bi bi+1 q (bi+1,bi)ϕ

c,c^′,c^′^′∈Dq,(q−1)/2 b∈Dq,(q+1)/2 b^′∈Dq,2q−1

(c,c^′,c^′^′,b,b^′)ϕ

(a,a^′,e,e^′,e^′^′,e^′^′^′)ϕ

(a,b)ϕ

a̸=0,b̸=0 (a,b)ϕ

(a,b)ϕ∪→







(a,0,aq+b)ϕ |aq+b|≤(q² 1)/2, (1,a+(q 1),0,(aq+b)+q²)ϕ aq+b< (q² 1)/2, (¯1,a (q 1),0,(aq+b) q²)ϕ

a̸=0,b=0 b

a

a=0,b=0 a b

a

(e,e^′,e^′^′,e^′^′^′)ϕ ϕr a∈Dq,(q+1)/2,a^′∈

Dq,2q−1 a a^′ q

(c,c^′,c^′^′,b,b^′)ϕ

i (i+1) ♭ (i+

2) (i+3) ♯ a^′ q

|a^′|≤2q 2 a^′=q a^′= q a^′=q

a^′=q a^′= q

a^′ q (♯,♭)=((1),(2)),((2),(1)),((2),(2)),((3),(2))

1 2

(♯,♭) =((1),(2)) a^′= c+c^′+(q 1) c^′= c+1 (c,c^′,c^′^′,b,b^′)ϕ e^′=( c+1)q+c^′^′+b+q²

e^′>(q² 1)/2 |e^′|≤(q² 1)/2

(43)

(♯,♭)=((2),(1)) a^′=c+c^′+1 c=c^′= (q 1)/2 (c,c^′,c^′^′,b,b^′)ϕ e^′^′^′=bq+b^′+q² e^′= c^′^′+b+(q²+3q 2)/2 b= (q 3)/2, (q 1)/2, (q+1)/2

b≤ q |b|≤(q+1)/2

(♯,♭)=((2),(2)) a^′=c+c^′+q c^′= c (c,c^′,c^′^′,b,b^′)ϕ e^′^′^′=bq+b^′+q² e^′=( c+1)q+

c^′^′+b+(q 1)+q² b= (q 3)/2, (q 1)/2, (q+1)/2 cq+c^′^′< (q² 1)/2

c^′^′,c

(♯,♭) =((3),(2)) a^′= c+c^′+q 2 c^′= c+2 (c,c^′,c^′^′,b,b^′)ϕ e^′^′^′=bq+b^′ q² e^′=( c+1)q+c^′^′+b (q 1)+q² b=(q 3)/2,(q 1)/2,(q+1)/2 cq+c^′^′< (q² 1)/2