大整数库

用户 6918454

4.77/5 (18投票s)

2010年2月22日

CPOL

5分钟阅读

98711

5636

一个 .NET 2.0 和 Mono 库，用于 64 位优化处理非常大的整数，最多可达 10240 个二进制位数或大约（可安全使用）3000 个十进制位数

引言

BigInteger 是一个 .NET 2.0 和 Mono 库，用于处理非常大的整数，最多可达 10240 个二进制位数或大约（可安全使用）3000 个十进制位数。

背景

为了进行我学士学位论文中的模运算和加密操作，我需要一个自定义类型（类）来管理可变长度的整数。2007 年，我开始开发这个类型，它很好地满足了预期的目的。2010 年初，我开始对项目进行彻底重构，并形成了本文。

数制基数

第一个决定涉及要使用的数制基数（基数）。朴素的解决方案是使用十进制基数，因为它更熟悉。在计算机体系结构中，这个解决方案是不合适的，因为

它浪费了 32 位（或 64 位）整数处理器寄存器，只使用了可用位中的 3-4 位
同一个数字的二进制位数和十进制位数之间没有公式化的对应关系。人们只知道近似值 2¹⁰ = 10³。因此，将二进制数据转换为十进制格式将导致不一致的数据大小。

选择基数 2 几乎同样不合适，因为在这种情况下，虽然数据可以无缝地导入为数字，但处理器寄存器位的浪费是巨大的。正确的选择是选择一个多二进制基数，即 2 的幂的数制基数。

考虑到算术运算可能发生的溢出，很明显，如果不对计算结果进行调整，就无法期望使用完整的处理器寄存器来存储一个数字。上述原因以及需要使用字节单位（用于 I/O）可整除的数字大小的必要性。

在研究了最苛刻的算术运算算法（除法）的溢出情况，以及适应大尺寸整数的需要后，我决定采用 2¹⁶ = 65536 的基数，它可以用 2 个字节表示，并存储在 8 字节类型中，以便在原地管理非常大数字除法上的重度溢出。

在实现方面，类的字段如下所示

/// <summary>
/// The number's sign, where Positive also stands for the number zero.
/// </summary>
private enum Sign { Positive, Negative };

/// <summary>
/// 2^16 numeration base for internal computations, in order to benefit the most from the
/// 32 bit (or 64 bit) integer processor registers.
/// </summary>
private const long NumberBase = 65536;

/// <summary>
/// Maximum size for numbers is up to 10240 binary digits or 
/// approximately (safe to use) 3000 decimal digits.
/// The maximum size is, in fact, double the previously specified amount, 
/// in order to accommodate operations'
/// overflow.
/// </summary>
internal const int MaxSize = 2 * 640;

/// <summary>
/// Ratio for the conversion of a BigInteger's size to a binary digits size.
/// </summary>
private const int RatioToBinaryDigits = 16;

/// Integer constants
private static readonly BigInteger Zero = new BigInteger();
private static readonly BigInteger One = new BigInteger(1);
private static readonly BigInteger Two = new BigInteger(2);
private static readonly BigInteger Ten = new BigInteger(10);

/// <summary>
/// The array of digits of the number.
/// </summary>
private long[] digits;

/// <summary>
/// The actual number of digits of the number.
/// </summary>
private int size;

/// <summary>
/// The number sign.
/// </summary>
private Sign sign;

构造函数

实现了以下类型的 BigInteger 构造函数

默认构造函数 - 将数字设置为 0
接受一个 long（64 位）十进制数字作为参数的构造函数
接受一个可变长度字符串（包含十进制数字）的构造函数
使用字节数组参数的构造函数，用于将原始二进制数据转换为 BigInteger ，比例为 2 个原始字节对 1 个 BigInteger 数字

加法、减法和乘法

两个大整数的基本算术运算（加法、减法和乘法）可以很容易地实现为小学方法自然延伸。

加法辅助方法代码

/// <summary>
/// Adds two BigNumbers a and b, where a >= b, a, b non-negative.
/// </summary>
private static BigInteger Add(BigInteger a, BigInteger b)
{
     BigInteger res = new BigInteger(a);
     long trans = 0, temp;
     int i;

     for (i = 0; i < b.size; i++)
     {
          temp = res.digits[i] + b.digits[i] + trans;
          res.digits[i] = temp % NumberBase;
          trans = temp / NumberBase;
     }

     for (i = b.size; ((i < a.size) && (trans > 0)); i++)
     {
          temp = res.digits[i] + trans;
          res.digits[i] = temp % NumberBase;
          trans = temp / NumberBase;
     }

     if (trans > 0)
     {
          res.digits[res.size] = trans % NumberBase;
          res.size++;
          trans /= NumberBase;
     }

     return res;
}

