За 15ч проверил до

, подходящих

не нашёл.
Выглядит привлекательной идея вести перебор по

. В этом случае наиболее затратной операцией является факторизация

.
Так порядок роста будет

, это не есть хорошо, я
выше привёл алгоритм с ростом

. Собственно как показывает указанное мною время уже нет разницы по

или по

(точнее по

) вести перебор, основное время занимает перебор делителей (ну и вероятно разложение на множители для него).
С какой скоростью можно искать квадратичные вычеты для составных чисел

и будет ли это быстрее факторизации (перебора делителей) я пока не в курсе, похоже придётся делать факторизацию

и искать вычеты по каждому простому в разложении. Впрочем вычисление символа Лежандра вроде бы быстрее разложения на множители, а китайская теорема об остатках (для получения полного списка вычетов) и проверка делителей довольно быстрые ...