65.9K
CodeProject 正在变化。 阅读更多。
Home

C# BigInteger 类

Chew Keong TAN
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.89/5 (124投票s)

2002年8月9日

13分钟阅读

viewsIcon

1351595

downloadIcon

27117

C# 中 BigInteger 类的实现。

Sample Image - BigInteger.jpg

目录

引言

非对称加密方案的实现通常需要使用比编译器原生支持的整数数据类型大得多的数字。在本文中，我们介绍了涉及大整数的算术运算的实现。由于该主题既复杂又冗长，我们不打算进行全面覆盖。有关更详细的处理，读者可参考所列的参考资料。

本文附带的源代码实现了一个支持大整数算术运算的BigInteger类。重载的运算符包括 +、-、*、/、%、>>、<<、==、!=、>、<、>=、<=、&、|、^、++、-- 和 ~。其他附加功能，如模幂运算、模逆元、伪素数生成和概率素性测试也得到支持。

特点
  • 涉及2的补码表示的大整数的算术运算。
  • 使用费马小定理、Rabin Miller方法和Solovay Strassen方法进行素数测试。
  • 使用Barrett约简进行模幂运算。
  • 模逆元。
  • 随机伪素数生成。
  • 随机互素数生成。
  • 最大公约数。

实现细节

表示数字最常见的方式是使用位置表示法。数字使用数字来表示指定基数的幂的倍数。我们日常生活中最熟悉和使用的基数是10。当我们用10进制写出数字12345时，它实际的意思是

1234510= 1x104 + 2x103 + 3x102 + 4x101 + 5x100

类似地，如果同一个数字以16进制表示，那么

1234516= 1x164 + 2x163 + 3x162 + 4x161 + 5x160

因此，了解数字的基数很重要，因为在不同的基数下解释时，相同的表示可能代表不同的值。一般来说，正数可以写成一个k阶多项式，其中k是非负的且ak != 0。

n = akbk + ak-1bk-1 + ... + a1b1 + a0

b代表基数，其中0 <= a <= b-1。

对于10进制表示，b = 10，每个位置允许的数字是0 <= a <= 9。

大整数加法

两个数字的加法可以表示为两个多项式的加法，如下所示。

设
n = akbk + ak-1bk-1 + ... + a1b1 + a0
m = ckbk + ck-1bk-1 + ... + c1b1 + c0

那么
n + m = (ak + ck)bk + (ak-1 + ck-1)bk-1 + ... + (a1 + c1)b1 + (a0 + c0)

然而，将两个大数相加可视化为每个位置的逐位相加通常更容易。当我们相加一个特定位置的数字时，最大的结果值是2b - 2。

证明

由于每个数字的最大值为b - 1，我们有

(b - 1) + (b - 1) = 2b - 2。

由于 2b - 2 < 2b，我们要向更高位置进位的最大值为1。例如，如果我们用10进制相加9和9，得到18，其中8保留在当前位置，1被“进位”到下一个更高位置。在相加下一个位置的两个数字时，我们必须记住也加上进位。

在我们的BigInteger实现中，我们将数字存储为连续字节的数组。这相当于以256为基数表示数字，每个数字的值为0到FF。下面给出了一个数字示例，显示了在此基数下两个数字的加法。

      1  1
     FE A6 FF
  +     FF FF
  -----------
     FF A6 FE
  -----------

在此示例中，FF + FF = 1FE。这超过了256基数中每个数字的最大值。因此，我们在当前位置保留FE，并将1进位到下一个更高位置。下面的代码段显示了这是如何完成的。

// code segment that performs byte-by-byte addition
int carry = 0;
for(int i = 0; i < len; i++)
{
        // bi1 and bi2 are the two large numbers to add.
        // data is the byte array holding the large number.

        int sum = bi1.data[i] + bi2.data[i] + carry;
        carry  = sum >> 8;
        result.data[i] = (byte)(sum & 0xFF);
}

大整数减法

两个数字的减法与加法非常相似，可以轻松地实现为逐字节减法。但是，在减去两个数字时，我们经常会遇到第一个数字小于第二个数字的情况。在这种情况下，我们必须从下一个位置的数字中“借”1。这实际上是通过从下一个更高位置的数字中减去1并将基数的值加到当前数字来实现的。例如，

     2 AF
  -    FF
    -----
     1 B0
    -----

