Блин, все никак не могу домучить универское задание по RSA a, b, c - натуральные, порядка нескольких сотен. Как по-человечески посчитать выражение ( a ^ b ) mod c ? ОЧЕНЬ не хочется писать класс для работы с большими числами. Как в данном случае обойтись старым советским DWORD-ом ?
_DEN_ А в чем проблема? У тебя числа , т.е. в двойное слово ты влезаешь без проблем. Или ты сначала собираешься вычислить ВСЕ значение степени, а ПОТОМ вычислять модуль? Так это НЕ ОБЯЗАТЕЛЬНО! Ты можешь ПОСЛЕ КАЖДОГО умножения брать значение по модулю и дальше продолжать работать только с ним. В результате у тебя промежуточные значения всегда будут умещаться в двойном слове. И посмотри приведенный yureckor архив. Там есть краткое описание, где сказано, как значительно ускорить вычисление степени. (Ну а если же я тебя неверно понял, и проблема в другом, то извини...)
Sergey_R Понял нормально Тоесть... Блин, что-то я не понял Давай на примере: (117 ^ 341) mod 514. Ты хочешь сказать что (117 ^ 341) mod 514 = ((((117 mod 514) * 117) mod 514) * 117) mod 514) ... итд 341 раз ...) Так чтоли?
Так, только еще более эффективно - возводи некую переменную с начальным значением 117 в квадрат по модулю 514 и домножай на нее тоже по модулю там где нужно. Только вот вопрос есть в ограничениях на взаимную простоту a и с.
_DEN_ Да, именно! Арифметика по модулю это позволяет. НО! только, если делать "в лоб" ;о) Смотри. Допустим, Тебе нужно возвести в степень 8: a^8. Ты можешь 8 раз a*a*a*a*a*a*a*a, а можешь - ((a^2)^2)^2). Не 8 умножений (и взятий по модулю. а всего 3! Или b=18=16+2 -> a^b -> a^18 = (a^(16+2)) = (a^16)*(a^2) = ((((a^2)^2)^2)^2)*(a^2) или a^18 = (a^((8+1)*2)) = ((a^(8+1))^2) = ((((a^2)^2)^2)*a)^2 То есть, начиная со старшего бита проверяешь, если очередной бит равен "1", то умножаешь промежуточный результат на "a". Если биты еще не кончились, умножаешь промежуточный результат сам на себя (возможишь в квадрат), и переходишь к следующему биту. Что-то вроде: Код (Text): temp = a; // в любом случае, кроме b=0, тогда temp = 1. while ("просмотр битов от старшего к младшему") { temp = temp * temp; if ("очередной бит" == 1) temp = temp * a; } Ну и, естественно, взятие каждого промежуточного результата по модулю... ;о)
