Quasi-quadratic elliptic curve point counting using rigid cohomology |
| |
Authors: | Hendrik Hubrechts |
| |
Affiliation: | Department of Mathematics, Katholieke Universiteit Leuven, Celestijnenlaan 200B - bus 2400, B-3001 Heverlee, Belgium |
| |
Abstract: | Let E be a nonsupersingular elliptic curve over the finite field with pn elements. We present a deterministic algorithm that computes the zeta function and hence the number of points of such a curve E in time quasi-quadratic in n. An older algorithm having the same time complexity uses the canonical lift of E, whereas our algorithm uses rigid cohomology combined with a deformation approach. An implementation in small odd characteristic turns out to give very good results. |
| |
Keywords: | Elliptic curve Point counting Rigid cohomology Cryptography |
本文献已被 ScienceDirect 等数据库收录! |