TTT писал(а):

дальше можно разложить

и подстановкой найти целые решения.
Смущает зависимость от числа множителей.Их может быть очень много.
Есть ли какие-то другие варианты решения без разложения

,т.е. без перебора?
Во-первых, не всякое разложение 4A+1 в произведение двух множителей дает решение. Множители должны давать одинаковые остатки при делении на 8 (а поэтому, в частности, A должно быть четным числом). Каждое такое разложение будет давать решение.
Во-вторых, без разложения 4A+1 на множители не обойтись. Дело в том, любое решение исходного уравнения будет автоматически давать некоторое разложение 4A+1 на множители указанного вида. Поэтому эти задачи эквивалентны.