减法辅助方法代码

/// <summary>
/// Subtracts the BigInteger b from the BigInteger a, where a >= b, a, b non-negative.
/// </summary>
private static BigInteger Subtract(BigInteger a, BigInteger b)
{
     BigInteger res = new BigInteger(a);
     int i;
     long temp, trans = 0;
     bool reducible = true;

     for (i = 0; i < b.size; i++)
     {
          temp = res.digits[i] - b.digits[i] - trans;
          if (temp < 0)
          {
               trans = 1;
               temp += NumberBase;
          }
          else trans = 0;
          res.digits[i] = temp;
     }

     for (i = b.size; ((i < a.size) && (trans > 0)); i++)
     {
          temp = res.digits[i] - trans;
          if (temp < 0)
          {
               trans = 1;
               temp += NumberBase;
          }
          else trans = 0;
          res.digits[i] = temp;
     }

     while ((res.size - 1 > 0) && (reducible == true))
     {
          if (res.digits[res.size - 1] == 0)
          res.size--;
          else reducible = false;
     }

     return res;
}

乘法辅助方法代码

/// <summary>
/// Multiplies two BigIntegers.
/// </summary>
private static BigInteger Multiply(BigInteger a, BigInteger b)
{
     int i, j;
     long temp, trans = 0;

     BigInteger res = new BigInteger();
     res.size = a.size + b.size - 1;
     for (i = 0; i < res.size + 1; i++)
          res.digits[i] = 0;

     for (i = 0; i < a.size; i++)
          if (a.digits[i] != 0)
               for (j = 0; j < b.size; j++)
                    if (b.digits[j] != 0)
                          res.digits[i + j] += a.digits[i] * b.digits[j];

     for (i = 0; i < res.size; i++)
     {
          temp = res.digits[i] + trans;
          res.digits[i] = temp % NumberBase;
          trans = temp / NumberBase;
     }

     if (trans > 0)
     {
          res.digits[res.size] = trans % NumberBase;
          res.size++;
          trans /= NumberBase;
     }

     return res;
}

除法

与加法、减法和乘法实现的简单性相反，除法算法不仅实现起来很困难，而且很难找到好的文档。在研究了 Knuth 的《Seminumerical Algorithms》第 2 卷的疏漏之处后，我偶然发现了 Per Brinch Hansen 的这篇精彩论文 [1]。

有 5 个除法辅助方法执行此操作，每个方法对应于上述论文中的一个方法。

已实现算法的类别

简单的算术运算不足以满足大整数操作库的需求。已实现以下算法、模运算函数和素数测试，这些对于现代公钥密码算法（如 RSA）都是必需的

通过快速幂运算实现幂运算

/// <summary>
/// Returns the power of a BigInteger base to a non-negative exponent by using the
/// fast exponentiation algorithm (right to left binary exponentiation).
/// </summary>
/// <param name="number">The BigInteger base</param>
/// <param name="exponent">The non-negative exponent</param>
/// <returns>The power of the BigInteger base to the non-negative exponent</returns>
/// <exception cref="BigIntegerException">
/// Cannot raise a BigInteger to a negative power exception</exception>
public static BigInteger Power(BigInteger number, int exponent)
{
    if (exponent < 0)
         throw new BigIntegerException
		("Cannot raise an BigInteger to a negative power.", null);

    if (a == Zero)
         return new BigInteger();

    BigInteger res = new BigInteger(1);
    if (exponent == 0)
         return res;

    BigInteger factor = new BigInteger(number);

    while (exponent > 0)
    {
         if (exponent % 2 == 1)
              res *= factor;

         exponent /= 2;

         if (exponent > 0)
              factor *= factor;
    }

    return res;
}

整数平方根（主要用于尝试将 RSA 模数分解为其素数，假设素数之间的差足够小）

/// <summary>
/// Integer square root of the given BigInteger using Newton's numeric method.
/// </summary>
/// <param name="n">The BigInteger whose integer square root is to be computed
/// </param>
/// <returns>The integer square root of the given BigInteger</returns>
/// <exception cref="BigIntegerException">Cannot compute the 
/// integer square root of a negative number exception</exception>
public static BigInteger IntegerSqrt(BigInteger n)
{
     if (n.sign == Sign.Negative)
          throw new BigIntegerException
	   ("Cannot compute the integer square root of a negative number.", null);

     BigInteger oldValue = new BigInteger(0);
     BigInteger newValue = new BigInteger(n);

     while (BigInteger.Abs(newValue - oldValue) >= One)
     {
          oldValue = newValue;
          newValue = (oldValue + (n / oldValue)) / Two;
     }

     return newValue;
}

