是否有一个实用的算法,给出"乘法链"
为了澄清,目标是产生任意和精确长度的
乘法变化长度为1的乘法链是微不足道的.
"乘法链"将被定义为代码中使用的2个数字{start}和{multiplier}:
Given a pointer to array of size [{count}] // count is a parameter a = start; do { a = a * multiplier; // Really: a = (a * multiplier) MOD (power of 2 *(pointer++) = a; } while (a != {constant} ) // Postcondition: all {count} entries are filled.
我想找到一个带有三个参数的例程
1. 2的幂
2.停止{constant}
3. {count} - 循环迭代的次数
例程将返回{start}和{multiplier}.
理想情况下,{Constant}值为0应该有效.
琐碎的例子:
power of 2 = 256 stopping constant = 7 number of times for the loop = 1 returns {7,1}
非常重要的例子:
power of 2 = 256 stopping constant = 1 number of times for the loop = 49 returns {25, 19}
给定功率2的最大{count}可能相当小.
例如,2 ^ 4(16)似乎限于4的计数
您要求对以下模块化方程式进行重要解决方案:
s * m^N = C (mod 2^D)
哪里
s是起始常数
m是乘数
N是迭代次数(由问题给出)
C是最终常数(由问题给出)
D是2的幂的指数(由问题给出)
看看数论中的欧拉定理.
对于任意奇数 m(具有2 ^ D的素数),你有
m^phi(2^D) = 1 (mod 2^D)
从而
C * m^phi(2^D) = C (mod 2^D)
最后
C * m^(phi(2^D)-N) * m^N = C (mod 2^D)
采取
s = C * m^(phi(2^D)-N)
你完成了 该欧拉披功能的2次方是一半的2,即功率:
phi(2^D) = 2^(D-1)
例子.让
N = 5
C = 3
2 ^ D = 16
phi(16)= 8
任意选择m = 7(奇数),然后计算
3 * 7^(8-5) = 1029 s = 1029 mod 16 = 5
现在
s * m^N = 5 * 7^5 = 84035 84035 mod 16 = 3 == C