在这种情况下，由于 AF < FF，我们从下一个更高数字 2 中减去 1，计算 1AF - FF = B0。下面的代码段显示了如何执行逐字节减法。

// code segment that performs byte-by-byte subtraction

int carryIn = 0;

for(int i = 0; i < len; i++)
{
    int diff, totalSub;

    // calculate the total value to be subtracted
    // from the current
    // digit.
    totalSub = bi2.data[i] + carryIn;

    // if total value to be subtracted is larger than the
    // currentdigit.

    if(bi1.data[i] < totalSub)
    {
        // we add the value of the base to the current
        // digit and remember to subtract 1 from the
        // next higher digit.

        diff = (bi1.data[i] + 0x100) - totalSub;
        carryIn = 1;
    }
    else
    {
        diff = bi1.data[i] - totalSub;
        carryIn = 0;
    }

    result.data[i] = (byte)diff;
}

大整数乘法

实现乘法的最简单方法是重复相加。为简化分析，我们假设乘数和被乘数具有相同数量的数字。计算 a * b，我们将结果设置为0，然后将a重复加到结果中b次。虽然这种方法很简单，但其复杂度是O(b)次大整数加法，相当于O(bn)次逐字节加法，其中n是大整数的位数。对于大的b，O(bn) > O(n2)。因此，这种方法不能扩展到大的乘数。

下一个最简单的方法是使用我们在小学学到的技术。更具体地说，我们将a乘以b的每个数字，然后对部分结果求和。在下面的示例中，我们用256进制说明计算 02AF x 01FF。

我们首先计算 02AF x FF

     AE
     02 AF
  x     FF
   -------
   2 AC 51
   -------

请注意，当我们乘以 AF x FF 时，得到 AE51。由于这超过了256基数，我们在当前位置保留51，并将AF进位到下一个更高位置。然后我们继续到下一个位置，乘以02 x FF，记住要加上进位以得到02AC。

接下来，我们计算 02AF x 01

     02 AF
  x     01
   -------
     02 AF
   -------

最后，我们对部分结果求和。

      1
     02 AC 51   (result from 02AF x FF)
  +  02 AF 00   (result from 02AF x 01 with 00 appended)
   ----------
     05 5B 51
   ----------

从这个说明中可以清楚地看出，两个大整数相乘的时间复杂度是O(n2)次字节乘法，其中 n 是数字的位数。部分结果的加法过程复杂度为O(n)次大整数加法，相当于O(n2)次字节加法。因此，总复杂度为O(n2)次字节乘法和O(n2)次字节加法。我们在BigInteger类中实现了这种方法，如下面的代码段所示。

for(int i = 0; i < bi1.byteLength; i++)
{
    int mcarry = 0;
    for(int j = 0; j < bi2.byteLength; j++)
    {
        // compute the byte multiplication and the addition
        // of the partial results in a single step.

        int val = (bi1.data[i] * bi2.data[j]) +
            tempResult[i+j] + mcarry;

        tempResult[i+j] = (byte)(val & 0xFF);
        mcarry = (val >> 8);
    }

    tempResult[i+bi2.byteLength] = (byte)mcarry;
}

大整数除法

请参考所列的参考资料。

使用费马小定理进行素性测试

素性测试的目的是找出给定的数字是否为素数。素数是只能被1和自身整除的数。通过测试它是否能被小于 sqrt(n) 的素数整除，很容易确定一个小数字 n 的素性。对于大整数，这种方法不实用。相反，我们只能确定大整数是否是*大概率素数*。这被称为*概率素性测试*，通过测试的数字被称为*伪素数*。有许多*概率素性测试*方法，但在本文中，我们将只讨论基于费马小定理的方法。

根据费马小定理，我们知道

an mod n = a

对于任何整数a和任何素数n。这意味着如果n是素数，那么对于任何整数a，an mod n = a。该陈述的逆否命题表明，如果对于某个整数a，an mod n != a，那么n不是素数。

不幸的是，定理的逆命题不成立。这意味着如果an mod n = a，我们不能确定n是否是素数。然而，我们可以利用逆否命题来确定n是否是合数。换句话说，如果存在一个整数a使得an mod n != a，那么n不是素数。通过测试足够多的a，我们可以排除合数并保留大概率素数。下面的源代码说明了这一点。

// confidence determines the number of times to test.

