TCS-TR-A-19-83

Date: Wed Jul 24 17:32:59 2019

Title: Taking Discrete Roots in the Field Z_p and in the Ring Z_p^e

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 Z_p and in the ring Z_p^e, 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 p^e. 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.