Тест простоты

[Pedja]

Гипотеза:
Пусть $n$ будет натуральным числом причем $n>1$. Пусть $F_n(x)$ будет полиномом Фибоначчи, тогда $n$ простое тогда и только тогда , когда $\displaystyle\sum_{k=0}^{n-1}F_{n}(k) \equiv -1 \pmod n\)$ .

Вы можете попробовать этот тест здесь (Conjecture 6).

[Dmitriy40]

Обычно ищут более быстрые тесты, а этот вылетает уже на числе $10001$.
Хотя если доказать гипотезу, то наверное будет полезно.

[nnosipov]

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

Хотя если доказать гипотезу, то наверное будет полезно.

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

Вообще, задействовать для теста на простоту числа $n$ суммы с $n$ слагаемыми как-то нелепо.

[Pedja]

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

Обычно ищут более быстрые тесты

Это правда. Посмотрите тест с временем выполнения $O (\log ^ 3 n)$, описанным в гипотезе 5.

[Dmitriy40]

nnosipov
Я думал полезно в плане математики, теории, не практики. Может там какие широкие следствия будут, или ещё что ...

[nnosipov]

Вот, кстати, надо бы спросить у ТС мотивировку этой гипотезы про многочлены Фибоначчи. Есть ощущение, что к такого рода вещам обычно интерес исключительно практический. Тест с многочленами Чебышева в этом плане гораздо лучше мотивирован.

[Soul Friend]

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

Вообще, задействовать для теста на простоту числа $n$ суммы с $n$ слагаемыми как-то нелепо

А это суммирование можно как-то сократить?

Pedja в сообщении #1437563 писал(а):

$\displaystyle\sum_{k=0}^{n-1}F_{n}(k) \equiv -1 (\pmod n\)$ .

По ссылке, там первую теорему ведь можно и так записать:
$(n-1)! \equiv (n-1) \pmod {n((n-1)/2)}$

[nnosipov]

Soul Friend в сообщении #1437604 писал(а):

А это суммирование можно как-то сократить?

Переадресуем этот вопрос ТС.

[Soul Friend]

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

Хотя если доказать гипотезу, то наверное будет полезно.

если докажут - будет нечто второго АКС теста. (по сложности)

[nnosipov]

(Оффтоп)

ozheredov
Iff --- это сокращение if and only if.

[ozheredov]

(Оффтоп)

nnosipov

Ээээ... спасибо, не знал
Сообщение удалено

[nnosipov]

Soul Friend в сообщении #1437621 писал(а):

если докажут - будет нечто второго АКС теста. (по сложности)

Здесь Вы какую гипотезу имеете в виду? С многочленами Фибоначчи?

[Soul Friend]

да

[nnosipov]

И как Вы собираетесь быстро вычислять левую часть сравнения?

[Dmitriy40]

Причём для $n>10^{30}$, к примеру, сильно меньшие не интересны.