TCS-TR-A-19-83

Date: Wed Jul 24 17:32:59 2019

Title: Taking Discrete Roots in the Field Zp and in the Ring Zpe

Authors: Thomas Zeugmann

Contact:

  • First name: Thomas
  • Last name: Zeugmann
  • Address: Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan
  • Email: thomas@ist.hokudai.ac.jp

Abstract. The present paper studies the problem of taking discrete roots in the field Zp and in the ring Zpe, where p is a prime number and e is a positive natural number. After surveying the state of the art, the paper presents several generalizations of Tonelli-Shanks and Adleman-Manders-Miller like approaches. In particular, it shown that there is a generalization of the generalized Adleman-Manders-Miller algorithm which allows one to compute directly discrete qth roots with respect to the modulus pe. The second part is devoted to lifting algorithms. Here the main emphasis is completeness; i.e., we present lifting algorithms for all possible cases depending on the prime p, the root q and the greatest common divisor of p and q. As a byproduct, we also present a proof of one of Tonelli's (1891) lifting algorithms.


©Copyright 2019 Authors