Тест для чисел Ферма

[nnosipov]

Dmitriy40 в сообщении #1654963 писал(а):

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

Да не было никакого обоснования. При $n=16$ тест заведомо врет, про значения $n>32$ вообще ничего неизвестно, кроме какой-то мелочи (я случайно помню, например, что число $F_{1945}$ составное, ибо делится на $5 \cdot 2^{1947}+1$). Так что на данный момент любой подобный тест будет вопросом веры, а не доказательства. Вот ТС верит, что число $F_{196}$ простое... Было бы прикольно, если б так и оказалось :)

[Dmitriy40]

Гораздо забавнее найти простое $F_n$ для $n$ из условия выше $2^n\equiv n\pmod{n+2}$, т.е. когда данный тест ошибается в обратную сторону, тогда его польза точно обнулится.
И кстати не так уж и мало известно про разные $F_n$.

[nnosipov]

Dmitriy40 в сообщении #1654992 писал(а):

И кстати не так уж и мало известно про разные $F_n$.

Да, действительно, я давно не интересовался этим вопросом.

[Батороев]

Dmitriy40 в сообщении #1654963 писал(а):

Я так понял после контрпримера утверждение просто смягчилось с "отсеивает все" до "отсеивает почти все" (составные).

Надеюсь, что хотя бы Ваши слова будут услышаны. Спасибо!

Dmitriy40 в сообщении #1654963 писал(а):

Вот только обоснования я так и не понял, математического (а не этой повторённой кучи слов), даже есть ли оно. Насколько вообще отличается вероятность для произвольного $n$ оказаться отсеянным (число Ферма составное) от 50%? Т.е. насколько данному тесту вообще можно верить? Вы поняли? Тесты этого не показывают, слишком по малому чисел Ферма известен вердикт.

Наверняка Вам известно понятие - "свидетели простоты", используемые в различных тестах, например, в тесте Миллера-Рабина.
В моем тесте отражен механизм нахождения свидетелей простоты для чисел Ферма, т.е. тех чисел до
$F_{n}$, которые имеют остатки: $(-1)\pmod {F_{n}}$ и $1\pmod {F_{n}}$ в степенях $\dfrac{F_{n}-1}{2}$ и $F_{n}-1$ соответственно.
Свидетели простоты получаются путем умножения числа $a$, имеющего в степени $2^n-n-1$ остаток $2\pmod {F_{n}}$ на числа, имеющие в этой степени остаток $1\pmod {F_{n}}$. Чтобы у полученного свидетеля были такие же остатки, как и у числа $a$ в $n+1$ последних степенях, но при этом, чтобы все степени были "задействованы", необходимо соблюдение условий, определяемых формулой (1) теста.

-- 17 сен 2024 19:28 --

Намедни составил вспомогательный тест к первому, которым можно проверять числа, к которым имеются сомнения после применения первого теста. Например, он отсеял некоторые ЧФ, упомянутые ранее:

Dmitriy40 в сообщении #1652665 писал(а):

$F_n, n=\{196, 2836, 4551, 5956, 25936, \}$

(остальные проверить не смог).
С числом $F_{16}$ так и остались "непонятки". Уж думаю, не число ли Кармайкла оно?
Вот уравнение вспомогательного теста, в котором использовал остатки по основанию $4$:

$$2^n\equiv 0 \pmod {n}$$

nnosipov в сообщении #1654971 писал(а):

Вот ТС верит, что число $F_{196}$ простое...

Да, вроде не было такого.

[Dmitriy40]

Он не просто отсеял некоторые, он отсеял практически все, оставив только $n=\{4,16,65536\}$ (до $n<10^9$ других $n$ не осталось). Если выполняется $n_{i+1}=2^{n_i}$, то следующее не отсеянное $n=2^{65536}$ (это почти 20 тысяч цифр в $n$).
Можно и не выдумывать тесты, а сразу сказать что простых $F_{n>4}$ нет.

[Батороев]

Dmitriy40
Я потихоньку склоняюсь к этому мнению... но и полной уверенности в своих тестах нет.