快速乘法模2 ^ 16 + 1 [英] Fast multiplication modulo 2^16 + 1

问题描述

的想法密码使用乘法模 2 ^ 16 + 1 。是否有不一般的模运算符执行此操作的算法（仅模 2 ^ 16 （截断））？在IDEA的背景下，零是PTED为 2 ^ 16 （这意味着零不是我们乘的一个参数，它不能是这个结果间$ P $，所以我们可以节省一位，存储值 2 ^ 16 的位模式 0000000000000000 ）。我想知道如何不使用标准的模运算实现它有效（或是否有可能在所有）。

The IDEA cipher uses multiplication modulo 2^16 + 1. Is there an algorithm to perform this operation without general modulo operator (only modulo 2^16 (truncation))? In the context of IDEA, zero is interpreted as 2^16 (it means zero isn't an argument of our multiplication and it cannot be the result, so we can save one bit and store value 2^16 as bit pattern 0000000000000000). I am wondering how to implement it efficiently (or whether it is possible at all) without using the standard modulo operator.

推荐答案

您可以利用这一事实，即（N-1）％N == -1。

You can utilize the fact, that (N-1) % N == -1.

因此​​，（65536 * A）％65537 == -a％65537.结果
此外，-a％65537 == -a + 1（MOD 65536），当0 PTED为65536间$ P $

Thus, (65536 * a) % 65537 == -a % 65537.
Also, -a % 65537 == -a + 1 (mod 65536), when 0 is interpreted as 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;
}

这里唯一的问题是，如果喜==罗，结果将是0。幸运的是，一个测试套件证实，它实际上不可能......

The only problem here is if hi == lo, the result would be 0. Luckily a test suite confirms, that it actually can't be...

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);
        }
    }

输出：无​​

这篇关于快速乘法模2 ^ 16 + 1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！