Алгоритм выделения простых A005385

[kthxbye]

Баловался с МТФ, в результате чего наткнулся на следующий фильтр:

$$2^{\left\lfloor\frac{n}{2}\right\rfloor+\operatorname{nextprime}(\left\lfloor\frac{n}{2}\right\rfloor)} \equiv 1 \pmod n$$

Здесь $\operatorname{nextprime}(n)$ - наименьшее простое большее либо равное $n$.

Фильтр выделяет простые A005385, т.е. такие простые $p$, что $\frac{p-1}{2}$ также простое. Как и в МТФ, окромя них вылазят и составные $q$, но от них легко избавиться проверив $\frac{q-1}{2}$ на простоту.

Т.е. мы выполняем всего 2 операции:

• используем фильтр выше
• проверяем на простоту $\frac{n-1}{2}$

Если во втором случае мы получили простое, тогда это означает, что $n$ тоже простое.

Чем все это можно объяснить? Насколько эффективен приведенный выше алгоритм (например, в плане отсутствия неочевидных ошибок)?

[xagiwo]

kthxbye в сообщении #1547469 писал(а):

$$2^{\left\lfloor\frac{n}{2}\right\rfloor+\operatorname{nextprime}(\left\lfloor\frac{n}{2}\right\rfloor)} \equiv 1 \pmod n$$

Если n чётно, это не выполняется. Попробуйте упростить выражение слева, если n нечётно и $\frac{n-1}2$ простое