Обсуждение:Тест Миллера — Рабина
Эта статья была кандидатом в добротные статьи русской Википедии. См. страницу номинации (статус не присвоен 11 декабря 2014 года). |
Эта статья входит в число добротных статей русской Википедии. См. страницу номинации (статус присвоен 5 декабря 2015 года). |
Нестыковка[править код]
Нестыковка: написано в двух местах:
- "Выбирается случайное число a, 1 < a < m"
- "Выбрать случайное целое число a в отрезке [2, m − 2]"
Какое из них верно?
[Добавлено] вообщем, надо исправить на "Выбрать случайное целое число a в отрезке [2, m − 1]"
- А смысл? m-1 по модулю m это -1, алгоритм сразу его пропустит. Предлагаю исправлять в другом месте. -- X7q 18:50, 3 апреля 2012 (UTC)
Нестыковка: первая проверка свидетеля простоты заключается в сравнении , однако первое условие в псевдокоде сравнивает и с 1, и с (m-1). В чём подвох? 109.184.205.109 07:40, 25 октября 2012 (UTC) скромный студент
Теорема Рабина[править код]
Я могу привести небольшой набросок доказательства того, что вероятность ошибки теста миллера-рабина ≤ 2^(-r), если это кому-нибудь надо, конечно же. 178.158.140.22 11:42, 30 октября 2011 (UTC)
- Вообще-то даже , если по Рабину. Речь идёт как раз о теореме Рабина. 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)