如果您有其他因素且产品有溢出,您如何计算因子？

Question

a * x = b

我有一个看似相当复杂的乘法/ imul问题:如果我有一个并且我有b,如果它们都是32位双字(例如0-1 = FFFFFFFF,FFFFFFFF + 1 = 0),我怎么能计算x？例如:

0xcb9102df * x = 0x4d243a5d

在这种情况下,x是0x1908c643.我发现了一个类似的问题,但前提是不同的,我希望有一个比给出的更简单的解决方案.

Answer 1

数字具有模乘逆模 2 的幂，当且仅当它们是奇数。其他所有内容都是位移奇数（偶数零，可能是任何内容，所有位都移出）。所以有几种情况：

给定a * x = b

• tzcnt(a) > tzcnt(b)没有解决方案
• tzcnt(a) <= tzcnt(b)可解，有 2 个^tzcnt(a)解

第二种情况有一个特殊情况，有 1 个解，对于 odd a，即x = inverse(a) * b

更一般地说，x = inverse(a >> tzcnt(a)) * (b >> tzcnt(a))是一个解决方案，因为你写a为(a >> tzcnt(a)) * (1 << tzcnt(a))，所以我们用它的逆来取消左边的因子，我们将右边的因子作为结果的一部分（无论如何都不能取消），然后乘以剩余的值以获得b。显然，仍然只适用于第二种情况。如果您愿意，您可以通过填写最高位的所有可能性来枚举所有解决方案tzcnt(a)。

唯一剩下的就是求逆，您可能已经在其他答案中看到了它，无论它是什么，但为了完整起见，您可以按如下方式计算它：（未经测试）

; input x
dword y = (x * x) + x - 1;
dword t = y * x;
y *= 2 - t;
t = y * x;
y *= 2 - t;
t = y * x;
y *= 2 - t;
; result y