Как применить тест простоты Люка для n+1?

[west0293]

Здесь, на странице 23, теорема 1.23 для проверки простоты числа n, если известно n-1 на простые сомножители. Внизу теоремы приписано:
"Аналогичный результат справедлив в случае, когда известно полное
разложение n + 1 на множители."
Вопрос: Как применить эту теорему, если известно разложение n+1 на простые множители? Просто заменять "n-1" на "n+1"? Мне кажется вряд ли.
Подскажите что с этим делать. Спасибо!

[nnosipov]

west0293 в сообщении #559975 писал(а):

Подскажите что с этим делать.

А прочитать далее формулировку теоремы 1.24 не догадались?

[west0293]

Так следующая теорема уже немного о другом, а мне нужно именно эту теорему применить для n+1.
И в теореме 1.24 говорится:

Цитата:

Эта теорема принадлежит к так называемым (N + 1)-методам про-
верки простоты чисел. Ее доказательство, равно как и описание других
результатов, относящихся к (N + 1)-методам, выходит за рамки данной
книги.

Вопрос: где можно еще найти существующие (n+1)-методы? Может у кого-нибудь есть литература по этой теме?

Но главный вопрос остается: как применить теорему 1.23 для (n+1)?

[Sonic86]

west0293 в сообщении #560379 писал(а):

Вопрос: где можно еще найти существующие (n+1)-методы? Может у кого-нибудь есть литература по этой теме?

Там есть тест простоты для чисел Ферма через числа Люка (теорема 1.5) - это и есть тест $n+1$ - посмотрите его в книге (там несколько лемм и утверждений).

west0293 в сообщении #559975 писал(а):

Вопрос: Как применить эту теорему, если известно разложение n+1 на простые множители? Просто заменять "n-1" на "n+1"? Мне кажется вряд ли.

Да, так просто не получится.

west0293 в сообщении #560379 писал(а):

Но главный вопрос остается: как применить теорему 1.23 для (n+1)?

Вы хотите аналог теоремы 1.23 для $n+1$-методов? - это и есть теорема 1.24. Вы почитайте доказательство теоремы 1.5 - Вы поймете, что это не усложнение, а действительно аналог.

[west0293]

Спасибо Вам большое за ответ! Немного поясню. Тест Люка–Лемера, например, для чисел Мерсенна или теорема 1.24 не дают такой «четкой» задачи, т.е. для каждого числа нужно вычислять число определенной последовательности, чтобы потом проверить его делимость на проверяемое число. И чтобы найти это число (которое нужно делить) надо вычислять ВСЕ числа этой последовательности до искомого.
А теорема 1.23 сразу представляет чёткую формулу, и не нужно проводить кучу лишних операций.
Вот меня и интересуют такие же тесты только для (n+1).
Извините, что так много вопросов, просто я изучаю это всё самостоятельно, в универе нас такому не учат, а мне интересно. :)

[Sonic86]

Не могу понять, почему Вы решили, что тест простоты для чисел Мерсенна хуже (сложнее) чем теорема 1.24. Тест простоты чисел Мерсенна - это частный случай этой теоремы: $M_p+1=2^p$ - всего один простой делитель, поэтому проверяется всего одна делимость, а в теореме будет проверяться несколько аналогичных делимостей - для каждой делимости нужно считать $u_n$. Для чисел Мерсенна это особенно просто, поскольку мы можем $u_{2^{k+1}}$ выразить через $u_{2^k}$ и этого здесь достаточно. В теореме 1.24 придется в общем случае мучиться со всякими цифрами: мы будем представлять $n+1$ и $\frac{n+1}{q}$ в двоичном виде и потом считать $u_{2^k}$ и потом уже из них конструировать нужные нам $u_{\frac{n+1}{q}}$.

[west0293]

А как тогда с помощью теоремы 1.24 показать простоту, например, числа Мерсенна 7 ?

[Sonic86]

Ну в лоб так и доказывать. После всех упрощений будет то же самое, что и теорема 1.5.
Или я что-то не понял?