Назовём простое число р специальным, если

и исключительным, если существует n
Из того, что при p=1(mod 4) выполняется

, следует что такое число не является специальным простым числом. А простые числа вида p=7(mod 8) вообще не делят числа вида

, поэтому специальными простыми могут быть только простые вида p=3(mod 8), причём из

получается, что квадратичных вычетов среди чисел 1,2,3,...(p-1)/2 было нечётным (соответственно квадратичных невычетов чётно). Последнее условие эквивалентно так же нечётности количества нечётных квадратичных вычетов. Примерно половина простых вида p=3(mod 8) удовлетворяют этому условию и являются специальными.
Среди простых меньше 5 000 000 имеется ровно 3 исключительных:
Если кто хочет найти ещё исключительные простые (которых, как я понимаю бесконечно много) предлагаю алгоритм поиска. Будем по циклу нарасти число m и вычислим число

Во внутреннем цикле пробегаем по нечётным k и вычисляем

, если

, то

исключительное число для всех простых делителей

. При этом время от времени вычисляем

и сокращаем

на простые делители

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