欧几里得最大公约数算法和 GCD 的广义版本（对于 RSA 算法的密钥生成部分很有用）

/// <summary>
/// Euclidean algorithm for computing the 
/// greatest common divisor of two BigIntegers.
/// </summary>
/// <returns>The greatest common divisor of the two given BigIntegers</returns>
/// <exception cref="BigIntegerException">
/// Cannot compute the Gcd of negative BigIntegers exception</exception>
public static BigInteger Gcd(BigInteger a, BigInteger b)
{
     if ((a.sign == Sign.Negative) || (b.sign == Sign.Negative))
          throw new BigIntegerException
		("Cannot compute the Gcd of negative BigIntegers.", null);

     BigInteger r;

     while (b > Zero)
     {
          r = a % b;
          a = b;
          b = r;
     }

     return a;
}

/// <summary>
/// Extended Euclidian Gcd algorithm, returning the 
/// greatest common divisor of two BigIntegers,
/// while also providing u and v, where: a*u + b*v = gcd(a,b).
/// </summary>
/// <param name="u">Output BigInteger parameter, where a*u + b*v = gcd(a,b)
/// </param>
/// <param name="v">Output BigInteger parameter, where a*u + b*v = gcd(a,b)
/// </param>
/// <returns>The greatest common divisor of the two given BigIntegers</returns>
/// <exception cref="BigIntegerException">
/// Cannot compute the Gcd of negative BigIntegers exception</exception>
public static BigInteger ExtendedEuclidGcd(BigInteger a, BigInteger b,
                                           out BigInteger u, out BigInteger v)
{
     if ((a.sign == Sign.Negative) || (b.sign == Sign.Negative))
          throw new BigIntegerException
		("Cannot compute the Gcd of negative BigIntegers.", null);

     BigInteger u1 = new BigInteger();
     BigInteger u2 = new BigInteger(1);
     BigInteger v1 = new BigInteger(1);
     BigInteger v2 = new BigInteger();
     BigInteger q, r;

     u = new BigInteger();
     v = new BigInteger();

     while (b > Zero)
     {
          q = a / b;
          r = a - q * b;
          u = u2 - q * u1;
          v = v2 - q * v1;

          a = new BigInteger(b);
          b = new BigInteger(r);
          u2 = new BigInteger(u1);
          u1 = new BigInteger(u);
          v2 = new BigInteger(v1);
          v1 = new BigInteger(v);
          u = new BigInteger(u2);
          v = new BigInteger(v2);
     }

     return a;
}

模运算函数：模逆元、通过重复平方的模幂运算（用于 Miller-Rabin 素数测试以及 RSA 密钥生成、加密和解密过程）

