乘法链导致常数模2的幂

Question

是否有一个实用的算法,给出"乘法链"

为了澄清,目标是产生任意和精确长度的
乘法变化长度为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的计数

Answer 1

您要求对以下模块化方程式进行重要解决方案:

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