In this paper, we propose a new approach to solve DLPwAI concentrating on the behavior of function mapping between the finite fields rather than using an embedding to auxiliary groups. This result shows the relation between the complexity of the algorithm and the number of absolutely irreducible factors of the substitution polynomials, hence enlightens the research on the substitution polynomials.
More precisely, with a polynomial $f(x)$ of degree $d$ over $\mathbf{F}_p$, the proposed algorithm shows the complexity $O\left(\sqrt{p^2/R}\log^2d\log p\right)$ group operations to recover $\alpha$ with $g, g^{\alpha}, \dots, g^{\alpha^{d}}$, where $R$ denotes the number of pairs $(x, y)\in\mathbf{F}_p\times \mathbf{F}_p$ such that $f(x)-f(y)=0$. As an example using the Dickson polynomial, we reveal $\alpha$ in $O(p^{1/3}\log^2{d}\log{p})$ group operations when $d|(p+1)$. Note that Cheon's algorithm requires $g, g^{\alpha}, \dots, g^{\alpha^{d}}, \dots, g^{\alpha^{2d}}$ as an instance for the same problem.
Category / Keywords: foundations / discrete logarithm problem, Cheon's algorithm, fast multipoint evaluation, Dickson polynomial, substitution polynomial, point counting, absolutely irreducible polynomial Date: received 29 Oct 2012 Contact author: yoshiki1 at snu ac kr Available formats: PDF | BibTeX Citation Version: 20121029:140824 (All versions of this report) Discussion forum: Show discussion | Start new discussion