xkeirainx
@xkeirainx
Фулстэк энтерпрайз разной степени кровавости

Каков физический смысл модуля при модульном возведении в степень?

Сегодня смотрел задачу про последние десять цифр выражения 1^1 + 2^2 + ... + n^n. В данном случае интуитивно, я не математик, понятно, что модуль должен быть @mod = power(10, 10), а Wikipedia приводит в примерах 595^703 (mod 991).

Вопрос: что может дать выбор модуля 991? Как и какие модули используются на практике?

Псевдо-SQL для привлечения внимания:
function dbo.ufnModPow (@number numeric, @exp numeric, @mod numeric)
returns numeric 
as
begin
	declare @e numeric = 1
	declare @c numeric = 1
	
	while @e < @exp + 1
	begin
		set @c = (@c * @number) % @mod
		set @e = @e + 1
	end

	return @c
end

while @curr < @number + 1
begin
	set @sum = @sum + dbo.ufnModPow (@curr, @curr, @mod)
	set @curr = @curr + 1
end

print @sum
  • Вопрос задан
  • 220 просмотров
Решения вопроса 2
@vilgeforce
Раздолбай и программист
За физический смысл ничего не скажу, но операция A^B (mod N) (BN_mod_exp в OpenSSL) сплошь и рядом применяется при реализации RSA.
Ответ написан
Mrrl
@Mrrl
Заводчик кардиганов
Ну, например. Проводите вы какие-нибудь сложные вычисления, например, считаете определитель большой матрицы методом Гаусса. Получилось какое-то маленькое значение, но ошибка при вычислениях могла накопиться большая, и вы не уверены, 0 это или, скажем, 1 (у исходной матрицы коэффициенты целые). Что делать? Посчитать по какому-нибудь модулю. Если повезло и в процессе не пришлось делить на 0, то результат по этому модулю окажется правильным, и если получился не 0 - то значит, и вещественное число было ненулевым. Если же по нескольким разным модулям получились нули, то с большой вероятностью определитель действительно нулевой.
Модулярная арифметика может пригодиться для перемножения многочленов или больших чисел с помощью быстрого преобразования Фурье. Или для каких-нибудь расчётов, когда вообще неважно, чему равны числа, лишь бы они были ненулевыми и независимыми. В общем, случаи редкие, но когда они встречаются, неплохо бы об этом приёме знать.
А, да, ещё была "многомодульная геометрия" - когда с помощью модулярной арифметики проверяли, равны ли радиусы двух сфер. Хотя это олимпиадное программирование...
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы