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

Question

[Кирилл Таран]

Сегодня смотрел задачу про последние десять цифр выражения 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

Answer 1

[Владимир Мартьянов]

За физический смысл ничего не скажу, но операция A^B (mod N) (BN_mod_exp в OpenSSL) сплошь и рядом применяется при реализации RSA.

Answer 2

[Mrrl]

Ну, например. Проводите вы какие-нибудь сложные вычисления, например, считаете определитель большой матрицы методом Гаусса. Получилось какое-то маленькое значение, но ошибка при вычислениях могла накопиться большая, и вы не уверены, 0 это или, скажем, 1 (у исходной матрицы коэффициенты целые). Что делать? Посчитать по какому-нибудь модулю. Если повезло и в процессе не пришлось делить на 0, то результат по этому модулю окажется правильным, и если получился не 0 - то значит, и вещественное число было ненулевым. Если же по нескольким разным модулям получились нули, то с большой вероятностью определитель действительно нулевой.
Модулярная арифметика может пригодиться для перемножения многочленов или больших чисел с помощью быстрого преобразования Фурье. Или для каких-нибудь расчётов, когда вообще неважно, чему равны числа, лишь бы они были ненулевыми и независимыми. В общем, случаи редкие, но когда они встречаются, неплохо бы об этом приёме знать.
А, да, ещё была "многомодульная геометрия" - когда с помощью модулярной арифметики проверяли, равны ли радиусы двух сфер. Хотя это олимпиадное программирование...