On Generalization of Cheon's Algorithm.
Takakazu Satoh · 2009
Abstract. Let G be a cyclic group generated by g whose group operations are written additively. Assume that the order of G is a prime p. Let d be a divisor of p + 1. Let c∈Fp. Given cg, c 2 g,..., c 2d g, Cheon[4] gave an algorithm to compute c more efficiently than solving ordinal discrete logarithm problems. With improvement by Kozaki, Kutsuma and Matsuo[5], the algorithm runs with O(max(d, p p/d)) group operations. We generalize his algorithm for divisors of ϕn(p) where n∈N and ϕn is the n-th cyclotomic polynomial. In case that d is a divisor of p + 1 (i.e. the case n = 2), our algorithm requires only cg,..., c d g to compute c with Õ(max(d, p p/d)) operations of G and Fp. Key words: discrete log problem, generic algorithm, Cheon’s algorithm 1