Автор: M.US 28.12.2006 5:19
Цитата
Реализация вероятностного алгоритма Соловея-Штрассена
Алгоритм Соловея-Штрассена:
Выбирается случайное a из {1, ..., n - 1}. Проверяем условие НОД(a,n)=1
Если (1) не выполнено, то n – составное
Проверяем сравнение a^((n-1)/2) = a/n (mod n)
Если (3) не выполнено, то n – составное
В противном случае результат не известен
Мне не понятно как происходит сравнеие a^((n-1)/2) = a/n (mod n)
Пусть даны
a=2
p=7, тогда
2^((7-1)/2)=2/7(mod 7)
2^3= 2/7 (mod)7
Вопрос, как получаеться 2/7, ведь 8 (mod7)=1
Пожалуйста распишите как получаеться 2/7 ?
Автор: hiv 28.12.2006 13:58
Может http://72.14.205.104/search?q=cache:YoKiZotPXB8J:www.5ballov.ru/referats.php%3Fdo%3Dget_file%26ref_id%3D70570%26key%3D5A2E3966554567704532386577+%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC+%D0%A1%D0%BE%D0%BB%D0%BE%D0%B2%D0%B5%D1%8F-%D0%A8%D1%82%D1%80%D0%B0%D1%81%D1%81%D0%B5%D0%BD%D0%B0&hl=ru&gl=ru&ct=clnk&cd=16&client=firefox-a найдешь ответ...