Using quadratic sieve (see : https://en.wikipedia.org/wiki/Quadratic_sieve), it is possible to factorize a composite number $n$.
This method ultimately relies on the fact that we have $x$ and $y$ such that neither $x-y$ nor $x+y$ is divisible by $n$ but $x^2-y^2$ is divisible by $n$.
Most of us probably know this : it is possible to find such $x$ and $y$ is divisible by at least $2$ primes (if $n=p_1^{a_1}...p_r^{a_r}$ and $z$ is coprime to $n$ then the equation $x^2=z$ mod $n$ has either $0$ or $2^r$ solutions).
From this it follows that the quadratic sieve will never work when $n=p^a$ is a prime power. Whence my question :
Assume we know that $n$ is a prime power. How to find $p$ and $a$ ?
I see different methods :
Compute for $r$ from 1 to ... an approximation of $^r\sqrt{n}$ take the nearest integer $A_r(n)$ from it and compute $A_r(n)^r$. If $r$ divides $a$ then $A_r(n)^r$ will be equal to $n$. Apply the same thing to $A_r(n)$ which is then $p^{\frac{a}{r}}$. If $A_r(n)$ is prime then we are done, else keep on doing the same thing until we reach a prime number.
Use a Pollard "rho" method on $n$. Since $p=$ $^a\sqrt{n}$ then the method will, with a high probability, find a divisor $d$ in $O(n^{\frac{1}{2a}})$ iterations. Test if the divisor is prime, if it is then $p=d$ and compute an approximation of $log_p(n)$ which is $a$. If it is not keep on "rho" Pollard until we find a prime divisor.
The first method is very well adapted when $a$ is small (an approximation of $^r\sqrt{n}$ is "very" fastly and easily computed by the Newton algorithm which has quadratic convergence) and computing $A_n(r)^r$ is a piece of cake with a dichotomic expansion ($log(log(n))$ operations). However $a$ might be very big and the accumulation of approximations might get difficult.
The second method seems to handle the case where $a$ is very big, since the more $a$ is big, the smaller $p$ is and Pollard "rho" method handles the case where $p$ is small.
Are there better method than those ones to handle the case of a prime power?
As a final requirement, I would like to know if there is a way (analogous to prime numbers : Solovay-Strassen, Miller-Rabin...) to detecte prime powers easily.
As far as I can tell we only have the following proposition :
Let $n$ be an odd number. Then $n$ is a prime power if and only if the equation $x^2=1$ has exactly two solution modulo $n$.
Can we turn this one into a probabilistic algorithm of detection of prime powers? Is there any other property that could lead to a prime power detection?