c - bignum 库和素性测试算法的方便基础是什么？

Question

我要编写有关 RSA 的原始论文中提出的 Solovay-Strassen 素性检验的程序。

此外，我需要编写一个小型 bignum 库，因此在搜索 bignum 的方便表示时，我遇到了这个 specification :

struct {
  int sign;
  int size;
  int *tab;
} bignum;

我还将使用 Karatsuba 方法编写乘法例程。

所以，对于我的问题:

在 bignum 结构中存储整数数据使用什么基比较方便？

注意:我不允许使用第三方或内置的 bignum 实现，例如 GMP。

谢谢。

Answer 1

2 的幂。

对于一个简单的实现，可能是你机器上一个字的一半大小，这样你就可以将两个数字相乘而不会溢出。所以 65536 或 4294967296。或者可能是最大整数类型大小的一半，出于同样的原因，但整体性能可能更好。

但我从未真正实现过这样的库:如果您使用的是最著名的算法，那么您就不会进行学校风格的长乘法运算。 Karatsuba 乘法(以及您使用的任何其他巧妙的技巧)可能会受益于以两倍于数字大小的整数来完成，我真的不知道性能如何。如果是这样，那么您最好使用 256 和 32 位算法，或者 65536 和 64 位算法。

在任何情况下，如果您的表示是二进制的，那么您可以为每个操作挑选和选择更大的二次幂的基数。例如，您可以将数据视为以 2^16 为基数进行乘法，但以 2^32 为基数进行加法。只要您注意字节顺序，一切都是一样的。我可能会从基数 2^16 开始(因为这迫使我一开始就获得字节顺序的正确性，而 2^8 则不会)，然后看看我如何进行 - 随着每个操作都得到优化，部分优化是确定最佳碱基。

使用不是字节倍数的大小是可能的，但是你必须对所有内容使用相同的基数，因为根据基数，存储中的特定位置有未使用的位。