求方幂模s = a^j mod p

在编写程序时，经常求方幂模，即s = a^j mod p

而如果先求a^j，则可能会导致溢出，于是采用了一种避免溢出的算法ModularExponent

伪代码：

ModularExponent(a, j, p){ //求方幂模s=aj mod p, 注意先求aj可能会溢出 s ← 1; while j>0 do { if (j is odd) s ← s·a mod p; a ← a2 mod p; j ← j div 2; } return s; } 运行正确的代码（C语言编写）：

#include <stdio.h> #include <stdlib.h> // return a^j mod p int ModularExponent(int a,int j, int p){ int s = 1; while(j>0){ if(j%2==1) s = (s*a)%p; a = (a*a)%p; j = j/2; } return s; }一点补充：

X={a^j mod p | j ≥ 1}，X中的j至多为p-1，由此可得一种在X中随机，均匀和独立地取一个元素的算法。

Draw (a, p) { // 在X中随机取一元素 j ← uniform(1..p-1); return ModularExponent(a, j, p); // 在X中随机取一元素 }