Генерация больших простых чисел

[netang]

Здравствуйте.

Дано такое утверждение:

Цитата:

Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма.

Пусть $N$, $S$ --- нечётные натуральные числа, $N-1 = S R$, причем для каждого простого делителя $q$ числа $S$ существует целое число $a$ такое, что

$a^{N-1}=1(\mod N), НОД( a^{(N-1)/q}-1, N ) = 1$
Тогда каждый простой делитель $p$ числа $N$ удовлетворяет сравнению $p = 1(\mod 2S)$

Следствие.

Если выполнены условия теоремы Ферма и $R \leqslant 4S+2$, то $N$ --- простое число.

http://algolist.manual.ru/maths/teornum/gene_prime.php
Как получили выражение для условия $R \leqslant 4S+2$? Почему поставили такое ограничение $a^{N-1}=1(\mod N), НОД( a^{(N-1)/q}-1, N ) = 1$? Не могли бы вы позадавать наводящие вопросы, чтобы я смог понять? Спасибо.

[gevaraweb]

(Оффтоп)

netang в сообщении #1210365 писал(а):

Не могли бы вы позадавать наводящие вопросы, чтобы я смог понять? Спасибо.

Чувак то жгет :)

[Brukvalub]

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

[netang]

Я могу ошибаться, но посмею предположить, что только единица удовлетворяет этому условию.

[Brukvalub]

Верно. А зачем я это спросил?

[Sonic86]

netang в сообщении #1210365 писал(а):

Почему поставили такое ограничение $a^{N-1}=1(\mod N), НОД( a^{(N-1)/q}-1, N ) = 1$?

Это можно понять, прочитав про тест простоты Люка (например в Вики: https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 0%BA%D0%B0), он проще, чем это утверждение, и сильно понятнее.