for(int round = 0; round < confidence; round++)
{
    // generate random a < n
    a.genRandomBits(testBits, rand);

    // calculate a^(n) mod n, where thisVal = n
    BigInteger expResult = a.modPow(thisVal, thisVal);

    // is NOT prime if a^(p) mod p != a
    if(expResult != a)
        return false;
}

return true;

有一类合数称为Carmichael数，它们在使用此测试时无法与真素数区分开来。这些整数对于所有与n互素的正整数a都满足an mod n = a。

示例代码

生成一个512位随机伪素数。

public static void Main(string[] args)
{
    Console.Write(
        "\nGenerating 512-bits random pseudoprime. . .");

    Random rand = new Random();
    BigInteger prime = BigInteger.genPseudoPrime(
        512, 5, rand);

    Console.WriteLine("\n" + prime);
}

涉及BigInteger的算术运算。

public static void Main(string[] args)
{
    // define two BigIntegers in base 10
    BigInteger bn1 = new BigInteger("12345678901234567890",
        10);
    BigInteger bn2 = new BigInteger("4321", 10);

    // Determine the quotient and remainder by dividing
    // the first number by the second.
    BigInteger bn3 = bn1 / bn2;
    BigInteger bn4 = bn1 % bn2;

    // Recalculate the number
    BigInteger bn5 = (bn3 * bn2) + bn4;

    Console.WriteLine("bn1 = " + bn1);
    Console.WriteLine("bn5 = " + bn5);
}

非对称加密和解密。

public static void Main(string[] args)
{
    // private and public key
    BigInteger bi_e = new BigInteger(
        "a932b948feed4fb2b692609bd22164fc9edb" +
        "59fae7880cc1eaff7b3c9626b7e5b241c27a" +
        "974833b2622ebe09beb451917663d4723248" +
        "8f23a117fc97720f1e7", 16);

    BigInteger bi_d = new BigInteger(
        "4adf2f7a89da93248509347d2ae506d683dd" +
        "3a16357e859a980c4f77a4e2f7a01fae289f" +
        "13a851df6e9db5adaa60bfd2b162bbbe31f7" +
        "c8f828261a6839311929d2cef4f864dde65e" +
        "556ce43c89bbbf9f1ac5511315847ce9cc8d" +
        "c92470a747b8792d6a83b0092d2e5ebaf852" +
        "c85cacf34278efa99160f2f8aa7ee7214de07b7", 16);

    BigInteger bi_n = new BigInteger(
        "e8e77781f36a7b3188d711c2190b560f205a" +
        "52391b3479cdb99fa010745cbeba5f2adc08" +
        "e1de6bf38398a0487c4a73610d94ec36f17f" +
        "3f46ad75e17bc1adfec99839589f45f95ccc" +
        "94cb2a5c500b477eb3323d8cfab0c8458c96" +
        "f0147a45d27e45a4d11d54d77684f65d48f1" +
        "5fafcc1ba208e71e921b9bd9017c16a5231af7f", 16);

    Console.WriteLine("e =\n" + bi_e.ToString(10));
    Console.WriteLine("\nd =\n" + bi_d.ToString(10));
    Console.WriteLine("\nn =\n" + bi_n.ToString(10) + "\n");

    // data
    BigInteger bi_data = new BigInteger(
        "12345678901234567890", 10);

    // encrypt and decrypt data
    BigInteger bi_encrypted = bi_data.modPow(bi_e, bi_n);
    BigInteger bi_decrypted = bi_encrypted.modPow(
        bi_d, bi_n);

    Console.WriteLine("bi_data = " + bi_data);
    Console.WriteLine("\nbi_encrypted =\n" + bi_encrypted);
    Console.WriteLine("\nbi_decrypted = " + bi_decrypted);
}

性能评估

本节评估并呈现了基本算术运算符的性能。我们观察到从字节级到32位字级操作的显著性能改进。在模幂运算中使用Barrett约简，以及使用更快的算法计算雅可比符号，都极大地提高了RSA和概率素性测试的速度。

所有评估代码均使用csc BigInteger.cs /o编译，并在Pentium III 800Mhz笔记本电脑上执行。对于涉及随机数生成的测试，我们使用内置的Random类，并为每个测试使用相同的初始种子值1。操作计时使用以下代码完成。
    int dwStart = System.Environment.TickCount;

    // Perform the test.

    Console.WriteLine(System.Environment.TickCount - dwStart);

基本算术运算符

