Цитата
Реализация вероятностного алгоритма Соловея-Штрассена
Алгоритм Соловея-Штрассена:
Выбирается случайное a из {1, ..., n - 1}. Проверяем условие НОД(a,n)=1
Если (1) не выполнено, то n – составное
Проверяем сравнение a^((n-1)/2) = a/n (mod n)
Если (3) не выполнено, то n – составное
В противном случае результат не известен
Алгоритм Соловея-Штрассена:
Выбирается случайное 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 ?