Koblitz curves have been proposed to quickly generate random ideal classes and points on hyperelliptic and elliptic curves. To obtain a further speedup a different way of generating these random elements has recently been proposed. In this paper we give an upper bound on the number of collisions for this alternative approach. For elliptic Koblitz curves we additionally use the same methods to derive a bound for a modified algorithm. These bounds are tight for cyclic subgroups of prime order, which is the case of most practical interest for cryptography.
|Number of pages||9|
|Journal||Applicable Algebra in Engineering, Communications and Computing|
|Publication status||Published - Feb 2005|
- Discrete Logarithm
- Hyperelliptic Curves
- Koblitz Curves
- Public Key Cryptography