Problems in Algorithmic Number theory

Abstract

This thesis presents new results for four problems in the field of Algorithmic and Computational Number Theory. The first gives an improved analysis of algorithms for testing whether a given positive integer n is a perfect power. The second problem gives an improved upper bound on the worst case numbers for a variant of the strong pseudo prime test, very close to settling a Granville's Conjecture. The third result is about progress towards a conjecture of S.W. Graham; It is shown that his conjecture is true for an improved condition. The fourth result deals with the problem of finding the least witness w(n) of a composite number n. A number w is a witness for a composite number n if n is not a strong Pseudo-prime to the base w. Other interesting algorithmic results about witnesses are also presented.