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

[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
Я потихоньку склоняюсь к этому мнению... но и полной уверенности в своих тестах нет.

[Батороев]

Составил новый тест проверки на простоту чисел Ферма:

$$2^{F_{n}}\equiv 2\pmod {(F_{n}-1)^2-1}$$

где $F_{n}$ число Ферма.
По сравнению с Тестом Пепина он более "громоздкий" с точки зрения объемов вычислений, но на мой взгляд, более информативный.

[nnosipov]

Батороев в сообщении #1694098 писал(а):

более информативный

Э-э, похоже, сравнение выполняется для любого $n$ (во всяком случае, для $n \leqslant 13$).

[Dmitriy40]

Вплоть по $n=20$ выполняется. Test failed, информации от него ноль.

[nnosipov]

Написав пару формул, понял, что сравнение верно для любого $n$. А что, как задача на экзамене, сойдет. Но до здешнего олимпиадного раздела сильно не дотягивает :)

[Батороев]

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

Э-э, похоже, сравнение выполняется для любого $n$ (во всяком случае, для $n \leqslant 13$).

Ну, тогда либо я сравнение не сумел составить, либо идея моя изначально не верна. (

-- 13 июл 2025 22:26 --

nnosipov
Dmitriy40


Спасибо в получении отрицательного результата! )