IPB
ЛогинПароль:

> Правила раздела!

1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!

> Реализация вероятностного алгоритма Соловея-Штрассена, есть кое-какие неясности
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 2
Пол: Мужской

Репутация: -  0  +


Цитата
Реализация вероятностного алгоритма Соловея-Штрассена

Алгоритм Соловея-Штрассена:
Выбирается случайное 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 ?


 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 20:35
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name