IDEA密码使用乘法模2 ^ 16 1.是否有算法在没有通用模运算符的情况下执行此操作(仅模2 ^ 16(截断))？在IDEA的上下文中,零被解释为2 ^ 16(这意味着零不是我们乘法的参数,它不能是结果,因此我们可以保存一位并将值存储为2 ^ 16作为位模式0000000000000000).我想知道如何在不使用标准模运算符的情况下有效地实现它(或者是否有可能).
解决方法
您可以利用(N-1)％N == -1这一事实.
因此,(65536 * a)％65537 == -a％65537.
此外,-a％65537 == -a 1(mod 65536),当0被解释为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);
- }
- }
输出：无
