Обсуждение:Тест Миллера — Рабина

Нестыковка

Нестыковка: написано в двух местах:

1. "Выбирается случайное число a, 1 < a < m"
2. "Выбрать случайное целое число a в отрезке [2, m − 2]"

Какое из них верно?

[Добавлено] вообщем, надо исправить на "Выбрать случайное целое число a в отрезке [2, m − 1]"

А смысл? m-1 по модулю m это -1, алгоритм сразу его пропустит. Предлагаю исправлять в другом месте. -- X7q 18:50, 3 апреля 2012 (UTC)

Нестыковка: первая проверка свидетеля простоты заключается в сравнении $~a^{t}\equiv 1{\pmod {m}}$, однако первое условие в псевдокоде сравнивает и с 1, и с (m-1). В чём подвох? 109.184.205.109 07:40, 25 октября 2012 (UTC) скромный студент

Теорема Рабина

Я могу привести небольшой набросок доказательства того, что вероятность ошибки теста миллера-рабина ≤ 2^(-r), если это кому-нибудь надо, конечно же. 178.158.140.22 11:42, 30 октября 2011 (UTC)

• Вообще-то даже $\leq 4^{-r}=2^{-2r}$, если по Рабину. Речь идёт как раз о теореме Рабина. Vlsergey 04:32, 9 января 2012 (UTC)
  • Согласен с последним. Добавил ссылку на статью-источник к последнему утверждению. Dmitriy.borodiy 07:30, 21 октября 2014 (UTC)

Свидетели

Сравниваю текст в en. и ru. и вижу, что термин «свидетель» используется противоположно: «свидетель простоты» versus «свидетель, того что число, составное». Есть ли АИ?

• Например, статья Гашкова. Maxal 03:13, 9 января 2012 (UTC)
• Да, это более распространенный термин в русскоязычной мат. литературе. Dmitriy.borodiy 07:31, 21 октября 2014 (UTC)

Обозначения

Вроде бы первая половина статьи написана о числе p, а вторая половина статьи о том же самом (?) числе n. Надо бы как-то сохранять однообразие.

• Вы правы, исправил. — Алексей Копылов 04:11, 16 декабря 2016 (UTC)

Внутри рамки с доказательством, кажется, тоже надо поправить.

• Там не обязательно: это отдельная лемма. — Алексей Копылов 20:01, 16 декабря 2016 (UTC)