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 the previous best-known bound of $O(n^{1/4})$. The second bound, assuming the Extended Riemann Hypothesis (ERH), is $O((\log n)^k)$ steps, showing that primality can be tested in time polynomial in the length of the binary representation of the number. The paper also discusses the relationship between the complexity of computing the prime factorization, Euler's phi function, and other related functions, proving that these functions are polynomial-time equivalent. The proofs rely on the existence of "small" quadratic nonresidues and the properties of certain functions under the ERH. The algorithms are designed to handle composite numbers efficiently, including those that satisfy Fermat's Congruence and those with specific properties related to the Carmichael $\lambda$-function. The paper concludes with detailed analyses of the algorithms' running times and correctness.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 the previous best-known bound of $O(n^{1/4})$. The second bound, assuming the Extended Riemann Hypothesis (ERH), is $O((\log n)^k)$ steps, showing that primality can be tested in time polynomial in the length of the binary representation of the number. The paper also discusses the relationship between the complexity of computing the prime factorization, Euler's phi function, and other related functions, proving that these functions are polynomial-time equivalent. The proofs rely on the existence of "small" quadratic nonresidues and the properties of certain functions under the ERH. The algorithms are designed to handle composite numbers efficiently, including those that satisfy Fermat's Congruence and those with specific properties related to the Carmichael $\lambda$-function. The paper concludes with detailed analyses of the algorithms' running times and correctness.