什么是方便下榻之所BIGNUM文献保障;素性测试的算法？ [英] What is a convenient base for a bignum library & primality testing algorithm?

问题描述

我来编程psented在RSA的原纸上的Solovay-Strassen的素性测试$ P $。

I am to program the Solovay-Strassen primality test presented in the original paper on RSA.

此外我需要写一个小BIGNUM库，因此寻找一种方便的再presentation为BIGNUM，当我碰到这个的规范：

Additionally I will need to write a small bignum library, and so when searching for a convenient representation for bignum I came across this specification:

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

我也会使用Karatsuba的方法写一个乘法程序。

I will also be writing a multiplication routine using the Karatsuba method.

所以，我的问题：

什么基础将可以方便的存储整型数据的BIGNUM结构？

What base would be convenient to store integer data in the bignum struct?

注：我不允许使​​用第三方或内置的实现BIGNUM如GMP

Note: I am not allowed to use third party or built-in implementations for bignum such as GMP.

感谢你。

推荐答案

您使用应该是2的幂，因为它看起来就像你要单独跟踪标志，你可以使用无符号整数存储基地数字本身。你将需要乘这些数字的2片/位/单元在时间的能力，因此，大小不得超过半数你有可用的字大小。即在x86上一个unsigned int是32位，所以你希望你的位数不超过16位。你也可以使用长长为无符号整数产品的中间结果。然后你看2 ^ 32的基地。最后要考虑的是，你可能要添加的产品款项，这将溢出，除非你用更少的位。

The base you use should be a power of 2. Since it looks like you're going to keep track of sign separately, you can use unsigned ints for storing the numbers themselves. You're going to need the ability to multiply 2 pieces/digits/units of these numbers at a time, so the size must be no more than half the word size you've got available. i.e. on x86 an unsigned int is 32 bits, so you'd want your digits to be not more than 16 bits. You may also use "long long" for the intermediate results of products of unsigned ints. Then you're looking at 2^32 for your base. One last thing to consider is that you may want to add sums of products, which will overflow unless you use fewer bits.

如果性能不是大问题，我只是用底座256和收工。您可能需要使用typedef和定义的常量，所以你以后可以很容易地修改这些参数。

If performance is not a major concern, I'd just use base 256 and call it a day. You may want to use typedefs and defined constants so you can later change these parameters easily.

这篇关于什么是方便下榻之所BIGNUM文献保障;素性测试的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！