/// <summary>
/// Computes the modular inverse of a given BigInteger.
/// </summary>
/// <param name="a">The non-zero BigInteger whose inverse is to be computed</param>
/// <param name="n">The BigInteger modulus, 
/// which must be greater than or equal to 2
/// </param>
/// <returns>The BigInteger equal to a^(-1) mod n</returns>
/// <exception cref="BigIntegerException">Invalid number or modulus exception
/// </exception>
public static BigInteger ModularInverse(BigInteger a, BigInteger n)
{
     if (n < Two)
          throw new BigIntegerException("Cannot perform a 
		modulo operation against a BigInteger less than 2.", null);

     if (Abs(a) >= n)
          a %= n;
     if (a.sign == Sign.Negative)
          a += n;

     if (a == Zero)
          throw new BigIntegerException("Cannot obtain the 
				modular inverse of 0.", null);

     if (Gcd(a, n) != One)
          throw new BigIntegerException("Cannot obtain the 
	  modular inverse of a number that is not 
		coprime with the modulus.", null);

     BigInteger u, v;
     ExtendedEuclid(n, a, out u, out v);
     if (v.sign == Sign.Negative)
          v += n;

     return v;
}

/// <summary>
/// Returns the power of a BigInteger to a non-negative exponent modulo n, 
/// by using the fast exponentiation algorithm 
/// (right to left binary exponentiation) and modulo optimizations.
/// </summary>
/// <param name="a">The BigInteger base</param>
/// <param name="exponent">The non-negative exponent</param>
/// <param name="n">The modulus, which must be greater than or equal to 2</param>
/// <returns>The power of the BigInteger to the non-negative exponent</returns>
/// <exception cref="BigIntegerException">Invalid exponent or modulus exception
/// </exception>
public static BigInteger ModularExponentiation
	(BigInteger a, BigInteger exponent, BigInteger n)
{
     if (exponent < 0)
          throw new BigIntegerException
		("Cannot raise a BigInteger to a negative power.", null);

     if (n < Two)
          throw new BigIntegerException("Cannot perform a 
		modulo operation against a BigInteger less than 2.", null);

     if (Abs(a) >= n)
          a %= n;
     if (a.sign == Sign.Negative)
          a += n;

     if (a == Zero)
          return new BigInteger();

     BigInteger res = new BigInteger(1);
     BigInteger factor = new BigInteger(a);

     while (exponent > Zero)
     {
          if (exponent % Two == One)
               res = (res * factor) % n;
          exponent /= Two;
          factor = (factor * factor) % n;
     }

     return res;
}

复合素数测试方法（包括对小于 1000 的素数进行试除，然后进行 Miller-Rabin 测试）

/// <summary>
/// Determines whether the given BigInteger number is probably prime, 
/// with a probability of at least 1/(4^MaxMillerRabinIterations), 
/// using the Miller-Rabin primality test.
/// </summary>
private static bool IsPrimeMillerRabinTest(BigInteger number)
{
     BigInteger s = new BigInteger();
     BigInteger t = number - One;
     BigInteger b = new BigInteger(2);
     BigInteger nmin1 = number - One;
     BigInteger r, j, smin1;

     if (number == One)
          return false;
     else if (number == Two)
          return true;
     else if (number == Three)
          return true;

     while (t % Two == Zero)
     {
          t /= Two;
          s++;
     }

     smin1 = s - One;

     for (int i = 0; i < MaxMillerRabinIterations; i++)
     {
          r = BigInteger.ModularExponentiation(b, t, number);

          if ((r != One) && (r != nmin1))
          {
               j = new BigInteger(One);
               while ((j <= smin1) && (r != nmin1))
               {
                    r = (r * r) % number;
                    if (r == One)
                         return false;
                    j++;
               }
               if (r != nmin1)
                    return false;
          }

          if (b == Two)
               b++;
          else
               b += Two;
      }

      return true;
}

之前提到的大部分操作的理论和算法可以在我的学士学位论文 [2] 的第 2 章和第 3 章中找到。

其他提及

为了在十进制（十进制）中显示 BigInteger ，该库使用了一个精简版的 BigInteger 类，称为 Base10BigInteger ，其中数制基数设置为 10 ，并将数字从 BigInteger 类的基数 65536 实时转换。C# 中 C++ 风格的泛型抽象（允许按值（基数）进行参数化）的可用性本可以消除这个辅助类的必要性。

BigInteger 库旨在简单明了。它重载了所有算术运算符，因此客户端程序员可以使用 BigInteger 就像使用普通内置数值类型一样。

此外，BigInteger 类实现了 ISerializable 、IEquatable<T> 、IComparable 和 IComparable<T> 接口。

示例代码

以下是与该库交互的一个小示例

BigInteger m = new BigInteger("982451159");
BigInteger m2 = m + 31567;
Console.WriteLine(BigInteger.IsPrime(m));
BigInteger n = BigInteger.Power(m, 10);
BigInteger p = BigInteger.Power(m, 4);
Console.WriteLine(BigInteger.IntegerSqrt(n) / p == m);
BigInteger q = BigInteger.ModularExponentiation(m, n, p);
Console.WriteLine(q.ToString());

库和加密应用程序

BigInteger 和 BigInteger-Mono 库（属于同一个 Google Code 项目）的完整源代码和二进制文件可以在此处访问。

我还提供了一套实现了 RSA 和 Rabin 密码系统的加密应用程序，它们依赖于一个旧版本的 BigInteger 库。这些可以在此处找到。

我非常欢迎对这个 BigInteger 开源（LGPL）项目的贡献和反馈。

参考文献

[1] P. B. Hansen, Multiple-length Division Revisited: a Tour of the Minefield, Software - Practice and Experience, vol. 24(6), 579-601, 1994

[2] The Prime Pages, http://primes.utm.edu/

[3] The Microsoft Developer Network (MSDN) pages

历史

版本 0.1 - 初始提交 - 2010/02/20
版本 0.2 - 将项目内容添加到 CodeProject - 2010/02/21
版本 0.5 - 更新项目内容和解释 - 2010/02/23
版本 1.0 - 源代码修订 - 2010/02/24
版本 1.1 - 在文章开头添加下载链接 - 2010/02/28
版本 1.2 - 为代码中的 public 方法添加了完整的 XML 注释 - 2010/03/13
版本 1.3 - 添加了 Mono 的二进制文件 - 2010/06/04
版本 1.4 - 更新了内容、源代码和二进制文件 - 2011/09/21