This paper presents new upper bounds on the complexity of algorithms for testing the primality of a number. The first bound is O(n^{1/7}), improving upon the previously known O(n^{1/4}) bound by Pollard. The second bound, under the assumption of the Extended Riemann Hypothesis (ERH), provides an algorithm that tests primality in O((log n)^4) steps, showing that primality is testable in polynomial time relative to the length of the binary representation of a number. The paper also explores the relationship between the complexity of computing the prime factorization of a number, the Euler phi function, and other related functions. It shows that these functions are polynomial time equivalent under the ERH. The key steps involve demonstrating the existence of a "small" quadratic nonresidue and using results from Burgess and Ankeny to establish the bounds. The paper defines an algorithm class A_f, which tests primality by checking if a number is a perfect power or by testing certain conditions on a set of values. The algorithm's complexity is analyzed, and it is shown that under the ERH, the algorithm runs in O(|n|^4 log log |n|) steps. The paper also discusses the implications of these results for the complexity of factoring numbers and the recognition of composite numbers that satisfy Fermat's congruence. The results are supported by various lemmas and theorems, including those related to the Carmichael numbers and the properties of quadratic residues. The paper concludes with the proof of the main theorems and the implications of the results for the complexity of primality testing and factorization.This paper presents new upper bounds on the complexity of algorithms for testing the primality of a number. The first bound is O(n^{1/7}), improving upon the previously known O(n^{1/4}) bound by Pollard. The second bound, under the assumption of the Extended Riemann Hypothesis (ERH), provides an algorithm that tests primality in O((log n)^4) steps, showing that primality is testable in polynomial time relative to the length of the binary representation of a number. The paper also explores the relationship between the complexity of computing the prime factorization of a number, the Euler phi function, and other related functions. It shows that these functions are polynomial time equivalent under the ERH. The key steps involve demonstrating the existence of a "small" quadratic nonresidue and using results from Burgess and Ankeny to establish the bounds. The paper defines an algorithm class A_f, which tests primality by checking if a number is a perfect power or by testing certain conditions on a set of values. The algorithm's complexity is analyzed, and it is shown that under the ERH, the algorithm runs in O(|n|^4 log log |n|) steps. The paper also discusses the implications of these results for the complexity of factoring numbers and the recognition of composite numbers that satisfy Fermat's congruence. The results are supported by various lemmas and theorems, including those related to the Carmichael numbers and the properties of quadratic residues. The paper concludes with the proof of the main theorems and the implications of the results for the complexity of primality testing and factorization.