2

有没有给出“乘法链”的实用算法

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

4

3 回答 3

5

您要求以下模方程的非平凡解：

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 次方的欧拉 phi 函数是 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
于 2008-11-01T05:26:05.887 回答
2

以下是在常数为奇数的情况下计算 start 和 multiplier 值的方法：

  1. 找到这样的奇数 m（m = 乘数），即 m 模 2^D 的阶数至少是计数，这意味着最小的 n 使得 m^n = 1 (mod 2^D) 至少是计数。除了随机猜测之外，我不知道找到这样的 m 的任何其他方法，但是从一些实验来看，1 到 2^D 之间的奇数的一半似乎具有最大的 2^(D-2) 阶。（我最多尝试了 D 12。）

  2. 计算 x 使得 x * m^count = 1 (mod 2^D) 并设置 start = x * constant (mod 2^D)。

这样的 x 可以通过“扩展欧几里得算法”找到：给定 a 和 b 没有公约数，它给你 x 和 y 使得 a * x + b * y = 1。这里 a=m^count mod 2^D 和b = 2^D。

编辑：如果常数恰好是偶数，您可以将其除以 2 的幂，例如 2^k，使其变为奇数，然后对输入 {constant/2^k, count, 2^(Dk)} 执行上述操作最后返回 {start*2^k,multiplier}。

于 2008-11-01T18:16:59.107 回答
1

为什么不能满足要求？

start = constant;
multiplier = 1;

更新：我现在看到循环数是输入参数之一。听起来这个问题是离散对数问题的一个特例，或者至少与离散对数问题有关。

于 2008-11-01T04:37:18.793 回答