a * x = b
我有一个看似相当复杂的乘法/imul 问题:如果我有 a 和我有 b,如果它们都是 32 位双字(例如 0-1 = FFFFFFFF、FFFFFFFF+1 = 0),我如何计算 x?例如:
0xcb9102df * x = 0x4d243a5d
在这种情况下,x 是 0x1908c643。我发现了一个类似的问题,但前提不同,我希望有一个比给出的更简单的解决方案。
数字具有模乘逆模,只要它们是奇数,恰好是 2 的幂。其他一切都是位移奇数(即使是零,可能是任何东西,所有位都移出)。所以有几种情况:
给定a * x = b
tzcnt(a) > tzcnt(b)
没有解决方案tzcnt(a) <= tzcnt(b)
可解,有 2 个tzcnt(a)解第二种情况有一个特殊情况,有 1 个解,对于奇数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