2

我将编写关于 RSA 的原始论文中提出的 Solovay-Strassen 素性测试。

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

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

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

所以，对于我的问题：

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

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

谢谢你。

4

4 回答 4

3

2 的幂。

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

但我从来没有真正实现过这样的库：如果你使用的是最知名的算法，那么你就不会做学校风格的长乘法。Karatsuba 乘法（以及您使用的任何其他巧妙技巧）可能会受益于以数字大小两倍以上的整数完成，我真的不知道性能如何。如果是这样，那么您最好使用 256 和 32 位算术，或 65536 和 64 位算术。

在任何情况下，如果您的表示是二进制的，那么您可以选择更大的二次方基数，以方便每个操作。例如，您可以将数据视为基数 2^16 进行乘法运算，但将数据视为基数 2^32 进行加法运算。只要你小心字节序，一切都是一样的。我可能会从基数 2^16 开始（因为这迫使我从一开始就获得正确的字节序，而 2^8 则不会），然后看看我是如何开始的——因为每个操作都经过优化，部分优化是确定最佳基础。

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

于 2010-04-18T22:51:44.467 回答
2

您将大量执行以下操作：

a b+c d ...;

要么选择最大字长的 1/4，要么选择最大字长的 1/2，减去一两位。64 位系统为 2^16 或 2^30，32 位系统为 2^8 或 2^14。使用编译器支持的最大尺寸，而不是硬件。

如果您在 64 位系统上选择 2^31，这意味着您可以添加 4 个产品而不会溢出。如果您选择 2^30，那么您可以添加 16 个产品而不会溢出。您可以添加的越多而不会溢出，您可以使用的临时块就越大。

如果您选择 1/4 字长，您仍将拥有本机类型，因此更容易将结果存储回来。您也几乎可以忽略溢出。这基本上将使编写代码更快，更不容易出错，并且内存效率略高。我会推荐这个，除非你喜欢大量的位操作以及你的数学。

选择更大的基数会使大 O 数字看起来更好。在实践中，虽然拥有更大的基数可能会更快，但它不会是您可能希望的 4 倍减速带。

于 2010-04-18T23:23:56.747 回答
1

您使用的基数应该是 2 的幂。因为看起来您要单独跟踪符号，所以您可以使用无符号整数来存储数字本身。您将需要一次将这些数字的 2 个部分/数字/单位相乘的能力，因此大小不得超过可用字长的一半。即在 x86 上，无符号整数是 32 位，因此您希望您的数字不超过 16 位。您也可以将“long long”用于无符号整数乘积的中间结果。然后你正在为你的基地寻找 2^32。最后要考虑的一件事是您可能想要添加乘积之和，除非您使用更少的位，否则它将溢出。

如果性能不是主要问题，我会使用 base 256 并收工。您可能希望使用 typedef 和定义的常量，以便以后可以轻松更改这些参数。

于 2010-04-18T22:52:34.963 回答
1

tab 数组中的整数应该是无符号的。它们应该是您可以乘以并仍然代表产品的最大可能大小（基础）。例如，如果您的编译器/处理器支持 64 位 unsigned long long，您可以将 uint32_t 用于“数字”数组。如果您的编译器/处理器只能本地生成 32 位产品，则应使用 uint16_t。

当你对两个数组求和时，你需要处理溢出；在组装中这很容易。在 C 语言中，您可以选择少用一位（31 或 15）来使溢出检测更容易。

还要考虑字节序，以及它和算法对缓存行为的影响。

于 2010-04-18T22:54:57.683 回答