Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Последний раз редактировалось Stasya7 15.10.2016, 23:56, всего редактировалось 2 раз(а).
Пусть требуется вычислить, например, . Я вычисляю где-то за 7-8 итераций. Может, можно быстрее? Может, есть какой-нибудь быстрый метод вычисления вот таких степеней?
StaticZero
Re: Редукция по модулю
16.10.2016, 00:04
Последний раз редактировалось StaticZero 16.10.2016, 00:05, всего редактировалось 1 раз.
(TeX)
Наведите мышкой на примеры, чтобы узнать код.
Simple Fairy
Re: Редукция по модулю
16.10.2016, 02:45
Последний раз редактировалось Simple Fairy 16.10.2016, 02:47, всего редактировалось 2 раз(а).
Если я правильно понимаю, то , и наименьшее такое, что , т.е. грубо говоря, является делителем . И в вашем случае 50 является делителем 100, а значит и сравнимо с единицей по модулю 101.
Ну, делителей у 100 много, вот хотя бы и 1, однако . Из теоремы Ферма мы доподлинно только знаем, что Stasya7, а какими средствами Вы владеете, про квадратичные вычеты слышали?