Прогресс в теории простых чисел и методы шифрования

[B3LYP]

Хочу разобраться с тестом Миллера-Рабина. Это ведь он используется в реальном RSA-шифровании?
В википедии используются формулы с обозначениями, которые я пока не совсем понимаю:
$a^d=1(\mod n)$
Что это означает - что $a^d-1$ делится нацело на n?
И второй вопрос: есть детерминистический вариант теста, который называется тестом Миллера, но он опирается на недоказанную пока расширенную гипотезу Римана. Но как же принцип фальсифицируемости? Почему нельзя использовать в алгоритмах тест Миллера, до тех пор пока хоть раз обнаружится что он не сработает и гипотеза Римана окажется ошибочной?

[Dmitriy40]

B3LYP в сообщении #1737241 писал(а):

Хочу разобраться с тестом Миллера-Рабина. Это ведь он используется в реальном RSA-шифровании?

Не обязательно, использовать можно любой тест простоты, алгоритм RSA никаких требований на тест простоты вроде бы не накладывает.

B3LYP в сообщении #1737241 писал(а):

$a^d=1(\mod n)$
Что это означает - что $a^d-1$ делится нацело на n?

Да.

B3LYP в сообщении #1737241 писал(а):

И второй вопрос: есть детерминистический вариант теста, который называется тестом Миллера, но он опирается на недоказанную пока расширенную гипотезу Римана. Но как же принцип фальсифицируемости? Почему нельзя использовать в алгоритмах тест Миллера, до тех пор пока хоть раз обнаружится что он не сработает и гипотеза Римана окажется ошибочной?

Можно. И если найдётся такое составное число, что проходит тест Миллера, то видимо (насколько я понимаю) это и будет свидетельством что GRH неверна.
Но тест Миллера - медленный! По сравнению с вероятностными тестами. И потому на практике его не используют. А перебирать составные числа из десятков (больше 36) цифр и надеяться что вот оно наконец пройдёт тест Миллера - занятие очень так себе, малопродуктивное, ведь если GRH таки верна, то такого составного числа и не найдётся, никогда, сколько ни считай.

-- добавлено через 5 минут --

B3LYP в сообщении #1737241 писал(а):

В википедии используются формулы с обозначениями, которые я пока не совсем понимаю:

Учитывайте что на разных страницах вики используются разные обозначения! И n в RSA может быть вовсе не тем же что n в тесте Ферма (или тесте простоты).
Даже на одной странице обозначения могут "гулять" в зависимости от контекста.

[B3LYP]

Почитал про тест Миллера-Рабина, считаю примеры, и возникли три вопроса:
1) Числа a, которые становятся свидетелями простоты, могут быть любыми (от 2 до n) или же только простыми?
2) Число r может быть равно нулю, или оно может быть только от 1 до s-1 (s это количество двоек в разложении n-1)?
3) Правильно ли я понял, что надо перебирать все варианты r от 0 (или там от 1) до s-1, и если хотя бы раз сработает $(a^{2^r \cdot d}) \mod n = -1$, то значит a это свидетель простоты n?
4) Соответственно, если n-1 нечётное, то есть s=0, то вторая проверка не проводится? Хотя я вроде уже понял что ответ тривиален - если n-1 нечётное значит n составное - но чисто с формальной точки зрения вопрос.

[Dmitriy40]

B3LYP в сообщении #1737294 писал(а):

1) Числа a, которые становятся свидетелями простоты, могут быть любыми (от 2 до n) или же только простыми

ГуглИИ:

Цитата:

В качестве базы $a$ можно выбирать как простые числа (например, 2, 3, 5), так и составные (например, 4, 6, 9).
На практике обычно проверяют, чтобы наибольший общий делитель $\gcd(a, n) = 1$. Если вдруг $\gcd(a, n) > 1$, то мы мгновенно находим делитель числа n, и тест можно даже не продолжать — число n гарантированно составное.

Из $\gcd$ мгновенно следует что проверять достаточно лишь простые a, составные а имеют в своём составе меньшие простые и такие делители найдутся раньше составного при проверке начиная с меньших а.

B3LYP в сообщении #1737294 писал(а):

2) Число r может быть равно нулю, или оно может быть только от 1 до s-1 (s это количество двоек в разложении n-1)?

Вики про тест Миллера-Рабина писал(а):

$ \forall r: 0 \leq r \leq s-1: a^{2^{r}d}\not \equiv -1{\pmod {n}}$

Видите левое условие на $r$? Если $r=0$, то $a^d=-1\pmod n$, т.е. $a^d+1$ делится на $n$. Вполне возможно такое.

B3LYP в сообщении #1737294 писал(а):

3) Правильно ли я понял, что надо перебирать все варианты r от 0 (или там от 1) до s-1, и если хотя бы раз сработает $(a^{2^r \cdot d}) \mod n = -1$, то значит a это свидетель простоты n?

Да.
Потому что если ни для одного $0 \leq r < s$ условие не сработало (и не сработало $a^d=1\pmod n$), то такое a будет свидетелем составного числа n (и оно точно составное).

B3LYP в сообщении #1737294 писал(а):

4) Соответственно, если n-1 нечётное, то есть s=0, то вторая проверка не проводится? Хотя я вроде уже понял что ответ тривиален - если n-1 нечётное значит n составное - но чисто с формальной точки зрения вопрос.

