access icon free Remarks on the Pocklington and Padró–Sáez cube root algorithm in 𝔽 q

© The Institution of Engineering and Technology
Received 25/03/2014, Published 27/06/2014

A cube root algorithm in 𝔽 q proposed by Pocklington and later rediscovered by Padró and Sáez is clarified and generalised. Some errors in the result of Padró and Sáez are corrected and a full generalisation of their result is given. A comparison of the implementation of the proposed algorithm with the two most popular cube root algorithms is also given, namely the Adleman–Manders–Miller algorithm and the Cipolla–Lehmer algorithm. To the authors’ knowledge, this comparison is the first one which compares three fundamental algorithms together.

Inspec keywords: mathematical analysis

Other keywords: Adleman-Manders-Miller algorithm; Padró-Sáez cube root algorithm; Cipolla-Lehmer algorithm

Subjects: Mathematical analysis; Mathematical analysis; Other topics in mathematical methods in physics; Mathematical analysis

References

    1. 1)
    2. 2)
      • 9. American Mathematical Society: ‘MathSciNet Review’, Available at http://www.ams.org/mathscinet.
    3. 3)
      • 5. Williams, K.S., Hardy, K.: ‘A refinement of H. C. Williams’ qth root algorithm’, Math. Comput., 1993, 61, pp. 475–483.
    4. 4)
      • 2. Adleman, L., Manders, K., Miller, G.: ‘On taking roots in finite fields’. Proc. 18th IEEE Symp. Foundations on Computer Science (FOCS), Providence, RI, USA, November 1977, pp. 175–177.
    5. 5)
    6. 6)
      • 1. Pocklington, H.C.: ‘The direct solution of the quadratic and cubic binomial congruences with prime moduli’, Proc. Cambridge Philos. Soc., 1917, 19, pp. 57–59.
    7. 7)
      • 3. Cao, Z., Sha, Q., Fan, X.: ‘Adlemen–Manders–Miller root extraction method revisited’, 2011, preprint. Available at http://www.arxiv.org/abs/1111.4877.
    8. 8)
      • 4. Williams, H.C.: ‘Some algorithm for solving xq ≡ N(mod p)’. Proc. Third Southeastern Conf. Combinatorics, Graph Theory, and Computing, Florida Atlantic University, FI, USA, March 1972, pp. 451–462.
    9. 9)
      • 8. Bernstein, D.: ‘Faster square roots in annoying finite fields’, preprint. Available at http://www.cr.yp.to/papers/sqroot.pdf.
http://iet.metastore.ingenta.com/content/journals/10.1049/el.2014.1037
Loading

Related content

content/journals/10.1049/el.2014.1037
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading