Improving the Pocklington and Padr'{o}-S'{a}ez cube root Algorithm

摘要

In this paper, we present a cube root algorithm using a recurrence relation. Additionally, we compare the implementations of the Pocklington and Padr'{o}-S'{a}ez algorithm with the Adleman-Manders-Miller algorithm. With the recurrence relations, we improve the Pocklington and Padr'{o}-S'{a}ez algorithm by using a smaller base for exponentiation. Our method can reduce the average number of Fq multiplications.