algorithm - 产生常数模 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 的指数(由问题给出)

看看Euler's theorem在数论中。

对于任意的奇数 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)

你就完成了。 Euler's phi function 2 的幂是 2 的幂的一半，即:

phi(2^D) = 2^(D-1)

示例。让

• N = 5
• C = 3
• 2^D = 16
• φ(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