2

几件事：

  • 我是一名大学生
  • 这不是作业问题（我很好奇 bignum 库是如何工作的）
  • 这里所有的代码片段都可以用 gcc -lgmp 编译

这是我的实现，它不断返回错误的答案。我尝试过使用 gdb 并使用 GMP 检查单个操作并标记代码中哪些操作肯定失败，但我还没有设法具体找到问题所在。

除此之外，我无法确定问题出在哪里。

uint64_t *multiply(u256 c, u256 a, uint64_t alen, u256 b, uint64_t blen) {
    if (alen == 1 || blen == 1) {
        u2_set(c, 0);
        c[0] = a[0] * b[0];
        c[1] = c[0] >> 32LU;
        c[0] &= MASK;
        return c;
    } else {
        uint64_t al, bl;
        uint64_t M = min(alen, blen);
        al = ceil(alen, 2);
        bl = ceil(blen, 2);
        uint64_t m = M / 2;
        u256 low1, low2, high1, high2, z0, z1, z2;
        u2_set(low1, 0);
        u2_set(low2, 0);
        u2_set(high1, 0);
        u2_set(high2, 0);
        memcpy(low1, a, sizeof(uint64_t) * al);
        memcpy(low2, b, sizeof(uint64_t) * bl);
        memcpy(high1, &(a[al]), sizeof(uint64_t) * (alen - al));
        memcpy(high2, &(b[bl]), sizeof(uint64_t) * (blen - bl));

        /* Starts ok, goes bad immediately. Mostly ok. */
        multiply(z0, low1, al, low2, bl);

        u2_add(low1, low1, high1); /* CHECKED */
        u2_add(low2, low2, high2); /* CHECKED */

        multiply(z1, low1, al, low2, bl); /* Starts ok, goes bad immediately. */

        /* Bad but starts & usually is ok */
        multiply(z2, high1, (alen - al), high2, (blen - bl));

        /* ALL GOOD */
        u256 o;
        u2_sub(z1, z1, z2);
        u2_sub(z1, z1, z0);
        u2_shl(z1, z1, m);
        u2_shl(z2, z2, m * 2);
        u2_add(o, z2, u2_add(z1, z1, z0));

        u2_copy(c, o);
        return c;
    }
}

老实说，最糟糕的部分是没有中间值的测试向量。除了维基百科页面示例中的那些（我似乎通过了），我找不到任何东西。

u256是一个 8 的数组uint64_t。我只使用这些整数的低 32 位来进行掩蔽并更容易携带。这个想法是做 Karatsuba 乘法基数 2 32。

其余的代码可以在这里找到。

任何帮助，将不胜感激。

编辑：

错误示例：

a = 89637787616193205010487395076171907549998432494691382753495063501471509582488
b = 62570744880332518477645686292054860709644349224438728618405612469614908709348

乘以 2 应该返回

16439926136035242788212517705012640494860769275971090459163708006828967815008

相反，它返回

38696864898835518778416

可以通过编译此代码来运行该特定测试：here

使用 gcc 和 -lgmp

ceil被定义为：

#define ceil(a, b) (((a) + (b) - 1LU) / (b))

使用这个测试代码，它可以更深入地检查一些东西，我相信我将问题缩小了一些。

它发生在 的m=4乘积上z0 = low1 * low2。相乘的两个值是100000000000和100000000000，预期的结果是10000000000000000000000最终结果是1478053504202008644。运行上面的测试代码将重现这一点。我认为这意味着我的 karatsuba 实现被简单地破坏了，因为组件没有抛出任何错误，而且它在 m=2 乘法上特别失败。我正在检查 m=1 乘法，它们看起来很好。

4

0 回答 0