Необходимое условие простоты числа

[maximk]

$p \in\mathbb{P}$$\to p \mid p\sum\limits_{j=1}^{p-1}(-1)^jB_j+1$
Доказательство тривиально, утверждение теоремы следует из теоремы Вильсона и topic54476.html (домножим обе части сравнения на $p$ (в соотношении из теоремы Вильсона и в соотношении на странице, куда ведет ссылка (оставив модуль неизменным во втором соотношении)), выполним сокращение).
При $p=5$ это необходимое условие перестаёт работать. Где ошибка?
И да, насколько эффективны такие условия на практике в вычислительном плане?

[Lia]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»

[nnosipov]

maximk в сообщении #1020064 писал(а):

При $p=5$ это необходимое условие перестаёт работать.

Считать не умеете.

[maximk]

nnosipov, а что можете сказать по поводу самого этого необходимого условия в плане вычислительной сложности?

[nnosipov]

Ну вот представьте, что $p$ --- это 100-значное число. Как Вы собираетесь вычислять эту сумму? Она, слегка так, во вселенную не помещается.

[maximk]

nnosipov, так же, как вычислять по малой теореме Ферма, $a^1^0^0$ тоже прийдется втиснуть хоть в одну галактику. При всех своих недостатках преимущество необходимого условия через сумму чисел Бернулли в том, что эта сумма получается "достаточно маленькой" по отношению к $p$, как раз порядка $p$.

[arseniiv]

(Formulæ.)

maximk в сообщении #1020624 писал(а):

$a^1^0^0$

a^{100} $a^{100}$.
Так и проще, и правильнее.

[Sonic86]

maximk в сообщении #1020624 писал(а):

nnosipov, так же, как вычислять по малой теореме Ферма, $a^1^0^0$ тоже прийдется втиснуть хоть в одну галактику. При всех своих недостатках преимущество необходимого условия через сумму чисел Бернулли в том, что эта сумма получается "достаточно маленькой" по отношению к $p$, как раз порядка $p$.

maximk, ну я сильно извиняюсь, но ответьте на простые вопросы:
1. Какие тесты простоты вы знаете? (2-3 штуки назовите)
2. Какова сложность этих тестов? (оценки вида $O(f(p))$ или $\Theta(f(p))$)
3. Оцените хоть как-нибудь сложность вычисления указанной суммы.
4. Как Вы думаете, какова истинная сложность вычисления указанной суммы?

[maximk]

(Оффтоп)

arseniiv, спасибо.

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

[Sonic86]

maximk в сообщении #1020641 писал(а):

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

Ну елки.
Ну возьмите Кормен, Лейзерсон Ривест Алгоритмы: построение и анализ и прочитайте сколько-нибудь.
Рассмотрите множество конкретных примеров (можете просто почитать разные алгоритмы в Вики и их сложность)
(еще есть
Макконнелл Основы современных алгоритмов
Кнут Искусство программирования (II)
Василенко Теоретико-числовые методы в криптографии
Гасфилд Строки, деревья и последовательности в алгоритмах
Дасгупта Пападимитриу Алгоритмы)

[maximk]

Sonic86, может быть когда-нибудь почитаю (думаю, это будет не скоро), а пока не могли бы вы сказать, пригодна ли для практики вышеизложенная теорема?

[venco]

Нет.
Даже простое деление на все числа до корня будет быстрее.

[Sonic86]

maximk в сообщении #1020757 писал(а):

Sonic86, может быть когда-нибудь почитаю (думаю, это будет не скоро), а пока не могли бы вы сказать, пригодна ли для практики вышеизложенная теорема?

Попытайтесь понять сами, это очень легко, невероятно легко.
Если непонятно, выполните проверку ручками по указанному критерию для $p=211$.