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

Question

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

此外，我还需要编写一个小的bignum库，所以当搜索bignum的方便表示时，我偶然发现了这个specification

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

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

所以，对于我的问题：

在bignum结构中存储整数数据的基数是什么？

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

谢谢。

Answer 1

你使用的基数应该是2的幂。因为看起来你要单独跟踪符号，你可以使用无符号整数来存储数字本身。您将需要一次将这些数字的2个片段/数字/单位相乘的能力，因此大小不能超过现有字长的一半。也就是说，在x86上，无符号整数是32位的，所以你希望你的数字不超过16位。您也可以使用"long long“表示无符号整数乘积的中间结果。然后你看你的基数是2^32。最后要考虑的一件事是，您可能想要添加乘积和，除非您使用较少的位，否则会溢出。

如果性能不是主要考虑因素，我会使用基数256，到此为止。您可能希望使用typedefs和定义的常量，以便以后可以轻松地更改这些参数。

Answer 2

2的幂。

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

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

在任何情况下，如果您的表示是二进制的，那么您可以选择更大的2次幂的基，以方便进行每一次操作。例如，您可以将数据视为以2^16为基数的乘法，以2^32为基数的加法。如果你小心的使用endian-ness，这一切都是一样的。我可能会从基数2^16开始(因为这迫使我一开始就必须正确地使用endian-ness，而2^8不会)，然后看看我是如何进行的-因为每个操作都被优化了，优化的一部分就是确定最佳基数。

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

Answer 3

您将大量执行以下操作：

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的字长，你仍然会有一个原生类型，这样会更容易把结果存储出来。你也可以忽略掉overflow。这基本上将使编写代码更快，更不容易出错，并稍微提高内存效率。我建议你这样做，除非你喜欢在数学运算的同时进行大量的比特操作。

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