Обсуждение:Тест Соловея — Штрассена

Неправильная формула

В интернете, на 99% сайтов опубликована неверная формула. В большинстве случаев mod(p) блуждает, и зачастую указывается то в левой, то в правой части. Но правильно-то писать в обоих! Я долго пытался реализовать рабочий тест Соловея-Штрассена по этим алгоритмам, включая этот, с Вики, и вечно простое число признавалось составным. После разборок я нашёл верную формулу: $\textstyle w^{(m-1)/2}{\pmod {m}}\equiv \left({w \over m}\right){\pmod {m}}$ При этом следует учесть, что остаток от отрицательных чисел в тестах на простоту всегда положителен, т.е. -1 mod m=m-1 (к примеру, -2 mod 5 = 3). Таким образом, число составное, если выполняются оба условия: $w^{(m-1)/2}{\pmod {m}}\not \equiv \left({w \over m}\right)$ и $w^{(m-1)/2}{\pmod {m}}\not \equiv \left({w \over m}\right)+m$ Не знаю, откуда появилось заблуждение по поводу формулы, но гарантирую, что вариант, предложенный выше, верен. Программа, созданная мною по этому алгоритму, никогда не ошибётся, назвав простое число составным, а составные числа вычисляет с указанной точностью. Я не первый раз эту страницу правлю, потому что кто-то, видимо, вычитав в интернете неправильный вариант, портит формулу. Заблокируйте редактирование, пожалуйста.

Неправильно. Вам очевидно вообще не преподавали теорию чисел, а то вы говорите полную нелепость. Нотация $a\equiv b{\pmod {m}}$, используемая в статье, совершенно правильна, общепринята, и всего лишь обозначает тот факт, что a и b сравнимы по модулю m. Т.е. (a - b) делится на m. Никакой операции взятия по модулю всего лишь в правой части тут нет. -- X7q 19:01, 31 марта 2012 (UTC)

Название

Правильно - Тест Соловея — Штрассена 89.178.100.152 19:48, 18 ноября 2009 (UTC)

Green apple 21:49, 18 ноября 2009 (UTC) Cпасибо за исправления

Заблуждение

В определении сказано: Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. По алгоритму всё наоборот: он точно определяет, что число является составным, а то что оно может являться простым, он может сказать только с долей вероятности. Ch00b

Немного запутанная формулировка, да, но я не улавливаю противоречий. По моему заблуждаетесь где-то вы. Если на вход подается простое, он всегда скажет "вероятно простое". Если составное - может сказать "точно составное" или "вероятно простое" (т.е. ошибиться). Ну и где тут противоречие? -- X7q 06:23, 17 января 2012 (UTC)

Понятно. Почему алгоритм выдаёт, что 5 составное? Если взять в качестве случайного числа 2. Символ Якоби тогда равен 1, а значение выражения 2^( (5-1)/2 )=4. Но 1 не равно 4. И алгоритм говорит, что число 5 составное. Напишите, пожалуйста, кто понимает, в чём проблема. Я уже несколько часов пытаюсь довести до ума программу. Ch00b

Всё, нашёл ошибку — неверно вычислялся символ. Прошу прощения за беспокойство. Ch00b