快速乘法模 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);
        }
    }

输出：none

Answer 2

首先，a或b为零的情况。在那种情况下，它被解释为具有值 2^16，因此初等模算术告诉我们：

result = -a - b + 1;

，因为（在IDEA的上下文中）2^16的乘法逆元仍然是2^16，其最低16位全为零

一般情况比看起来容易得多，现在我们处理了“0”特殊情况（2^16+1 是 0x10001）：

/* This operation can overflow: */
unsigned result = (product & 0xFFFF) - (product >> 16);
/* ..so account for cases of overflow: */
result -= result >> 16;

放在一起：

/* All types must be sufficiently wide unsigned, e.g. uint32_t: */
unsigned long long product = a * b;
if (product == 0) {
    return -a - b + 1;
} else {
    result = (product & 0xFFFF) - (product >> 16);
    result -= result >> 16;
    return result & 0xFFFF;
}

快速乘法模 2^16 + 1

Fast multiplication modulo 2^16 + 1

c

cryptography

algebra

modulus