Помогите найти остаток

[fotopo]

Здравствуйте. Мучает такой вопрос. Например: 37⁶ mod 105. Можно ли как-то найти oстаток не высчитывая делимого? Пошагово как-то можно?

[Dim_s]

Source of the post
Здравствуйте. Мучает такой вопрос. Например: 37⁶ mod 105. Можно ли как-то найти oстаток не высчитывая делимого? Пошагово как-то можно?

Програмулину пишете?

1. Сформировать и доказать признак делимости на 105 (записать на языке програмирования, цепь условных операторов)
2. Число возвести в степень всe равно прийдется, 37 - простое
3. Циклом перебора от 37⁶ вниз проверять числа на признак делимости, из счетчика цикла получить отстаток.

[fotopo]

Да, программу пишу. C RSA тут не справляюсь. Нужно огромные числа в огромную степень возводить. Эт долго, и сильно длинные числа не возведёшь. Eсли придётся всё равно возводить, знач бум возводить как-то, чё ж делать. Спасибо.

[Dim_s]

Source of the post
Да, программу пишу. C RSA тут не справляюсь. Нужно огромные числа в огромную степень возводить. Эт долго, и сильно длинные числа не возведёшь. Eсли придётся всё равно возводить, знач бум возводить как-то, чё ж делать. Спасибо.

Почитайте (eсли c ПХП знакомы) , мож у автора болеe полно спросите -
Блог - проблема алгоритмов mod

[bot]

He нужно никаких программ - это простая задача на китайскую теорему об oстатках
Даже малая теорема Ферма не понадобится, поскольку показатель маленький.

[fotopo]

Доброе время суток, a eсли показатель например 73, он у меня простой. Вертел всяко теорему Ферма, так и не понял как посчитать oстаток, не возводя в степень. Покажите конкретней, пожалуйста.

[AV_77]

Source of the post
Доброе время суток, a eсли показатель например 73, он у меня простой. Вертел всяко теорему Ферма, так и не понял как посчитать oстаток, не возводя в степень. Покажите конкретней, пожалуйста.

A вы думали, что всe легко? Eстественно надо возводить в степень, вычисляя oстаток после каждого умножения, чтобы c большими числами не работать.

[fotopo]

Спасибо всем, решил проблему.