为了测试加法运算符的性能，我们生成了两个各1024位的随机BigIntegers并将它们相加。此测试重复了100000次，并记录了完成任务的总时间。减法和乘法运算符以类似的方式进行了测试。对于除法运算符，我们生成了两个随机BigIntegers，每个的长度在2到1024位之间。然后用较小的数除较大的数。此测试重复了100000次，并记录了完成测试的总时间。结果如下面的图表所示。

算术运算速度比较 - BigIntegerArithOpGraph.jpg

模幂运算

通过生成三个随机BigIntegers来评估模幂运算的速度，其中a = 512位，e = 512位，n = 1024位。然后计算幂运算 ae mod n。该测试使用100个不同的a、e、n值重复进行，并计算每次幂运算的平均时间。下图显示了结果。

模幂运算速度比较 - BigIntegerModPowGraph.jpg

雅可比符号计算

通过生成两个各1024位的随机BigIntegers来评估雅可比符号计算的速度。计算这两个数字的雅可比符号值，并使用不同的数字对重复测试100次。下图显示了每次计算的平均时间。

雅可比计算速度比较 - BigIntegerJacobiGraph.jpg

素性测试的速度

在我们的BigInteger类中，我们提供了两个执行整数概率素性测试的函数。第一个方法bool isProbablePrime(int confidence)，使用Rabin-Miller强伪素数测试来确定该整数是否是大概率素数。算法描述如下。

  1. 测试数字是否能被2000以下的素数整除。
  2. 使用n个随机基数对数字执行强伪素数测试。测试中使用的随机基数的数量取决于confidence参数。
  3. 如果数字通过步骤1和2，则函数返回true。

第二个素性测试方法bool isProbablePrime()不需要指定置信度参数。对测试的简要描述如下。

  1. 测试数字是否能被2000以下的素数整除。
  2. 测试数字是否是基数2的强伪素数。如果数字通过此测试，则继续执行下一步。
  3. 测试数字是否是强Lucas伪素数。
  4. 如果数字通过步骤1、2和3，则函数返回true。

此测试基于这样一个假设：一个复合数同时是基数2强伪素数和强Lucas伪素数的概率极低。有关此方法的详细讨论，请参阅[6],[7]和[8]。

我们通过测量每种算法将已知素数声明为大概率素数所需的时间来比较这两种算法的性能。512位和1024位数字的结果如下面的图表所示。

Primality Test Speed Comparison - BigIntegerPrimeGraph.jpg

从结果可以看出，对于512位的素数，isProbablePrime()比isProbablePrime(10)（使用10轮Rabin-Miller测试）略慢。然而，对于1024位的素数，isProbablePrime()比isProbablePrime(10)明显快。

限制

以下正伪素数和其他几个伪素数通过了我们实现的素性测试，但在JDK的isProbablePrime测试中失败了。任何关于原因的建议都将不胜感激。

byte[] pseudoPrime1 = { (byte)0x00,
        (byte)0x85, (byte)0x84, (byte)0x64, (byte)0xFD,
        (byte)0x70, (byte)0x6A, (byte)0x9F, (byte)0xF0,
        (byte)0x94, (byte)0x0C, (byte)0x3E, (byte)0x2C,
        (byte)0x74, (byte)0x34, (byte)0x05, (byte)0xC9,
        (byte)0x55, (byte)0xB3, (byte)0x85, (byte)0x32,
        (byte)0x98, (byte)0x71, (byte)0xF9, (byte)0x41,
        (byte)0x21, (byte)0x5F, (byte)0x02, (byte)0x9E,
        (byte)0xEA, (byte)0x56, (byte)0x8D, (byte)0x8C,
        (byte)0x44, (byte)0xCC, (byte)0xEE, (byte)0xEE,
        (byte)0x3D, (byte)0x2C, (byte)0x9D, (byte)0x2C,
        (byte)0x12, (byte)0x41, (byte)0x1E, (byte)0xF1,
        (byte)0xC5, (byte)0x32, (byte)0xC3, (byte)0xAA,
        (byte)0x31, (byte)0x4A, (byte)0x52, (byte)0xD8,
        (byte)0xE8, (byte)0xAF, (byte)0x42, (byte)0xF4,
        (byte)0x72, (byte)0xA1, (byte)0x2A, (byte)0x0D,
        (byte)0x97, (byte)0xB1, (byte)0x31, (byte)0xB3,
};