Ну можно и провести для $r=0$ (и даже может получиться что такое a будет свидетелем простоты), но толку-то, мы же и так уже знаем что n составное, зачем делать лишнюю работу.

[B3LYP]

Я уже писал что пробую себя в роли популяризатора и "объяснятора", и ниже пишу текст про тест Миллера-Рабина - просьба прокомментировать, насколько всё верно написано:

(Оффтоп)

Цитата:

Рассмотрим тест Миллера-Рабина на простоту чисел. Чтобы определить, является ли число n простым либо составным, надо взять n-1 и разложить его на множители, точнее определить, сколько среди его множителей двоек. Нужно выписать n-1=2^s * d, то есть здесь s это число двоек среди набора простых делителей числа n-1, а d это произведение всех остальных делителей, и d всегда нечётно. Для любого n-1 можно только одним образом определить s и d. Можно не рассматривать варианты где s равно нулю, поскольку если n-1 нечётно, то значит n чётно и соответственно n составное.
Далее, мы выбираем случайное число a (лучше в качестве чисел a брать только простые числа), которое меньше n, и проверяем, выполняется ли одно из двух равенств:
(a^d) mod n = 1
(a^((2^r)*d) mod n)=-1
Во втором равенстве r это любое число от 0 до s-1, то есть нужно перебрать все возможные r от 0 до s-1 и если хотя бы в одном случае равенство сработает, то значит проверка сработала и ясно, что a является свидетелем числа n на простоту, и значит стала выше вероятность, что число n простое. Если же оба условия не выполняются, то мы точно знаем что число n составное. Ещё раз можно сказать так: мы берём число n-1 без двоек или с любым числом двоек, но не со всеми, и смотрим, даёт ли это число при делении на n остаток 1 (это когда с двойками не берём вообще) либо -1.
Разберём примеры:
1)
n=9
n-1=8 s=3 d=1
Возьмём a=2: (a^d) mod 10 = (2^1) mod 10 = 2 mod 10 = 2
Поскольку получилось не 1, мы теперь предполагаем что n составное. Но для проверки этого надо ещё пройти цикл со вторым условием:
(2^((2^0)*1) mod 10 = 2 mod 10 = 2
(2^((2^1)*1) mod 10 = 4 mod 10 = 4
(2^((2^2)*1) mod 10 = 16 mod 10 = 6
Нигде не получилось -1 (то есть 9), поэтому оба условия не выполнены, и теперь мы точно знаем что число 9 составное.
2)
n=11
n-1=10=2*5. s=1 d=5
Возьмём a=2:
(a^d) mod n = (2^5) mod 11 = 32 mod 11 = -1
Пока не получилось 1, проводим вторую проверку: перебираем r от 0 до s-1, то есть берём r=0, и считаем
a^((2^r)*d) mod n =2^((2^0)*5) mod 11 = 32 mod 11 = -1
Всё получилось, результат -1 означает что число 2 стало свидетелем простоты числа 11
Теперь попробуем a=3:
(3^5) mod 11 = 243 mod 11 =1
Совпало, число 3 свидетель простоты числа 11. Итого, поскольку уже два числа (2 и 3) стали свидетелями простоты числа 11, можно полагать что 11 наверняка простое (но чтобы убедиться в этом абсолютно точно, придётся перебирать разные a до 11).
3) n=13
n-1=12=(2^2)*3 s=2 d=3
Возьмём a=2:
(2^3) mod 13 = 9 mod 13 =-4
Проверка не прошла. Проводим вторую проверку: перебираем r от 0 до 1, и считаем
2^((2^0)*3) mod 13 = -4
2^((2^1)*3) mod 13 = 2^6 mod 13 = 64 mod 13 = -1
Проверка прошла, число 2 является свидетелем простоты числа 13. Теперь попробуем a=3:
3^3 mod 13 = 27 mod 13 = 1
Проверка прошла, число 3 является свидетелем простоты числа 13. С двумя свидетелями мы можем сказать что 13 это число наверняка простое.
4) n=15
n-1=14=2*7 s=1 d=7
Возьмём a=2:
2^7 mod 15 = 128 mod 15 = -7
Проверка с r:
2^7 mod 15 = -7
2^((2^1)*7) mod 15 = 2^14 mod 15 = 4096 mod 15 = 1

Обе проверки не сработали так что мы теперь точно знаем, что число 15 составное. В других случаях может быть так, что с каким-то a проверка проходит и a становится свидетелем числа n на простоту, но следующие проверки показывают что всё-таки n составное.

[mihaild]

B3LYP в сообщении #1737304 писал(а):

Я уже писал что пробую себя в роли популяризатора и "объяснятора"

Пожалуйста, не надо популяризовывать и объяснять вещи, которые сами не очень хорошо понимаете.
А вот что надо - правильно оформлять формулы.

[Dedekind]

(Оффтоп)

mihaild in post #1737305 писал(а):

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

Понимание приходит в процессе объяснения:)

[Dmitriy40]

B3LYP в сообщении #1737304 писал(а):

С двумя свидетелями мы можем сказать что 13 это число наверняка простое.

Вероятность ошибки в 6% не настолько мала чтобы надеяться на простоту числа. Пусть оно и правда простое.
С другой стороны, до 1.37млн нет составных чисел, для которых эти два основания одновременно являются свидетелями простоты. А до 2047 можно было ограничиться и лишь $a=2$. Правда это уже не теоретический результат, а практический, проверенный прямыми вычислениями.