IDEA密码使用乘法2^16 + 1
模。是否有一种算法可以执行此操作而无需一般的模运算符(仅对2^16
模(截断)求模)?在IDEA的上下文中,零被解释为2^16
(这意味着零不是我们乘法的参数,并且它不可能是结果,因此我们可以保存一位并将值2^16
存储为位模式0000000000000000
)。我想知道如何在不使用标准模运算符的情况下有效地实现它(或根本不可能实现)。
最佳答案
您可以利用以下事实:(N-1)%N == -1。
因此,(65536 * a)%65537 == -a%65537。
另外,当将0解释为65536时,-a%65537 == -a + 1(mod 65536)
uint16_t fastmod65537(uint16_t a, uint16_t b)
{
uint32_t c;
uint16_t hi, lo;
if (a == 0)
return -b + 1;
if (b == 0)
return -a + 1;
c = (uint32_t)a * (uint32_t)b;
hi = c >> 16;
lo = c;
if (lo > hi)
return lo-hi;
return lo-hi+1;
}
唯一的问题是
hi == lo
,结果将为0。幸运的是,一个测试套件确认,它实际上不可能是...int main()
{
uint64_t a, b;
for (a = 1; a <= 65536; a++)
for (b = 1; b <= 65536; b++)
{
uint64_t c = a*b;
uint32_t d = (c % 65537) & 65535;
uint32_t e = m(a & 65535, b & 65535);
if (d != e)
printf("a * b % 65537 != m(%d, %d) real=%d m()=%d\n",
(uint32_t)a, (uint32_t)b, d, e);
}
}
输出:无