78.
For pairing based cryptography we need elliptic curves defined over finite fields
whose group order is divisible by some prime
with
where
k is relatively small. In Barreto et al. and Dupont et al. [Proceedings of the Third Workshop on Security in Communication Networks (SCN 2002), LNCS, 2576, 2003; Building curves with arbitrary small Mov degree over finite fields, Preprint, 2002], algorithms for the construction of ordinary elliptic curves over prime fields
with arbitrary embedding degree
k are given. Unfortunately,
p is of size
.We give a method to generate ordinary elliptic curves over prime fields with
p significantly less than
which also works for arbitrary
k. For a fixed embedding degree
k, the new algorithm yields curves with
where
or
depending on
k. For special values of
k even better results are obtained.We present several examples. In particular, we found some curves where
is a prime of small Hamming weight resp. with a small addition chain.AMS classification: 14H52, 14G50
相似文献