Большую степень не вычисляют в лоб, тем более, что при выполнении действий в модульной арифметике её не нужно хранить целиком, достаточно хранить остаток от деления на известное постоянное число. Знак "тождественное равенство" используется как знак равенства в модульной арифметике, если модуль указан отдельно, поскольку сами числа, естественно, не равны.
Дискретное логарифмирование - формально, задача на пространстве решений, на котором можно применять модульную арифметику над многочленами или числами, с некоторым простым числом в качестве размера множества, частного для деления по модулю и вообще.
Саму степень по модулю можно вычислить довольно простым образом: Вначале раскладываем показатель на двоичные составляющие: 2*24 = 48 = 32+16 = 2^5+2^4. Потом пользуемся двумя тождествами: Первое x^(a+b)=x^a*x^b - произведение степеней одного числа равно степени числа в сумме показателей (забыл точное название). Второе (x*y) mod n = (x mod n)*(y mod n) - неважно, когда брать остаток, в начале или в конце. В итоге возведение числа 2 в большую степень по модулю N выполняется так: в результат заносится 1, в аргумент 2, потом в цикле по разрядам показателя если текущий двоичный разряд показателя 1, результат множится на аргумент и берется остаток по модулю N, который кладется в результат, а аргумент потом умножается на себя и остаток аргумента по модулю N кладется в аргумент.
Итого: аргумент принимает последовательно значения 2, 4, 16, 256, 65536 mod 541 = 75, 75*75 mod 541 = 215, а результат - 1, 1, 1, 1, 75, 75*215 mod 541 = 436.
Средний
