Research Of Univariate Equations Over Finite Fields And Some Related Problems

In this thesis, we are mainly interested in solving univariate polynomial equations over ?nite ?elds and related problems that arise in number theory and cryptography.The problems we are interested in include square root, cubic root, r-th root and primality testing.First, we present a deterministic algorithm to compute square root over any ?nite?elds Fq. Our square root algorithm is ?nished by constructing a ring which is isomorphism Fq× Fq. All the computations proceeds on this ring. The running time of our algorithms is O(t log t log q + log2q),where q- 1 = 2st. Our algorithm is deterministic polynomial algorithm when t = poly(log q). Also, we applied this square root algorthm to Proth prime number testing. Our algorithm is the best Proth prime number testing algorithm when t is O((log q)2).Then, we extend Sze’s deterministic square root algorithm over Fqto a randomized square root algorithm, where q-1 = 2st. The expected running time of our randomized algorithm is O((log q)2). Contrast to Tonelli-Shanks, each random choice has a better probability if s grows faster. Also, we needn’t to compute ζ4.Then, we present 3 algorithm to computer square root over Fpusing Lucas sequence. We directly construct a randomized square root algorithm with Vn(P, Q). Its expected running time is 4.5 log p multiplications over Fp. After that, we construct a deterministic algorithm to compute square root with Vn(P, 1). It can exactly compute(p- 1)/4 + 1 square roots over Fp. Then we extend this deterministic algorithm to a randomized algorithm, its expected running time is 2 log p multiplications over Fp.Then, we extend Berlekamp algorithm to cubic root over Fq. Then we analysis the algorithm using fundamental cyclotomy theory. Unlike the previous algorithm, we use quadratic residue to compute cubic root and cubic residue is not involved in our procedure. After that, we extend this method to any x3+ ax2+ bx + c = 0 over Fq.At last, we give a randomized algorithm to solve xr= a over Fqby computing Norm from Fqrto Fq, where r is prime power. This can be seen an extension of CipollaLehmer square root algorithm. We ?nish our algorithm by constructing an irreducible polynomial over Fq[X ], where deg(f) = r and f(x) with constant term(-1)ra. Our algorithm is practical when r4≤ q.