Арифметика по модулю.

← →
MBo © (2003-08-25 14:15) [0]

Любопытная задачка оказалась (в чате вчера спросили):

Найти остаток по модулю С от A в степени B, т.е.
(A^B) mod C

A,B,C:DWord;

← →
Romkin © (2003-08-25 14:26) [1]

Если не ошибаюсь, остаток произведения по модулю равен произведению остатков по модулю :)

← →
MBo © (2003-08-25 14:34) [2]

ага, так сложность O(B) получится. А можно и лучше ;)

← →
nikkie © (2003-08-25 14:52) [3]

> сложность O(B) получится
ну не надо... сложность возведения в степень N - O(log(N))
тем более, что по модулю С достаточно возводить в степень не N, а в степень (N mod \phi(С)), где \phi - функция Эйлера.

можно еще дискретным логарифмом воспользоваться, но оценить его сложность я на вскидку не могу. вроде быстрее не получится (если стоит задача единоразовой операции).

← →
MBo © (2003-08-25 15:13) [4]

>nikkie ©
Угу, моя промашка - я сначала в степень простым циклом по одному возводил, вот и не воспринял сразу ;)

C функцией Эйлера интересно - не знал про это. Действительно, для c=10 Phi=4, а степени чисел по модулю 10 имеют макс. периодичность именно 4. Правда, вычислять ее накладно, за исключением случаев многократных вычислений для одного С.

Если кому-то интересно:
function APowerBModC(A,B,C:DWord):DWord; asm push ebx push esi push edi mov ebx,eax //A mov esi,ecx //C mov ecx,edx //B mov edi,1 //Temp test ecx,ecx jz @@Finish @@LoopStart: test ecx,1 //Odd jz @@Reduce mov eax,edi call @@LModulus mov edi,eax // Temp:=(Temp*A) mod C @@Reduce: shr ecx,1 // B div 2 jz @@Finish mov eax,ebx call @@LModulus mov ebx,eax // A:=Sqr(A) mod C jmp @@LoopStart @@Finish: mov eax, edi pop edi pop esi pop ebx ret @@LModulus: xor edx,edx push ecx push edx push esi mul ebx //edx:eax - InputEAX*A call System.@_llmod pop ecx ret end;

Арифметика по модулю. Найти похожие ветки