Name
Abstract | ||
|---|---|---|
Elliptic curves over number fields with CM can be used to design non-isogenous elliptic cryptosystems over finite fields efficiently. The existing algorithm to build such CM curves, so-called the CM field algorithm, is based on analytic expansion of modular functions, costing computations of O(25h/2h21/4) where h is the class number of the endomorphism ring of the CM curve. Thus it is effective only in the small class number cases. This paper presents polynomial time algorithms in h to build CM elliptic curves over number fields. In the first part, probabilistic probabilistic algorithms of CM tests are presented to find elliptic curves with CM without restriction on class numbers. In the second part, we show how to construct ring class fields from ray class fields. Finally, a deterministic algorithm for lifting the ring class equations from small finite fields thus construct CM curves is presented. Its complexity is shown as O(h7). |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/3-540-49649-1_9 | ASIACRYPT |
Keywords | Field | DocType |
cm field algorithm,elliptic curve,cm test,ray class field,class number,cm curve,secure elliptic,cm elliptic curve,ring class field,number field,ring class equation,cm tests,modular function,finite field | Discrete mathematics,Supersingular elliptic curve,Finite field,Abelian variety,Probabilistic analysis of algorithms,Algebraic number field,Counting points on elliptic curves,Mathematics,Elliptic curve,Schoof's algorithm | Conference |
Volume | ISSN | ISBN |
1514 | 0302-9743 | 3-540-65109-8 |
Citations | PageRank | References |
7 | 2.65 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jinhui Chao | 1 | 58 | 16.18 |
| Osamu Nakamura | 2 | 21 | 6.24 |
| Kohji Sobataka | 3 | 7 | 2.65 |
| Shigeo Tsujii | 4 | 598 | 131.15 |