# 快速幂模的两种实现

## ALGORITHM 1.

``````INPUT: a, e, b;
INIT: Res = 1, a = a mod b

LOOP (e IS NOT 0):
IF e % 2 == 1:
Res = (Res * a) mod b
END IF

a = a * a
e = e / 2
ENDLOOP

OUTPUT: Res = a^e mod b
``````

## ALGORITHM 2.

``````INPUT: a, e, b;
INIT: Res = 1, a = a mod b

LOOP (digit d in binary e, from left to right):
IF d == 1:
Res = Res * Res * a mod b
ELSE:
Res = Res * Res mod b
ENDIF
ENDLOOP

OUTPUT: Res = a^e mod b
``````

## CODE:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 `````` ``````#include #include #include int alkltr(int a, int e, int b); int alkrtl(int a, int e, int b); int main(){ // To calculate : (a^e) mod b int a,b,e; while(1){ scanf("%d %d %d",&a,&e,&b); printf("left to right: %d^%d mod %d = %d\n", a,e,b,alkltr(a,e,b)); printf("right to left: %d^%d mod %d = %d\n", a,e,b,alkrtl(a,e,b)); } return 0; } int alkrtl(int a, int e, int b){ // 这是脑子正常的快速幂模 // e&1 即取 e 二进制末位 // e>>1 右移一位对应 e=e/2 int res = 1; a %= b; while (e){ if(e&1){ res = (res * a) % b; } a = (a*a) %b; e = e >> 1; } printf("\n"); return res; } int aikltr(int a, int e, int b){ // 这是脑子不太正常的快速幂模 int res = 1; a %= b; int len=0; int e2 = e; while(e2){ len++; e2 = e2>>1; } while(len){ len --; if((e&(1<
```the comment system on this blog works via email. The button