Print

模重复平方解题过程

问:求5^16(mod113),用模重复平方或平方乘方法,求大神给出解答过程
  1. 答:5^16(mod113)=5*125^5(mod113)≡5*12^5(mod113)=60*144^2(mod113)
    ≡60*31^2(mod113)=60*961(mod113)=60*57(mod113)=3420(mod113)
    ≡30(mod113)
问:C语言 一个数学程序求解释
  1. 答:x[32]也是存放结果的。
    模重复平方法求的是a^m%n
    当m=13,即二进制的 1101 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0时,最终结果
    ans =a^m % n
    = a^(1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0) %n
    = [a^(1 * 2^3)] * [a^(1 * 2^2)] * [(a ^ (0 * 2^1)] * [a ^ (1 * 2^0)] % n
    也就是说,从低到高,在第 i 位的时候,将a^(bin[i] * 2^i) %n 乘到结果中即可。这里可以稍微变换一下:仅当bin[i] == 1的时候,将a^(2^i) % n乘进去即可。所以这里可以用一个辅助的变量 b 来保存 a^(2^i) % n,在每次迭代的过程中 b = b^2 % n 。
  2. 答:将m转换为二进制输出 调用函数to_binary()实现
    第二个计算a的n次方
问:模重复平方法怎么计算的?那个b1≡b^2(modm)怎么算的?
  1. 答:MOD用法及意义是:a≡b(modc)的意思是a和b除以c后余数相同读作a与b同余,mod为c例如:amodb=c说明:a除以b余数为c。再比如说2的100次方的个位是什么,可写成2^100≡6。(mod10)特别是进制,用“mod”来代表几进制。modn读作“模n”

本文来源: https://www.lunwen66.cn/article/aa38a9d87637d248b3572db9.html