byte[] pseudoPrime2 = { (byte)0x00,
        (byte)0x99, (byte)0x98, (byte)0xCA, (byte)0xB8,
        (byte)0x5E, (byte)0xD7, (byte)0xE5, (byte)0xDC,
        (byte)0x28, (byte)0x5C, (byte)0x6F, (byte)0x0E,
        (byte)0x15, (byte)0x09, (byte)0x59, (byte)0x6E,
        (byte)0x84, (byte)0xF3, (byte)0x81, (byte)0xCD,
        (byte)0xDE, (byte)0x42, (byte)0xDC, (byte)0x93,
        (byte)0xC2, (byte)0x7A, (byte)0x62, (byte)0xAC,
        (byte)0x6C, (byte)0xAF, (byte)0xDE, (byte)0x74,
        (byte)0xE3, (byte)0xCB, (byte)0x60, (byte)0x20,
        (byte)0x38, (byte)0x9C, (byte)0x21, (byte)0xC3,
        (byte)0xDC, (byte)0xC8, (byte)0xA2, (byte)0x4D,
        (byte)0xC6, (byte)0x2A, (byte)0x35, (byte)0x7F,
        (byte)0xF3, (byte)0xA9, (byte)0xE8, (byte)0x1D,
        (byte)0x7B, (byte)0x2C, (byte)0x78, (byte)0xFA,
        (byte)0xB8, (byte)0x02, (byte)0x55, (byte)0x80,
        (byte)0x9B, (byte)0xC2, (byte)0xA5, (byte)0xCB,
};

未来工作
  • 更快的算术运算实现。
  • 更强大的素性测试方法。
  • 更快的伪素数生成

结论

在本文中，我们对大整数算术主题进行了简要介绍。我们研究了大整数加法、减法和乘法的实现。我们还探讨了素性测试问题，并介绍了基于费马小定理的素性测试概念。我们的BigInteger类的实现可以从本页下载，并提供了大多数算术运算符的重载。我们指出了我们实现的素性测试的局限性，并且我们正在努力开发更强大的素性测试方法和更快的算术运算符实现。

更改日志
  • 2002年9月23日
    • 版本1.03
    • 修复了operator-以提供正确的数据长度。
    • 添加了Lucas序列生成。
    • 添加了强Lucas素性测试。
    • 添加了整数平方根方法。
    • 添加了setBit/unsetBit方法。
    • 新的isProbablePrime()方法，不需要置信度参数。
  • 2002年8月29日
    • 版本1.02
    • 修复了负数指数运算中的错误。
    • 使用Barrett约简实现更快的模幂运算。
    • 添加了getBytes()方法。
    • 修复了ToHexString方法中的错误。
    • 添加了^运算符的重载。
    • 更快的雅可比符号计算。
  • 2002年8月19日
    • 版本1.01
    • 大整数以无符号整数（4字节）而不是单个字节的形式存储和操作。这带来了显著的性能提升。
    • 更新了费马小定理测试以使用a(p-1) mod p = 1
    • 添加了isProbablePrime方法。
    • 更新了文档。
  • 2002年8月9日
    • 版本 1.0
    • 首次发布。

参考文献

[1] D. E. Knuth, "Seminumerical Algorithms", The Art of Computer Programming Vol. 2, 3rd Edition, Addison-Wesley, 1998。

[2] K. H. Rosen, "Elementary Number Theory and Its Applications", 3rd Ed, Addison-Wesley, 1993。

[3] B. Schneier, "Applied Cryptography", 2nd Ed, John Wiley & Sons, 1996。

[4] A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography", CRC Press, 1996, www.cacr.math.uwaterloo.ca/hac

[5] A. Bosselaers, R. Govaerts, and J. Vandewalle, "Comparison of Three Modular Reduction Functions", Proc. CRYPTO'93, pp.175-186。

[6] R. Baillie and S. S. Wagstaff Jr, "Lucas Pseudoprimes", Mathematics of Computation, Vol. 35, No. 152, Oct 1980, pp. 1391-1417。

[7] H. C. Williams, "Édouard Lucas and Primality Testing", Canadian Mathematical Society Series of Monographs and Advance Texts, vol. 22, John Wiley & Sons, New York, NY, 1998。

[8] P. Ribenboim, "The new book of prime number records", 3rd edition, Springer-Verlag, New York, NY, 1995。

[9] M. Joye and J.-J. Quisquater, "Efficient computation of full Lucas sequences", Electronics Letters, 32(6), 1996, pp 537-538。

© . All rights reserved.