Perhaps you shouldn't dismiss mahbel's remarks so quickly. I can't quite follow what he is stating but he is telling you that rather than blindly searching for squares, you can narrow your search to relevant forms.
It also helps to analyze routines with small numeric examples instead of astronomically large ones.
Suppose you want to factor 21,
52  21=5^22^2
You could build some intelligence into your search by knowing effective ranges and rules. You could also extend your search to powers other than 2.
For example:
n^5m^3  n^(5j)m(3j)
3 and 5 are arbitrary and can be replaced by any integers (or primes if you prefer).
But generally there is a commonality to the form of the composite candidate and it's subpower factors that can be built as intelligence into the search.
The Mersenne numbers are a subset of this rule of the form:
2^n1^m  2^(nj)1^(mj)
Last fiddled with by a1call on 20170305 at 16:37
