趣题：不用乘法实现 (1 + x + x^2 + x^4) mod 2233393

    下面是 IBM Ponder This 2013 年 5 月的谜题：写一个程序来计算 f(x) = 1 + x + x2 + x4 (mod 2233393) 。你的程序只能使用以下三种语句，其中等号表示赋值，变量 2 和变量 3 的位置都可以用常量来代替：

(1) 变量 1 = 变量 2 + 变量 3
(2) 变量 1 = 变量 2 * 变量 3
(3) 变量 1 = 变量 2 mod 变量 3

    很容易想到，一种最基本的解法如下：

a = x * x
b = a * a
c = a + b
d = c + x
e = d + 1
f = e mod 2233393

    这道谜题则要求你找到另外一种解法，它必须同时满足下面两个额外的要求：

      (1) 最多使用两次变量与变量之间的乘法运算（但允许多次变量与常量之间的乘法运算）
      (2) 最后两次运算分别是一次变量与变量之间的乘法运算和一次取余运算


 
 
 
 
 
 
 
 
 
 
 

    两次变量与变量之间的乘法运算正好能够产生四次多项式，而且其中一次乘法是在最后的取余运算之前进行的，这让我们想到了这样的思路：找出常数 a 、 b 、 c 、 d ，使得 (x2 + a · x + b)(x2 + c · x + d) 展开之后，从高到低各项系数除以 2233393 的余数正好是 1, 0, 1, 1, 1 。这样的话，我们就可以先用一次双变量的乘法产生 x2 ，然后构造出 x2 + a · x + b 和 x2 + c · x + d ，在倒数第二步把它们乘在一起，在最后一步取整个结果除以 2233393 的余数，这就实现了我们的目标。

    但是，即使用计算机去搜索 a 、 b 、 c 、 d ，计算量也太大了。怎么办呢？一个非常巧妙的办法是，注意到 2233393 = 19 × 41 × 47 × 61 ，因此我们可以分别找出从 a1 到 d4 共 16 个常数，使得它们满足：

(x2 + a1 · x + b1)(x2 + c1 · x + d1) = x4 + x2 + x + 1 (mod 19)
(x2 + a2 · x + b2)(x2 + c2 · x + d2) = x4 + x2 + x + 1 (mod 41)
(x2 + a3 · x + b3)(x2 + c3 · x + d3) = x4 + x2 + x + 1 (mod 47)
(x2 + a4 · x + b4)(x2 + c4 · x + d4) = x4 + x2 + x + 1 (mod 61)

    然后利用中国剩余定理便能得到 a 、 b 、 c 、 d 满足：

(x2 + a · x + b)(x2 + c · x + d) = x4 + x2 + x + 1 (mod 2233393)

    搜索前面 16 个常数的计算量已经很小了，即使是最后一个式子，我们也只需要枚举四个 0 到 60 之间的数的组合。结果如下：

(x2 + 7 · x + 10)(x2 + 12 · x + 2) = x4 + x2 + x + 1 (mod 19)
(x2 + 7 · x + 22)(x2 + 34 · x + 28) = x4 + x2 + x + 1 (mod 41)
(x2 + 4 · x + 26)(x2 + 43 · x + 38) = x4 + x2 + x + 1 (mod 47)
(x2 + 19 · x + 6)(x2 + 42 · x + 51) = x4 + x2 + x + 1 (mod 61)

    注意到 19、 41、 47 、 61 都是质数，因而它们也就是两两互质的。利用中国剩余定理，我们可以找出从 0 到 19 × 41 × 47 × 61 – 1 之间的一个数 M ，使得 M 除以 19 、 41 、 47 和 61 的余数分别是 7 、 7 、 4 、 19 。这个数便是 1594620 。类似地， (10, 22, 26, 6) 对应于 1831287 ， (12, 34, 43, 42) 对应于 638773 ， (2, 28, 38, 51) 对应于 1613501 。于是我们就有了

(x2 + 1594620 x + 1831287)(x2 + 638773 x + 1613501) = x4 + x2 + x + 1 (mod 2233393)

    这正是 IBM Ponder This 给出的标准答案：

y = x * x
a = 638773 * x
a = y + a
a = 1613501 + a
b = 1594620 * x
b = y + b
b = b + 1831287
z = a * b
z = z mod 2233393

 
    受此启发， Using your Head is Permitted 2013 年 6 月提出了一个加强版的问题，瞬间完爆 IBM Ponder This 的原题。你仍然只能使用那三种语句，仍然是要实现 f(x) = 1 + x + x2 + x4 (mod 2233393) ，但这一次的限制条件更加苛刻：

      (1) 完全不能使用任何乘法运算
      (2) 总共不能超过 10 次运算

    看上去，不用乘法就能算出一个四次多项式的值，这似乎根本就不可能。不过，我们也并不需要算出这个四次多项式的值，只需要算出这个四次多项式模 2233393 之后的值。我们或许可以在程序中使用一些非常大的常数，让它与 x 发生某种线性关系后，模 2233393 的余数正好与 1 + x + x2 + x4 相同。

 
 
 
 
 
 
 
 
 
 
 

    事实上，我们只需要 4 次运算就足够了，而且方法出人意料地简单。令 A 为一个充分大的常数，比如 1040 。算出 B = 1 – A + A2 + A4 ，它将成为程序中的另一个常数。依次执行下面四条语句，最后就会得到 (1 + x + x2 + x4) mod 2233393 。

a = x mod 2233393
b = a + A
c = B mod b
d = c mod 2233393

    为什么？首先，我们要计算的是 (1 + x + x2 + x4) mod 2233393 ，因此事先取 x 模 2233393 的余数，这不会对结果产生影响。那么，令 a = x mod 2233393 后，我们只需要算出 (1 + a + a2 + a4) mod 2233393 即可。

    而在第三步结束之后， c 的值正是 1 + a + a2 + a4 ！为了解释这件事，我们只需要注意到以下两点：首先，由于 b = a + A ，因此 – a 和 A 模 b 的余数是相同的，而 c 是 1 – A + A2 + A4 模 b 的余数，因而 c 也就等于 1 – (- a) + (- a)2 + (- a)4 模 b 的余数，即 1 + a + a2 + a4 模 b 的余数；其次， a 是一个不超过 2233393 的正整数，因而 1 + a + a2 + a4 也就是一个大小有限的正整数。我们选取的常数 A 非常非常大，从而保证了 b = a + A 也非常非常大，并且远远超过了 1 + a + a2 + a4 可能的最大值。所以说， 1 + a + a2 + a4 模 b 的余数也就是 1 + a + a2 + a4 本身。这就说明了， c 确实等于 1 + a + a2 + a4 。

    既然 c 已经等于 1 + a + a2 + a4 了，最后再来一个 d = c mod 2233393 ，问题就解决了。

    这个例子告诉了我们，引入大数运算会让计算能力出现意想不到的突破。事实上，假设计算机能瞬间完成任意大数之间的运算，我们就能做到 O(n) 时间的排序，甚至 O(1) 时间的排序。

26 条评论

发表评论




Enter Captcha Here :