快速乘法模2 ^ 16 + 1

Question

IDEA密码使用乘法模数2^16 + 1.是否有算法在没有通用模运算符的情况下执行此操作(仅模数2^16(截断))？在IDEA的上下文中,零被解释为2^16(它表示零不是我们乘法的参数,它不能是结果,因此我们可以保存一位并将值存储2^16为位模式0000000000000000).我想知道如何在不使用标准模运算符的情况下有效地实现它(或者是否有可能).

Answer 1

您可以利用(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);
        }
    }

输出:无