In Fermat factorization you can factor an integer $n$ if you find a nontrivial pair $(x,y)$ such that $x^2\equiv y^2 \mod n$.
At the end of the description in https://mathworld.wolfram.com/FermatsFactorizationMethod.html (last paragraph) I found the statement:
This algorithm can be used to prove primality, but is not practical.
Even if it is not practical, I suppose the algorithm must be better than exhaustive factor search. Does anyone know how Fermat factorization can be used for (inefficient) primality proving?
I begin with the second question. Suppose, $\ n\ $ is given. We want to check whether it is prime. We can assume that $\ n\ $ is odd since $\ 2\ $ is the only even prime. If $\ n\ $ is composite, there must be odd integers $\ a,b>1\ $ with $\ ab=n\ $. With $$x:=\frac{a+b}{2}$$ $$y:=\frac{a-b}{2}$$ we have $$x^2-y^2=ab=n$$ so, there must be some positive integer $\ x\ $ such that $\ x^2-n\ $ is a perfect square smaller than $\ (x-1)^2\ $. The Fermat method will eventually find it. If such $\ x\ $ does not exist, $\ n\ $ must be prime.
The method works well, if $\ n\ $ is the product of two odd factors that do not differ much. But if, for example , $\ n=pq\ $ , with $\ p\ $ a small prime and $\ \ q$ a large , the algorithm must continue until approximately $\ x=\frac{n}{2p}\ $ and this is much worse than trial division, which only needs to check upto $\ \sqrt{n}\ $