2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Вычислить a^n mod m
Сообщение15.10.2014, 17:57 
Исходная задача $5^{614} \pmod {1135}$ с помощью теоремы Ферма свелась к $5^{161} \pmod {227}$. Можно ли последнее посчитать вручную?

 
 
 
 Re: a^n mod m
Сообщение15.10.2014, 17:59 
Легко. Используйте бинарный алгоритм.

Можно также заменить показатель $161$ на $-65$, но сначала нужно будет алгоритмом Евклида найти $5^{-1} \bmod{227}$.

 
 
 
 Re: a^n mod m
Сообщение15.10.2014, 18:06 
nnosipov в сообщении #919264 писал(а):
Легко. Используйте бинарный алгоритм.

а где его взять?
где почитать?
Нужны примеры решения таких задач. наверняка они здесь не раз появлялись, но сейчас ничего не могу найти.

 
 
 
 Re: a^n mod m
Сообщение15.10.2014, 18:21 
Гуглите "Алгоритмы быстрого возведения в степень по модулю". Примеры сами сочините, проверку можно проделать в какой-нибудь системе компьютерной алгебры.

 
 
 
 Re: a^n mod m
Сообщение15.10.2014, 18:30 
nnosipov в сообщении #919274 писал(а):
Гуглите "Алгоритмы быстрого возведения в степень по модулю".

Дело в том, что подавляющее большинство того, что попадается в сети на эту тему, предназначенно для реализации на ПК, но не адаптировано под ручной счет

 
 
 
 Re: a^n mod m
Сообщение15.10.2014, 18:34 
Бинарный алгоритм (последовательное возведение в квадрат) довольно прост. Разберите его прямо на Вашем примере.

 
 
 
 Re: a^n mod m
Сообщение15.10.2014, 20:02 
да, я понял как работает этот алгоритм. но правда без калькулятора здесь всё равно не обойдешься )

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group