PROBLEMS

In this thesis, we are mainly interested in constructing deterministic polynomial-time algorithms for solving some computational problems that arise in number theory and cryptography. The problems we are interested in include finite field arithmetic, primality testing, and elliptic curve arithmetic. We first present a novel idea to compute square roots over some families of fi-nite fields. Our square root algorithm is deterministic polynomial-time and can be proved by elementary means. The approach of taking square roots is generalized to take nth roots. Then, we present a deterministic polynomial-time algorithm to solve polynomial equations over some families of finite fields. As applications, we construct a deterministic polynomial-time primality test for some forms of integers and show a deterministic polynomial-time algorithm computing elliptic curve “nth roots”. For example, we prove the following statements. Denote a finite field with q elements and characteristic p by Fq. (I) Suppose p ≡ 1 (mod 12), q = 2e3f t + 1 for some e, f ≥ 1 and some t = O(poly(log q)). There is a deterministic polynomial time algorithm taking square roots over Fq. (II) Let re11 · · · remm be the prime factorization of q − 1. Suppose rj = O(poly(log q)) and a primitive rjth root of unity can be computed efficiently for 1 ≤ j ≤ m. There is a deterministic polynomial time algorithm solving any polynomial equation with degree O(poly(log q)) over Fq. (III) Let N = ret+1 for some prime r and some positive integers t and e with re> t. There is an Õ(r2(log2N)(t+r logN)) deterministic primality testing algorithm. If r is a small constant and t = O(logN), the running time is Õ(log3N)