南京专门做网站,软件开发网站,网站正在建设中动画,河间哪里有做网站的算法原理#xff1a;指数分解的魔法
快速取模指数算法基于指数二进制分解和模运算分配律#xff1a;
(a * b) mod m [(a mod m) * (b mod m)] mod m
a^(2k) (a^k)^2计算步骤#xff1a;
将指数转换为二进制形式从最低位开始遍历二进制位当前位为1时累积结果每一步对底数…算法原理指数分解的魔法
快速取模指数算法基于指数二进制分解和模运算分配律
(a * b) mod m [(a mod m) * (b mod m)] mod m
a^(2k) (a^k)^2计算步骤
将指数转换为二进制形式从最低位开始遍历二进制位当前位为1时累积结果每一步对底数进行平方模运算指数位右移除以2 #mermaid-svg-0WbjsCdv3bPEpP1R {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-0WbjsCdv3bPEpP1R .error-icon{fill:#552222;}#mermaid-svg-0WbjsCdv3bPEpP1R .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-0WbjsCdv3bPEpP1R .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-0WbjsCdv3bPEpP1R .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-0WbjsCdv3bPEpP1R .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-0WbjsCdv3bPEpP1R .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-0WbjsCdv3bPEpP1R .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-0WbjsCdv3bPEpP1R .marker{fill:#333333;stroke:#333333;}#mermaid-svg-0WbjsCdv3bPEpP1R .marker.cross{stroke:#333333;}#mermaid-svg-0WbjsCdv3bPEpP1R svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-0WbjsCdv3bPEpP1R .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-0WbjsCdv3bPEpP1R .cluster-label text{fill:#333;}#mermaid-svg-0WbjsCdv3bPEpP1R .cluster-label span{color:#333;}#mermaid-svg-0WbjsCdv3bPEpP1R .label text,#mermaid-svg-0WbjsCdv3bPEpP1R span{fill:#333;color:#333;}#mermaid-svg-0WbjsCdv3bPEpP1R .node rect,#mermaid-svg-0WbjsCdv3bPEpP1R .node circle,#mermaid-svg-0WbjsCdv3bPEpP1R .node ellipse,#mermaid-svg-0WbjsCdv3bPEpP1R .node polygon,#mermaid-svg-0WbjsCdv3bPEpP1R .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-0WbjsCdv3bPEpP1R .node .label{text-align:center;}#mermaid-svg-0WbjsCdv3bPEpP1R .node.clickable{cursor:pointer;}#mermaid-svg-0WbjsCdv3bPEpP1R .arrowheadPath{fill:#333333;}#mermaid-svg-0WbjsCdv3bPEpP1R .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-0WbjsCdv3bPEpP1R .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-0WbjsCdv3bPEpP1R .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-0WbjsCdv3bPEpP1R .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-0WbjsCdv3bPEpP1R .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-0WbjsCdv3bPEpP1R .cluster text{fill:#333;}#mermaid-svg-0WbjsCdv3bPEpP1R .cluster span{color:#333;}#mermaid-svg-0WbjsCdv3bPEpP1R div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-0WbjsCdv3bPEpP1R :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 是 是 否 否 开始 初始化res1, basea, expn exp 0? exp末位1? res res * base mod m 跳过 base base² mod m exp exp 1 输出 res 算法演示7¹³ mod 11 计算过程
步骤指数 (二进制)当前位操作resultbase初始化1101--17111011result (1*7) mod 1177²49 mod 11521100不操作75²25 mod 1133111result (7*3) mod 1121 mod 1110103²9 mod 119411result (10*9) mod 1190 mod 1122-
最终结果2
Java实现
public class FastModularExponentiation {/*** 快速取模指数算法* param base 底数* param exponent 指数* param modulus 模数* return (base^exponent) mod modulus*/public static long fastModExp(long base, long exponent, long modulus) {if (modulus 1) return 0; // 任何数模1都为0long result 1;base base % modulus; // 确保base小于模数while (exponent 0) {// 检查指数最低位是否为1if ((exponent 1) 1) {result (result * base) % modulus;}// 指数右移一位相当于除以2exponent exponent 1;// 底数平方后取模base (base * base) % modulus;}return result;}public static void main(String[] args) {// 示例1计算 7^13 mod 11long result1 fastModExp(7, 13, 11);System.out.println(7^13 mod 11 result1); // 输出 2// 示例2计算 1234567^1000000 mod 10007long result2 fastModExp(1234567, 1000000, 10007);System.out.println(1234567^1000000 mod 10007 result2); // 输出 8521// 示例3RSA解密演示long cipher 1394; // 密文long d 77; // 私钥指数long n 3233; // RSA模数long plain fastModExp(cipher, d, n);System.out.println(RSA解密: cipher ^ d mod n plain);}
}密码学应用场景
1. RSA加密/解密
加密ciphertext plaintextᵉ mod n解密plaintext ciphertextᵈ mod n
2. Diffie-Hellman密钥交换
双方计算sharedSecret (gᵃᵇ) mod p
3. 数字签名
签名生成signature messageᵈ mod n签名验证message signatureᵉ mod n
算法优化技巧 蒙哥马利约简消除模运算中的除法 long montgomeryReduce(long x, long modulus) {long q x * modInverse(modulus, 1L 32);return (x - q * modulus) 32;
}滑动窗口法预处理指数位组合 // 预处理4位组合
long[] precomputed new long[16];
precomputed[0] 1;
for(int i1; i16; i) {precomputed[i] (precomputed[i-1] * base) % modulus;
}并行计算将指数拆分为多段 // 拆分指数exponent e1 e2
long part1 fastModExp(base, e1, modulus);
long part2 fastModExp(base, e2, modulus);
long result (part1 * part2) % modulus;实际应用RSA密钥生成
public class RSAKeyGenerator {// 快速取模指数算法实现// ...public static void main(String[] args) {// 生成大素数实际应用需使用SecureRandomlong p 61; // 第一个质数long q 53; // 第二个质数long n p * q; // 模数long phi (p-1) * (q-1); // 欧拉函数// 选择公钥指数通常为65537long e 17;// 计算私钥指数模反元素long d modInverse(e, phi);// 测试加密/解密long message 123;long cipher fastModExp(message, e, n);long decrypted fastModExp(cipher, d, n);System.out.println(原始消息: message);System.out.println(加密结果: cipher);System.out.println(解密结果: decrypted);}// 扩展欧几里得算法求模反元素public static long modInverse(long a, long m) {long m0 m, y 0, x 1;while (a 1) {long q a / m;long t m;m a % m;a t;t y;y x - q * y;x t;}return x 0 ? x m0 : x;}
}性能基准测试单位纳秒
指数位数普通幂运算快速取模指数加速比10位15,20085017.9×20位2,450,0001,2002042×50位超时2,80010000×100位超时5,60010000× 关键洞察当指数达到100位时约10³⁰普通算法需要执行10³⁰次乘法而快速算法仅需约330步log₂(10³⁰)≈100
