开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Internet/网络编程 > Telnet服务器 > 查看源码
BigInteger.cs
资源名称：Terminal_Control_jan_2009.zip　[点击查看]
上传用户：szltgg
上传日期：2019-05-16
资源大小：604k
文件大小：126k
源码类别：

Telnet服务器

开发平台：

C#

BigInteger.cs：源码内容
  1. //************************************************************************************
  2. // BigInteger Class Version 1.03
  3. //
  4. // Copyright (c) 2002 Chew Keong TAN
  5. // All rights reserved.
  6. //
  7. // Permission is hereby granted, free of charge, to any person obtaining a
  8. // copy of this software and associated documentation files (the
  9. // "Software"), to deal in the Software without restriction, including
  10. // without limitation the rights to use, copy, modify, merge, publish,
  11. // distribute, and/or sell copies of the Software, and to permit persons
  12. // to whom the Software is furnished to do so, provided that the above
  13. // copyright notice(s) and this permission notice appear in all copies of
  14. // the Software and that both the above copyright notice(s) and this
  15. // permission notice appear in supporting documentation.
  16. //
  17. // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  18. // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19. // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
  20. // OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
  21. // HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
  22. // INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
  23. // FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
  24. // NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
  25. // WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  26. //
  27. //
  28. // Disclaimer
  29. // ----------
  30. // Although reasonable care has been taken to ensure the correctness of this
  31. // implementation, this code should never be used in any application without
  32. // proper verification and testing.  I disclaim all liability and responsibility
  33. // to any person or entity with respect to any loss or damage caused, or alleged
  34. // to be caused, directly or indirectly, by the use of this BigInteger class.
  35. //
  36. // Comments, bugs and suggestions to
  37. // (http://www.codeproject.com/csharp/biginteger.asp)
  38. //
  39. //
  40. // Overloaded Operators +, -, *, /, %, >>, <<, ==, !=, >, <, >=, <=, &, |, ^, ++, --, ~
  41. //
  42. // Features
  43. // --------
  44. // 1) Arithmetic operations involving large signed integers (2's complement).
  45. // 2) Primality test using Fermat little theorm, Rabin Miller's method,
  46. //    Solovay Strassen's method and Lucas strong pseudoprime.
  47. // 3) Modulo exponential with Barrett's reduction.
  48. // 4) Inverse modulo.
  49. // 5) Pseudo prime generation.
  50. // 6) Co-prime generation.
  51. //
  52. //
  53. // Known Problem
  54. // -------------
  55. // This pseudoprime passes my implementation of
  56. // primality test but failed in JDK's isProbablePrime test.
  57. //
  58. //       byte[] pseudoPrime1 = { (byte)0x00,
  59. //             (byte)0x85, (byte)0x84, (byte)0x64, (byte)0xFD, (byte)0x70, (byte)0x6A,
  60. //             (byte)0x9F, (byte)0xF0, (byte)0x94, (byte)0x0C, (byte)0x3E, (byte)0x2C,
  61. //             (byte)0x74, (byte)0x34, (byte)0x05, (byte)0xC9, (byte)0x55, (byte)0xB3,
  62. //             (byte)0x85, (byte)0x32, (byte)0x98, (byte)0x71, (byte)0xF9, (byte)0x41,
  63. //             (byte)0x21, (byte)0x5F, (byte)0x02, (byte)0x9E, (byte)0xEA, (byte)0x56,
  64. //             (byte)0x8D, (byte)0x8C, (byte)0x44, (byte)0xCC, (byte)0xEE, (byte)0xEE,
  65. //             (byte)0x3D, (byte)0x2C, (byte)0x9D, (byte)0x2C, (byte)0x12, (byte)0x41,
  66. //             (byte)0x1E, (byte)0xF1, (byte)0xC5, (byte)0x32, (byte)0xC3, (byte)0xAA,
  67. //             (byte)0x31, (byte)0x4A, (byte)0x52, (byte)0xD8, (byte)0xE8, (byte)0xAF,
  68. //             (byte)0x42, (byte)0xF4, (byte)0x72, (byte)0xA1, (byte)0x2A, (byte)0x0D,
  69. //             (byte)0x97, (byte)0xB1, (byte)0x31, (byte)0xB3,
  70. //       };
  71. //
  72. //
  73. // Change Log
  74. // ----------
  75. // 1) September 23, 2002 (Version 1.03)
  76. //    - Fixed operator- to give correct data length.
  77. //    - Added Lucas sequence generation.
  78. //    - Added Strong Lucas Primality test.
  79. //    - Added integer square root method.
  80. //    - Added setBit/unsetBit methods.
  81. //    - New isProbablePrime() method which do not require the
  82. //      confident parameter.
  83. //
  84. // 2) August 29, 2002 (Version 1.02)
  85. //    - Fixed bug in the exponentiation of negative numbers.
  86. //    - Faster modular exponentiation using Barrett reduction.
  87. //    - Added getBytes() method.
  88. //    - Fixed bug in ToHexString method.
  89. //    - Added overloading of ^ operator.
  90. //    - Faster computation of Jacobi symbol.
  91. //
  92. // 3) August 19, 2002 (Version 1.01)
  93. //    - Big integer is stored and manipulated as unsigned integers (4 bytes) instead of
  94. //      individual bytes this gives significant performance improvement.
  95. //    - Updated Fermat's Little Theorem test to use a^(p-1) mod p = 1
  96. //    - Added isProbablePrime method.
  97. //    - Updated documentation.
  98. //
  99. // 4) August 9, 2002 (Version 1.0)
  100. //    - Initial Release.
  101. //
  102. //
  103. // References
  104. // [1] D. E. Knuth, "Seminumerical Algorithms", The Art of Computer Programming Vol. 2,
  105. //     3rd Edition, Addison-Wesley, 1998.
  106. //
  107. // [2] K. H. Rosen, "Elementary Number Theory and Its Applications", 3rd Ed,
  108. //     Addison-Wesley, 1993.
  109. //
  110. // [3] B. Schneier, "Applied Cryptography", 2nd Ed, John Wiley & Sons, 1996.
  111. //
  112. // [4] A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography",
  113. //     CRC Press, 1996, www.cacr.math.uwaterloo.ca/hac
  114. //
  115. // [5] A. Bosselaers, R. Govaerts, and J. Vandewalle, "Comparison of Three Modular
  116. //     Reduction Functions," Proc. CRYPTO'93, pp.175-186.
  117. //
  118. // [6] R. Baillie and S. S. Wagstaff Jr, "Lucas Pseudoprimes", Mathematics of Computation,
  119. //     Vol. 35, No. 152, Oct 1980, pp. 1391-1417.
  120. //
  121. // [7] H. C. Williams, "蒬ouard Lucas and Primality Testing", Canadian Mathematical
  122. //     Society Series of Monographs and Advance Texts, vol. 22, John Wiley & Sons, New York,
  123. //     NY, 1998.
  124. //
  125. // [8] P. Ribenboim, "The new book of prime number records", 3rd edition, Springer-Verlag,
  126. //     New York, NY, 1995.
  127. //
  128. // [9] M. Joye and J.-J. Quisquater, "Efficient computation of full Lucas sequences",
  129. //     Electronics Letters, 32(6), 1996, pp 537-538.
  130. //
  131. //************************************************************************************
  133. using System;
  136. public class BigInteger
  137. {
  138.         // maximum length of the BigInteger in uint (4 bytes)
  139.         // change this to suit the required level of precision.
  141.         private const int maxLength = 130;
  143.         // primes smaller than 2000 to test the generated prime number
  145.         public static readonly int[] primesBelow2000 = {
  146.         2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
  147.         101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
  148. 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
  149. 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
  150. 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
  151. 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
  152. 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
  153. 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
  154. 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
  155. 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
  156. 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
  157. 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193,
  158. 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297,
  159. 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
  160. 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499,
  161. 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
  162. 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699,
  163. 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
  164. 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
  165. 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999 };
  168.         private uint[] data = null;             // stores bytes from the Big Integer
  169.         public int dataLength;                 // number of actual chars used
  172. public bool IsNegative {
  173. get {
  174. return (data[maxLength - 1] & 0x80000000) != 0;
  175. }
  176. }
  180.         //***********************************************************************
  181.         // Constructor (Default value for BigInteger is 0
  182.         //***********************************************************************
  184.         public BigInteger()
  185.         {
  186.                 data = new uint[maxLength];
  187.                 dataLength = 1;
  188.         }
  191.         //***********************************************************************
  192.         // Constructor (Default value provided by long)
  193.         //***********************************************************************
  195.         public BigInteger(long value)
  196.         {
  197.                 data = new uint[maxLength];
  198.                 long tempVal = value;
  200.                 // copy bytes from long to BigInteger without any assumption of
  201.                 // the length of the long datatype
  203.                 dataLength = 0;
  204.                 while(value != 0 && dataLength < maxLength)
  205.                 {
  206.                         data[dataLength] = (uint)(value & 0xFFFFFFFF);
  207.                         value >>= 32;
  208.                         dataLength++;
  209.                 }
  211.                 if(tempVal > 0)         // overflow check for +ve value
  212.                 {
  213.                         if(value != 0 || (data[maxLength-1] & 0x80000000) != 0)
  214.                                 throw(new ArithmeticException("Positive overflow in constructor."));
  215.                 }
  216.                 else if(tempVal < 0)    // underflow check for -ve value
  217.                 {
  218.                         if(value != -1 || (data[dataLength-1] & 0x80000000) == 0)
  219.                                 throw(new ArithmeticException("Negative underflow in constructor."));
  220.                 }
  222.                 if(dataLength == 0)
  223.                         dataLength = 1;
  224.         }
  227.         //***********************************************************************
  228.         // Constructor (Default value provided by ulong)
  229.         //***********************************************************************
  231.         public BigInteger(ulong value)
  232.         {
  233.                 data = new uint[maxLength];
  235.                 // copy bytes from ulong to BigInteger without any assumption of
  236.                 // the length of the ulong datatype
  238.                 dataLength = 0;
  239.                 while(value != 0 && dataLength < maxLength)
  240.                 {
  241.                         data[dataLength] = (uint)(value & 0xFFFFFFFF);
  242.                         value >>= 32;
  243.                         dataLength++;
  244.                 }
  246.                 if(value != 0 || (data[maxLength-1] & 0x80000000) != 0)
  247.                         throw(new ArithmeticException("Positive overflow in constructor."));
  249.                 if(dataLength == 0)
  250.                         dataLength = 1;
  251.         }
  255.         //***********************************************************************
  256.         // Constructor (Default value provided by BigInteger)
  257.         //***********************************************************************
  259.         public BigInteger(BigInteger bi)
  260.         {
  261.                 data = new uint[maxLength];
  263.                 dataLength = bi.dataLength;
  265.                 for(int i = 0; i < dataLength; i++)
  266.                         data[i] = bi.data[i];
  267.         }
  270.         //***********************************************************************
  271.         // Constructor (Default value provided by a string of digits of the
  272.         //              specified base)
  273.         //
  274.         // Example (base 10)
  275.         // -----------------
  276.         // To initialize "a" with the default value of 1234 in base 10
  277.         //      BigInteger a = new BigInteger("1234", 10)
  278.         //
  279.         // To initialize "a" with the default value of -1234
  280.         //      BigInteger a = new BigInteger("-1234", 10)
  281.         //
  282.         // Example (base 16)
  283.         // -----------------
  284.         // To initialize "a" with the default value of 0x1D4F in base 16
  285.         //      BigInteger a = new BigInteger("1D4F", 16)
  286.         //
  287.         // To initialize "a" with the default value of -0x1D4F
  288.         //      BigInteger a = new BigInteger("-1D4F", 16)
  289.         //
  290.         // Note that string values are specified in the <sign><magnitude>
  291.         // format.
  292.         //
  293.         //***********************************************************************
  295.         public BigInteger(string value, int radix)
  296.         {
  297.                 BigInteger multiplier = new BigInteger(1);
  298.                 BigInteger result = new BigInteger();
  299.                 value = (value.ToUpper()).Trim();
  300.                 int limit = 0;
  302.                 if(value[0] == '-')
  303.                         limit = 1;
  305.                 for(int i = value.Length - 1; i >= limit ; i--)
  306.                 {
  307.                         int posVal = (int)value[i];
  309.                         if(posVal >= '0' && posVal <= '9')
  310.                                 posVal -= '0';
  311.                         else if(posVal >= 'A' && posVal <= 'Z')
  312.                                 posVal = (posVal - 'A') + 10;
  313.                         else
  314.                                 posVal = 9999999;       // arbitrary large
  317.                         if(posVal >= radix)
  318.                                 throw(new ArithmeticException("Invalid string in constructor."));
  319.                         else
  320.                         {
  321.                                 if(value[0] == '-')
  322.                                         posVal = -posVal;
  324.                                 result = result + (multiplier * posVal);
  326.                                 if((i - 1) >= limit)
  327.                                         multiplier = multiplier * radix;
  328.                         }
  329.                 }
  331.                 if(value[0] == '-')     // negative values
  332.                 {
  333.                         if((result.data[maxLength-1] & 0x80000000) == 0)
  334.                                 throw(new ArithmeticException("Negative underflow in constructor."));
  335.                 }
  336.                 else    // positive values
  337.                 {
  338.                         if((result.data[maxLength-1] & 0x80000000) != 0)
  339.                                 throw(new ArithmeticException("Positive overflow in constructor."));
  340.                 }
  342.                 data = new uint[maxLength];
  343.                 for(int i = 0; i < result.dataLength; i++)
  344.                         data[i] = result.data[i];
  346.                 dataLength = result.dataLength;
  347.         }
  350.         //***********************************************************************
  351.         // Constructor (Default value provided by an array of bytes)
  352.         //
  353.         // The lowest index of the input byte array (i.e [0]) should contain the
  354.         // most significant byte of the number, and the highest index should
  355.         // contain the least significant byte.
  356.         //
  357.         // E.g.
  358.         // To initialize "a" with the default value of 0x1D4F in base 16
  359.         //      byte[] temp = { 0x1D, 0x4F };
  360.         //      BigInteger a = new BigInteger(temp)
  361.         //
  362.         // Note that this method of initialization does not allow the
  363.         // sign to be specified.
  364.         //
  365.         //***********************************************************************
  367.         public BigInteger(byte[] inData)
  368.         {
  369.                 dataLength = inData.Length >> 2;
  371.                 int leftOver = inData.Length & 0x3;
  372.                 if(leftOver != 0)         // length not multiples of 4
  373.                         dataLength++;
  376.                 if(dataLength > maxLength)
  377.                       throw(new ArithmeticException("Byte overflow in constructor."));
  379.                 data = new uint[maxLength];
  381.                 for(int i = inData.Length - 1, j = 0; i >= 3; i -= 4, j++)
  382.                 {
  383.                         data[j] = (uint)((inData[i-3] << 24) + (inData[i-2] << 16) +
  384.                                          (inData[i-1] <<  8) + inData[i]);
  385.                 }
  387.                 if(leftOver == 1)
  388.                         data[dataLength-1] = (uint)inData[0];
  389.                 else if(leftOver == 2)
  390.                         data[dataLength-1] = (uint)((inData[0] << 8) + inData[1]);
  391.                 else if(leftOver == 3)
  392.                         data[dataLength-1] = (uint)((inData[0] << 16) + (inData[1] << 8) + inData[2]);
  395.                 while(dataLength > 1 && data[dataLength-1] == 0)
  396.                         dataLength--;
  398.                 //Console.WriteLine("Len = " + dataLength);
  399.         }
  402.         //***********************************************************************
  403.         // Constructor (Default value provided by an array of bytes of the
  404.         // specified length.)
  405.         //***********************************************************************
  407.         public BigInteger(byte[] inData, int inLen)
  408.         {
  409.                 dataLength = inLen >> 2;
  411.                 int leftOver = inLen & 0x3;
  412.                 if(leftOver != 0)         // length not multiples of 4
  413.                         dataLength++;
  415.                 if(dataLength > maxLength || inLen > inData.Length)
  416.                       throw(new ArithmeticException("Byte overflow in constructor."));
  419.                 data = new uint[maxLength];
  421.                 for(int i = inLen - 1, j = 0; i >= 3; i -= 4, j++)
  422.                 {
  423.                         data[j] = (uint)((inData[i-3] << 24) + (inData[i-2] << 16) +
  424.                                          (inData[i-1] <<  8) + inData[i]);
  425.                 }
  427.                 if(leftOver == 1)
  428.                         data[dataLength-1] = (uint)inData[0];
  429.                 else if(leftOver == 2)
  430.                         data[dataLength-1] = (uint)((inData[0] << 8) + inData[1]);
  431.                 else if(leftOver == 3)
  432.                         data[dataLength-1] = (uint)((inData[0] << 16) + (inData[1] << 8) + inData[2]);
  435.                 if(dataLength == 0)
  436.                         dataLength = 1;
  438.                 while(dataLength > 1 && data[dataLength-1] == 0)
  439.                         dataLength--;
  441.                 //Console.WriteLine("Len = " + dataLength);
  442.         }
  445.         //***********************************************************************
  446.         // Constructor (Default value provided by an array of unsigned integers)
  447.         //*********************************************************************
  449.         public BigInteger(uint[] inData)
  450.         {
  451.                 dataLength = inData.Length;
  453.                 if(dataLength > maxLength)
  454.                       throw(new ArithmeticException("Byte overflow in constructor."));
  456.                 data = new uint[maxLength];
  458.                 for(int i = dataLength - 1, j = 0; i >= 0; i--, j++)
  459.                         data[j] = inData[i];
  461.                 while(dataLength > 1 && data[dataLength-1] == 0)
  462.                         dataLength--;
  464.                 //Console.WriteLine("Len = " + dataLength);
  465.         }
  468.         //***********************************************************************
  469.         // Overloading of the typecast operator.
  470.         // For BigInteger bi = 10;
  471.         //***********************************************************************
  473.         public static implicit operator BigInteger(long value)
  474.         {
  475.                 return (new BigInteger(value));
  476.         }
  478.         public static implicit operator BigInteger(ulong value)
  479.         {
  480.                 return (new BigInteger(value));
  481.         }
  483.         public static implicit operator BigInteger(int value)
  484.         {
  485.                 return (new BigInteger((long)value));
  486.         }
  488.         public static implicit operator BigInteger(uint value)
  489.         {
  490.                 return (new BigInteger((ulong)value));
  491.         }
  494.         //***********************************************************************
  495.         // Overloading of addition operator
  496.         //***********************************************************************
  498.         public static BigInteger operator +(BigInteger bi1, BigInteger bi2)
  499.         {
  500.                 BigInteger result = new BigInteger();
  502.                 result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
  504.                 long carry = 0;
  505.                 for(int i = 0; i < result.dataLength; i++)
  506.                 {
  507.                         long sum = (long)bi1.data[i] + (long)bi2.data[i] + carry;
  508.                         carry  = sum >> 32;
  509.                         result.data[i] = (uint)(sum & 0xFFFFFFFF);
  510.                 }
  512.                 if(carry != 0 && result.dataLength < maxLength)
  513.                 {
  514.                         result.data[result.dataLength] = (uint)(carry);
  515.                         result.dataLength++;
  516.                 }
  518.                 while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
  519.                         result.dataLength--;
  522.                 // overflow check
  523.                 int lastPos = maxLength - 1;
  524.                 if((bi1.data[lastPos] & 0x80000000) == (bi2.data[lastPos] & 0x80000000) &&
  525.                    (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
  526.                 {
  527.                         throw (new ArithmeticException());
  528.                 }
  530.                 return result;
  531.         }
  534.         //***********************************************************************
  535.         // Overloading of the unary ++ operator
  536.         //***********************************************************************
  538.         public static BigInteger operator ++(BigInteger bi1)
  539.         {
  540.                 BigInteger result = new BigInteger(bi1);
  542.                 long val, carry = 1;
  543.                 int index = 0;
  545.                 while(carry != 0 && index < maxLength)
  546.                 {
  547.                         val = (long)(result.data[index]);
  548.                         val++;
  550.                         result.data[index] = (uint)(val & 0xFFFFFFFF);
  551.                         carry = val >> 32;
  553.                         index++;
  554.                 }
  556.                 if(index > result.dataLength)
  557.                         result.dataLength = index;
  558.                 else
  559.                 {
  560.                         while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
  561.                                 result.dataLength--;
  562.                 }
  564.                 // overflow check
  565.                 int lastPos = maxLength - 1;
  567.                 // overflow if initial value was +ve but ++ caused a sign
  568.                 // change to negative.
  570.                 if((bi1.data[lastPos] & 0x80000000) == 0 &&
  571.                    (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
  572.                 {
  573.                         throw (new ArithmeticException("Overflow in ++."));
  574.                 }
  575.                 return result;
  576.         }
  579.         //***********************************************************************
  580.         // Overloading of subtraction operator
  581.         //***********************************************************************
  583.         public static BigInteger operator -(BigInteger bi1, BigInteger bi2)
  584.         {
  585.                 BigInteger result = new BigInteger();
  587.                 result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
  589.                 long carryIn = 0;
  590.                 for(int i = 0; i < result.dataLength; i++)
  591.                 {
  592.                         long diff;
  594.                         diff = (long)bi1.data[i] - (long)bi2.data[i] - carryIn;
  595.                         result.data[i] = (uint)(diff & 0xFFFFFFFF);
  597.                         if(diff < 0)
  598.                                 carryIn = 1;
  599.                         else
  600.                                 carryIn = 0;
  601.                 }
  603.                 // roll over to negative
  604.                 if(carryIn != 0)
  605.                 {
  606.                         for(int i = result.dataLength; i < maxLength; i++)
  607.                                 result.data[i] = 0xFFFFFFFF;
  608.                         result.dataLength = maxLength;
  609.                 }
  611.                 // fixed in v1.03 to give correct datalength for a - (-b)
  612.                 while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
  613.                         result.dataLength--;
  615.                 // overflow check
  617.                 int lastPos = maxLength - 1;
  618.                 if((bi1.data[lastPos] & 0x80000000) != (bi2.data[lastPos] & 0x80000000) &&
  619.                    (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
  620.                 {
  621.                         throw (new ArithmeticException());
  622.                 }
  624.                 return result;
  625.         }
  628.         //***********************************************************************
  629.         // Overloading of the unary -- operator
  630.         //***********************************************************************
  632.         public static BigInteger operator --(BigInteger bi1)
  633.         {
  634.                 BigInteger result = new BigInteger(bi1);
  636.                 long val;
  637.                 bool carryIn = true;
  638.                 int index = 0;
  640.                 while(carryIn && index < maxLength)
  641.                 {
  642.                         val = (long)(result.data[index]);
  643.                         val--;
  645.                         result.data[index] = (uint)(val & 0xFFFFFFFF);
  647.                         if(val >= 0)
  648.                                 carryIn = false;
  650.                         index++;
  651.                 }
  653.                 if(index > result.dataLength)
  654.                         result.dataLength = index;
  656.                 while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
  657.                         result.dataLength--;
  659.                 // overflow check
  660.                 int lastPos = maxLength - 1;
  662.                 // overflow if initial value was -ve but -- caused a sign
  663.                 // change to positive.
  665.                 if((bi1.data[lastPos] & 0x80000000) != 0 &&
  666.                    (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
  667.                 {
  668.                         throw (new ArithmeticException("Underflow in --."));
  669.                 }
  671.                 return result;
  672.         }
  675.         //***********************************************************************
  676.         // Overloading of multiplication operator
  677.         //***********************************************************************
  679.         public static BigInteger operator *(BigInteger bi1, BigInteger bi2)
  680.         {
  681.                 int lastPos = maxLength-1;
  682.                 bool bi1Neg = false, bi2Neg = false;
  684.                 // take the absolute value of the inputs
  685.                 try
  686.                 {
  687.                         if((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
  688.                         {
  689.                                 bi1Neg = true; bi1 = -bi1;
  690.                         }
  691.                         if((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
  692.                         {
  693.                                 bi2Neg = true; bi2 = -bi2;
  694.                         }
  695.                 }
  696.                 catch(Exception) {}
  698.                 BigInteger result = new BigInteger();
  700.                 // multiply the absolute values
  701.                 try
  702.                 {
  703.                         for(int i = 0; i < bi1.dataLength; i++)
  704.                         {
  705.                                 if(bi1.data[i] == 0)    continue;
  707.                                 ulong mcarry = 0;
  708.                                 for(int j = 0, k = i; j < bi2.dataLength; j++, k++)
  709.                                 {
  710.                                         // k = i + j
  711.                                         ulong val = ((ulong)bi1.data[i] * (ulong)bi2.data[j]) +
  712.                                                      (ulong)result.data[k] + mcarry;
  714.                                         result.data[k] = (uint)(val & 0xFFFFFFFF);
  715.                 mcarry = (val >> 32);
  716.                                 }
  718.                                 if(mcarry != 0)
  719.                                         result.data[i+bi2.dataLength] = (uint)mcarry;
  720.                         }
  721.                 }
  722.                 catch(Exception)
  723.                 {
  724.                         throw(new ArithmeticException("Multiplication overflow."));
  725.                 }
  728.                 result.dataLength = bi1.dataLength + bi2.dataLength;
  729.                 if(result.dataLength > maxLength)
  730.                         result.dataLength = maxLength;
  732.                 while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
  733.                         result.dataLength--;
  735.                 // overflow check (result is -ve)
  736.                 if((result.data[lastPos] & 0x80000000) != 0)
  737.                 {
  738.                         if(bi1Neg != bi2Neg && result.data[lastPos] == 0x80000000)    // different sign
  739.                         {
  740.                                 // handle the special case where multiplication produces
  741.                                 // a max negative number in 2's complement.
  743.                                 if(result.dataLength == 1)
  744.                                         return result;
  745.                                 else
  746.                                 {
  747.                                         bool isMaxNeg = true;
  748.                                         for(int i = 0; i < result.dataLength - 1 && isMaxNeg; i++)
  749.                                         {
  750.                                                 if(result.data[i] != 0)
  751.                                                         isMaxNeg = false;
  752.                                         }
  754.                                         if(isMaxNeg)
  755.                                                 return result;
  756.                                 }
  757.                         }
  759.                         throw(new ArithmeticException("Multiplication overflow."));
  760.                 }
  762.                 // if input has different signs, then result is -ve
  763.                 if(bi1Neg != bi2Neg)
  764.                         return -result;
  766.                 return result;
  767.         }
  771.         //***********************************************************************
  772.         // Overloading of unary << operators
  773.         //***********************************************************************
  775.         public static BigInteger operator <<(BigInteger bi1, int shiftVal)
  776.         {
  777.                 BigInteger result = new BigInteger(bi1);
  778.                 result.dataLength = shiftLeft(result.data, shiftVal);
  780.                 return result;
  781.         }
  784.         // least significant bits at lower part of buffer
  786.         private static int shiftLeft(uint[] buffer, int shiftVal)
  787.         {
  788.                 int shiftAmount = 32;
  789.                 int bufLen = buffer.Length;
  791.                 while(bufLen > 1 && buffer[bufLen-1] == 0)
  792.                         bufLen--;
  794.                 for(int count = shiftVal; count > 0;)
  795.                 {
  796.                         if(count < shiftAmount)
  797.                                 shiftAmount = count;
  799.                         //Console.WriteLine("shiftAmount = {0}", shiftAmount);
  801.                         ulong carry = 0;
  802.                         for(int i = 0; i < bufLen; i++)
  803.                         {
  804.                                 ulong val = ((ulong)buffer[i]) << shiftAmount;
  805.                                 val |= carry;
  807.                                 buffer[i] = (uint)(val & 0xFFFFFFFF);
  808.                                 carry = val >> 32;
  809.                         }
  811.                         if(carry != 0)
  812.                         {
  813.                                 if(bufLen + 1 <= buffer.Length)
  814.                                 {
  815.                                         buffer[bufLen] = (uint)carry;
  816.                                         bufLen++;
  817.                                 }
  818.                         }
  819.                         count -= shiftAmount;
  820.                 }
  821.                 return bufLen;
  822.         }
  825.         //***********************************************************************
  826.         // Overloading of unary >> operators
  827.         //***********************************************************************
  829.         public static BigInteger operator >>(BigInteger bi1, int shiftVal)
  830.         {
  831.                 BigInteger result = new BigInteger(bi1);
  832.                 result.dataLength = shiftRight(result.data, shiftVal);
  835.                 if((bi1.data[maxLength-1] & 0x80000000) != 0) // negative
  836.                 {
  837.                         for(int i = maxLength - 1; i >= result.dataLength; i--)
  838.                                 result.data[i] = 0xFFFFFFFF;
  840.                         uint mask = 0x80000000;
  841.                         for(int i = 0; i < 32; i++)
  842.                         {
  843.                                 if((result.data[result.dataLength-1] & mask) != 0)
  844.                                         break;
  846.                                 result.data[result.dataLength-1] |= mask;
  847.                                 mask >>= 1;
  848.                         }
  849.                         result.dataLength = maxLength;
  850.                 }
  852.                 return result;
  853.         }
  856.         private static int shiftRight(uint[] buffer, int shiftVal)
  857.         {
  858.                 int shiftAmount = 32;
  859.                 int invShift = 0;
  860.                 int bufLen = buffer.Length;
  862.                 while(bufLen > 1 && buffer[bufLen-1] == 0)
  863.                         bufLen--;
  865.                 //Console.WriteLine("bufLen = " + bufLen + " buffer.Length = " + buffer.Length);
  867.                 for(int count = shiftVal; count > 0;)
  868.                 {
  869.                         if(count < shiftAmount)
  870.                         {
  871.                                 shiftAmount = count;
  872.                                 invShift = 32 - shiftAmount;
  873.                         }
  875.                         //Console.WriteLine("shiftAmount = {0}", shiftAmount);
  877.                         ulong carry = 0;
  878.                         for(int i = bufLen - 1; i >= 0; i--)
  879.                         {
  880.                                 ulong val = ((ulong)buffer[i]) >> shiftAmount;
  881.                                 val |= carry;
  883.                                 carry = ((ulong)buffer[i]) << invShift;
  884.                                 buffer[i] = (uint)(val);
  885.                         }
  887.                         count -= shiftAmount;
  888.                 }
  890.                 while(bufLen > 1 && buffer[bufLen-1] == 0)
  891.                         bufLen--;
  893.                 return bufLen;
  894.         }
  897.         //***********************************************************************
  898.         // Overloading of the NOT operator (1's complement)
  899.         //***********************************************************************
  901.         public static BigInteger operator ~(BigInteger bi1)
  902.         {
  903.                 BigInteger result = new BigInteger(bi1);
  905.                 for(int i = 0; i < maxLength; i++)
  906.                         result.data[i] = (uint)(~(bi1.data[i]));
  908.                 result.dataLength = maxLength;
  910.                 while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
  911.                         result.dataLength--;
  913.                 return result;
  914.         }
  917.         //***********************************************************************
  918.         // Overloading of the NEGATE operator (2's complement)
  919.         //***********************************************************************
  921.         public static BigInteger operator -(BigInteger bi1)
  922.         {
  923.                 // handle neg of zero separately since it'll cause an overflow
  924.                 // if we proceed.
  926.                 if(bi1.dataLength == 1 && bi1.data[0] == 0)
  927.                         return (new BigInteger());
  929.                 BigInteger result = new BigInteger(bi1);
  931.                 // 1's complement
  932.                 for(int i = 0; i < maxLength; i++)
  933.                         result.data[i] = (uint)(~(bi1.data[i]));
  935.                 // add one to result of 1's complement
  936.                 long val, carry = 1;
  937.                 int index = 0;
  939.                 while(carry != 0 && index < maxLength)
  940.                 {
  941.                         val = (long)(result.data[index]);
  942.                         val++;
  944.                         result.data[index] = (uint)(val & 0xFFFFFFFF);
  945.                         carry = val >> 32;
  947.                         index++;
  948.                 }
  950.                 if((bi1.data[maxLength-1] & 0x80000000) == (result.data[maxLength-1] & 0x80000000))
  951.                         throw (new ArithmeticException("Overflow in negation.n"));
  953.                 result.dataLength = maxLength;
  955.                 while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
  956.                         result.dataLength--;
  957.                 return result;
  958.         }
  961.         //***********************************************************************
  962.         // Overloading of equality operator
  963.         //***********************************************************************
  965.         public static bool operator ==(BigInteger bi1, BigInteger bi2)
  966.         {
  967. if(Object.Equals(bi1, bi2))
  968. return true;
  969. else
  970. return bi1.Equals(bi2);
  971.         }
  974.         public static bool operator !=(BigInteger bi1, BigInteger bi2)
  975.         {
  976. if(Object.Equals(bi1, bi2))
  977. return false;
  978. else
  979. return !(bi1.Equals(bi2));
  980.         }
  983.         public override bool Equals(object o)
  984.         {
  985. if(o==null || !(o is BigInteger)) return false;
  986. BigInteger bi = (BigInteger)o;
  988.                 if(this.dataLength != bi.dataLength)
  989.                         return false;
  991.                 for(int i = 0; i < this.dataLength; i++)
  992.                 {
  993.                         if(this.data[i] != bi.data[i])
  994.                                 return false;
  995.                 }
  996.                 return true;
  997.         }
  1000.         public override int GetHashCode()
  1001.         {
  1002.                 return this.ToString().GetHashCode();
  1003.         }
  1006.         //***********************************************************************
  1007.         // Overloading of inequality operator
  1008.         //***********************************************************************
  1010.         public static bool operator >(BigInteger bi1, BigInteger bi2)
  1011.         {
  1012.          int pos = maxLength - 1;
  1014.          // bi1 is negative, bi2 is positive
  1015.          if((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
  1016.                  return false;
  1018.                 // bi1 is positive, bi2 is negative
  1019.          else if((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
  1020.                  return true;
  1022.                 // same sign
  1023.          int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
  1024.         for(pos = len - 1; pos >= 0 && bi1.data[pos] == bi2.data[pos]; pos--);
  1026.         if(pos >= 0)
  1027.         {
  1028.         if(bi1.data[pos] > bi2.data[pos])
  1029.         return true;
  1030.         return false;
  1031.         }
  1032.         return false;
  1033.         }
  1036.         public static bool operator <(BigInteger bi1, BigInteger bi2)
  1037.         {
  1038.          int pos = maxLength - 1;
  1040.          // bi1 is negative, bi2 is positive
  1041.          if((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
  1042.                  return true;
  1044.                 // bi1 is positive, bi2 is negative
  1045.          else if((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
  1046.                  return false;
  1048.          // same sign
  1049.          int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
  1050.         for(pos = len - 1; pos >= 0 && bi1.data[pos] == bi2.data[pos]; pos--);
  1052.         if(pos >= 0)
  1053.         {
  1054.         if(bi1.data[pos] < bi2.data[pos])
  1055.         return true;
  1056.         return false;
  1057.         }
  1058.         return false;
  1059.         }
  1062.         public static bool operator >=(BigInteger bi1, BigInteger bi2)
  1063.         {
  1064.                 return (bi1 == bi2 || bi1 > bi2);
  1065.         }
  1068.         public static bool operator <=(BigInteger bi1, BigInteger bi2)
  1069.         {
  1070.                 return (bi1 == bi2 || bi1 < bi2);
  1071.         }
  1074.         //***********************************************************************
  1075.         // Private function that supports the division of two numbers with
  1076.         // a divisor that has more than 1 digit.
  1077.         //
  1078.         // Algorithm taken from [1]
  1079.         //***********************************************************************
  1081.         private static void multiByteDivide(BigInteger bi1, BigInteger bi2,
  1082.                                             BigInteger outQuotient, BigInteger outRemainder)
  1083.         {
  1084.                 uint[] result = new uint[maxLength];
  1086.                 int remainderLen = bi1.dataLength + 1;
  1087.                 uint[] remainder = new uint[remainderLen];
  1089.                 uint mask = 0x80000000;
  1090.                 uint val = bi2.data[bi2.dataLength - 1];
  1091.                 int shift = 0, resultPos = 0;
  1093.                 while(mask != 0 && (val & mask) == 0)
  1094.                 {
  1095.                         shift++; mask >>= 1;
  1096.                 }
  1098.                 //Console.WriteLine("shift = {0}", shift);
  1099.                 //Console.WriteLine("Before bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength, bi2.dataLength);
  1101.                 for(int i = 0; i < bi1.dataLength; i++)
  1102.                         remainder[i] = bi1.data[i];
  1103.                 shiftLeft(remainder, shift);
  1104.                 bi2 = bi2 << shift;
  1106.                 /*
  1107.                 Console.WriteLine("bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength, bi2.dataLength);
  1108.                 Console.WriteLine("dividend = " + bi1 + "ndivisor = " + bi2);
  1109.                 for(int q = remainderLen - 1; q >= 0; q--)
  1110.                         Console.Write("{0:x2}", remainder[q]);
  1111.                 Console.WriteLine();
  1112.                 */
  1114.                 int j = remainderLen - bi2.dataLength;
  1115.                 int pos = remainderLen - 1;
  1117.                 ulong firstDivisorByte = bi2.data[bi2.dataLength-1];
  1118.                 ulong secondDivisorByte = bi2.data[bi2.dataLength-2];
  1120.                 int divisorLen = bi2.dataLength + 1;
  1121.                 uint[] dividendPart = new uint[divisorLen];
  1123.                 while(j > 0)
  1124.                 {
  1125.                         ulong dividend = ((ulong)remainder[pos] << 32) + (ulong)remainder[pos-1];
  1126.                         //Console.WriteLine("dividend = {0}", dividend);
  1128.                         ulong q_hat = dividend / firstDivisorByte;
  1129.                         ulong r_hat = dividend % firstDivisorByte;
  1131.                         //Console.WriteLine("q_hat = {0:X}, r_hat = {1:X}", q_hat, r_hat);
  1133.                         bool done = false;
  1134.                         while(!done)
  1135.                         {
  1136.                                 done = true;
  1138.                                 if(q_hat == 0x100000000 ||
  1139.                                    (q_hat * secondDivisorByte) > ((r_hat << 32) + remainder[pos-2]))
  1140.                                 {
  1141.                                         q_hat--;
  1142.                                         r_hat += firstDivisorByte;
  1144.                                         if(r_hat < 0x100000000)
  1145.                                                 done = false;
  1146.                                 }
  1147.                         }
  1149.                         for(int h = 0; h < divisorLen; h++)
  1150.                                 dividendPart[h] = remainder[pos-h];
  1152.                         BigInteger kk = new BigInteger(dividendPart);
  1153.                         BigInteger ss = bi2 * (long)q_hat;
  1155.                         //Console.WriteLine("ss before = " + ss);
  1156.                         while(ss > kk)
  1157.                         {
  1158.                                 q_hat--;
  1159.                                 ss -= bi2;
  1160.                                 //Console.WriteLine(ss);
  1161.                         }
  1162.                         BigInteger yy = kk - ss;
  1164.                         //Console.WriteLine("ss = " + ss);
  1165.                         //Console.WriteLine("kk = " + kk);
  1166.                         //Console.WriteLine("yy = " + yy);
  1168.                         for(int h = 0; h < divisorLen; h++)
  1169.                                 remainder[pos-h] = yy.data[bi2.dataLength-h];
  1171.                         /*
  1172.                         Console.WriteLine("dividend = ");
  1173.                         for(int q = remainderLen - 1; q >= 0; q--)
  1174.                                 Console.Write("{0:x2}", remainder[q]);
  1175.                         Console.WriteLine("n************ q_hat = {0:X}n", q_hat);
  1176.                         */
  1178.                         result[resultPos++] = (uint)q_hat;
  1180.                         pos--;
  1181.                         j--;
  1182.                 }
  1184.                 outQuotient.dataLength = resultPos;
  1185.                 int y = 0;
  1186.                 for(int x = outQuotient.dataLength - 1; x >= 0; x--, y++)
  1187.                         outQuotient.data[y] = result[x];
  1188.                 for(; y < maxLength; y++)
  1189.                         outQuotient.data[y] = 0;
  1191.                 while(outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength-1] == 0)
  1192.                         outQuotient.dataLength--;
  1194.                 if(outQuotient.dataLength == 0)
  1195.                         outQuotient.dataLength = 1;
  1197.                 outRemainder.dataLength = shiftRight(remainder, shift);
  1199.                 for(y = 0; y < outRemainder.dataLength; y++)
  1200.                         outRemainder.data[y] = remainder[y];
  1201.                 for(; y < maxLength; y++)
  1202.                         outRemainder.data[y] = 0;
  1203.         }
  1206.         //***********************************************************************
  1207.         // Private function that supports the division of two numbers with
  1208.         // a divisor that has only 1 digit.
  1209.         //***********************************************************************
  1211.         private static void singleByteDivide(BigInteger bi1, BigInteger bi2,
  1212.                                              BigInteger outQuotient, BigInteger outRemainder)
  1213.         {
  1214.                 uint[] result = new uint[maxLength];
  1215.                 int resultPos = 0;
  1217.                 // copy dividend to reminder
  1218.                 for(int i = 0; i < maxLength; i++)
  1219.                         outRemainder.data[i] = bi1.data[i];
  1220.                 outRemainder.dataLength = bi1.dataLength;
  1222.                 while(outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength-1] == 0)
  1223.                         outRemainder.dataLength--;
  1225.                 ulong divisor = (ulong)bi2.data[0];
  1226.                 int pos = outRemainder.dataLength - 1;
  1227.                 ulong dividend = (ulong)outRemainder.data[pos];
  1229.                 //Console.WriteLine("divisor = " + divisor + " dividend = " + dividend);
  1230.                 //Console.WriteLine("divisor = " + bi2 + "ndividend = " + bi1);
  1232.                 if(dividend >= divisor)
  1233.                 {
  1234.                         ulong quotient = dividend / divisor;
  1235.                         result[resultPos++] = (uint)quotient;
  1237.                         outRemainder.data[pos] = (uint)(dividend % divisor);
  1238.                 }
  1239.                 pos--;
  1241.                 while(pos >= 0)
  1242.                 {
  1243.                         //Console.WriteLine(pos);
  1245.                         dividend = ((ulong)outRemainder.data[pos+1] << 32) + (ulong)outRemainder.data[pos];
  1246.                         ulong quotient = dividend / divisor;
  1247.                         result[resultPos++] = (uint)quotient;
  1249.                         outRemainder.data[pos+1] = 0;
  1250.                         outRemainder.data[pos--] = (uint)(dividend % divisor);
  1251.                         //Console.WriteLine(">>>> " + bi1);
  1252.                 }
  1254.                 outQuotient.dataLength = resultPos;
  1255.                 int j = 0;
  1256.                 for(int i = outQuotient.dataLength - 1; i >= 0; i--, j++)
  1257.                         outQuotient.data[j] = result[i];
  1258.                 for(; j < maxLength; j++)
  1259.                         outQuotient.data[j] = 0;
  1261.                 while(outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength-1] == 0)
  1262.                         outQuotient.dataLength--;
  1264.                 if(outQuotient.dataLength == 0)
  1265.                         outQuotient.dataLength = 1;
  1267.                 while(outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength-1] == 0)
  1268.                         outRemainder.dataLength--;
  1269.         }
  1272.         //***********************************************************************
  1273.         // Overloading of division operator
  1274.         //***********************************************************************
  1276.         public static BigInteger operator /(BigInteger bi1, BigInteger bi2)
  1277.         {
  1278.                 BigInteger quotient = new BigInteger();
  1279.                 BigInteger remainder = new BigInteger();
  1281.                 int lastPos = maxLength-1;
  1282.                 bool divisorNeg = false, dividendNeg = false;
  1284.                 if((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
  1285.                 {
  1286.                         bi1 = -bi1;
  1287.                         dividendNeg = true;
  1288.                 }
  1289.                 if((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
  1290.                 {
  1291.                         bi2 = -bi2;
  1292.                         divisorNeg = true;
  1293.                 }
  1295.                 if(bi1 < bi2)
  1296.                 {
  1297.                         return quotient;
  1298.                 }
  1300.                 else
  1301.                 {
  1302.                         if(bi2.dataLength == 1)
  1303.                                 singleByteDivide(bi1, bi2, quotient, remainder);
  1304.                         else
  1305.                                 multiByteDivide(bi1, bi2, quotient, remainder);
  1307.                         if(dividendNeg != divisorNeg)
  1308.                                 return -quotient;
  1310.                         return quotient;
  1311.                 }
  1312.         }
  1315.         //***********************************************************************
  1316.         // Overloading of modulus operator
  1317.         //***********************************************************************
  1319.         public static BigInteger operator %(BigInteger bi1, BigInteger bi2)
  1320.         {
  1321.                 BigInteger quotient = new BigInteger();
  1322.                 BigInteger remainder = new BigInteger(bi1);
  1324.                 int lastPos = maxLength-1;
  1325.                 bool dividendNeg = false;
  1327.                 if((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
  1328.                 {
  1329.                         bi1 = -bi1;
  1330.                         dividendNeg = true;
  1331.                 }
  1332.                 if((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
  1333.                         bi2 = -bi2;
  1335.                 if(bi1 < bi2)
  1336.                 {
  1337.                         return remainder;
  1338.                 }
  1340.                 else
  1341.                 {
  1342.                         if(bi2.dataLength == 1)
  1343.                                 singleByteDivide(bi1, bi2, quotient, remainder);
  1344.                         else
  1345.                                 multiByteDivide(bi1, bi2, quotient, remainder);
  1347.                         if(dividendNeg)
  1348.                                 return -remainder;
  1350.                         return remainder;
  1351.                 }
  1352.         }
  1355.         //***********************************************************************
  1356.         // Overloading of bitwise AND operator
  1357.         //***********************************************************************
  1359.         public static BigInteger operator &(BigInteger bi1, BigInteger bi2)
  1360.         {
  1361.                 BigInteger result = new BigInteger();
  1363.                 int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
  1365.                 for(int i = 0; i < len; i++)
  1366.                 {
  1367.                         uint sum = (uint)(bi1.data[i] & bi2.data[i]);
  1368.                         result.data[i] = sum;
  1369.                 }
  1371.                 result.dataLength = maxLength;
  1373.                 while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
  1374.                         result.dataLength--;
  1376.                 return result;
  1377.         }
  1380.         //***********************************************************************
  1381.         // Overloading of bitwise OR operator
  1382.         //***********************************************************************
  1384.         public static BigInteger operator |(BigInteger bi1, BigInteger bi2)
  1385.         {
  1386.                 BigInteger result = new BigInteger();
  1388.                 int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
  1390.                 for(int i = 0; i < len; i++)
  1391.                 {
  1392.                         uint sum = (uint)(bi1.data[i] | bi2.data[i]);
  1393.                         result.data[i] = sum;
  1394.                 }
  1396.                 result.dataLength = maxLength;
  1398.                 while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
  1399.                         result.dataLength--;
  1401.                 return result;
  1402.         }
  1405.         //***********************************************************************
  1406.         // Overloading of bitwise XOR operator
  1407.         //***********************************************************************
  1409.         public static BigInteger operator ^(BigInteger bi1, BigInteger bi2)
  1410.         {
  1411.                 BigInteger result = new BigInteger();
  1413.                 int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
  1415.                 for(int i = 0; i < len; i++)
  1416.                 {
  1417.                         uint sum = (uint)(bi1.data[i] ^ bi2.data[i]);
  1418.                         result.data[i] = sum;
  1419.                 }
  1421.                 result.dataLength = maxLength;
  1423.                 while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
  1424.                         result.dataLength--;
  1426.                 return result;
  1427.         }
  1430.         //***********************************************************************
  1431.         // Returns max(this, bi)
  1432.         //***********************************************************************
  1434.         public BigInteger max(BigInteger bi)
  1435.         {
  1436.                 if(this > bi)
  1437.                         return (new BigInteger(this));
  1438.                 else
  1439.                         return (new BigInteger(bi));
  1440.         }
  1443.         //***********************************************************************
  1444.         // Returns min(this, bi)
  1445.         //***********************************************************************
  1447.         public BigInteger min(BigInteger bi)
  1448.         {
  1449.                 if(this < bi)
  1450.                         return (new BigInteger(this));
  1451.                 else
  1452.                         return (new BigInteger(bi));
  1454.         }
  1457.         //***********************************************************************
  1458.         // Returns the absolute value
  1459.         //***********************************************************************
  1461.         public BigInteger abs()
  1462.         {
  1463.                 if((this.data[maxLength - 1] & 0x80000000) != 0)
  1464.                         return (-this);
  1465.                 else
  1466.                         return (new BigInteger(this));
  1467.         }
  1470.         //***********************************************************************
  1471.         // Returns a string representing the BigInteger in base 10.
  1472.         //***********************************************************************
  1474.         public override string ToString()
  1475.         {
  1476.                 return ToString(10);
  1477.         }
  1480.         //***********************************************************************
  1481.         // Returns a string representing the BigInteger in sign-and-magnitude
  1482.         // format in the specified radix.
  1483.         //
  1484.         // Example
  1485.         // -------
  1486.         // If the value of BigInteger is -255 in base 10, then
  1487.         // ToString(16) returns "-FF"
  1488.         //
  1489.         //***********************************************************************
  1491.         public string ToString(int radix)
  1492.         {
  1493.                 if(radix < 2 || radix > 36)
  1494.                         throw (new ArgumentException("Radix must be >= 2 and <= 36"));
  1496.                 string charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  1497.                 string result = "";
  1499.                 BigInteger a = this;
  1501.                 bool negative = false;
  1502.                 if((a.data[maxLength-1] & 0x80000000) != 0)
  1503.                 {
  1504.                         negative = true;
  1505.                         try
  1506.                         {
  1507.                                 a = -a;
  1508.                         }
  1509.                         catch(Exception) {}
  1510.                 }
  1512.                 BigInteger quotient = new BigInteger();
  1513.                 BigInteger remainder = new BigInteger();
  1514.                 BigInteger biRadix = new BigInteger(radix);
  1516.                 if(a.dataLength == 1 && a.data[0] == 0)
  1517.                         result = "0";
  1518.                 else
  1519.                 {
  1520.                         while(a.dataLength > 1 || (a.dataLength == 1 && a.data[0] != 0))
  1521.                         {
  1522.                                 singleByteDivide(a, biRadix, quotient, remainder);
  1524.                                 if(remainder.data[0] < 10)
  1525.                                         result = remainder.data[0] + result;
  1526.                                 else
  1527.                                         result = charSet[(int)remainder.data[0] - 10] + result;
  1529.                                 a = quotient;
  1530.                         }
  1531.                         if(negative)
  1532.                                 result = "-" + result;
  1533.                 }
  1535.                 return result;
  1536.         }
  1539.         //***********************************************************************
  1540.         // Returns a hex string showing the contains of the BigInteger
  1541.         //
  1542.         // Examples
  1543.         // -------
  1544.         // 1) If the value of BigInteger is 255 in base 10, then
  1545.         //    ToHexString() returns "FF"
  1546.         //
  1547.         // 2) If the value of BigInteger is -255 in base 10, then
  1548.         //    ToHexString() returns ".....FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01",
  1549.         //    which is the 2's complement representation of -255.
  1550.         //
  1551.         //***********************************************************************
  1553.         public string ToHexString()
  1554.         {
  1555.                 string result = data[dataLength - 1].ToString("X");
  1557.                 for(int i = dataLength - 2; i >= 0; i--)
  1558.                 {
  1559.                         result += data[i].ToString("X8");
  1560.                 }
  1562.                 return result;
  1563.         }
  1567.         //***********************************************************************
  1568.         // Modulo Exponentiation
  1569.         //***********************************************************************
  1571.         public BigInteger modPow(BigInteger exp, BigInteger n)
  1572.         {
  1573.                 if((exp.data[maxLength-1] & 0x80000000) != 0)
  1574.                         throw (new ArithmeticException("Positive exponents only."));
  1576.                 BigInteger resultNum = 1;
  1577.         BigInteger tempNum;
  1578.         bool thisNegative = false;
  1580.         if((this.data[maxLength-1] & 0x80000000) != 0)   // negative this
  1581.         {
  1582.                 tempNum = -this % n;
  1583.                 thisNegative = true;
  1584.         }
  1585.         else
  1586.                 tempNum = this % n;  // ensures (tempNum * tempNum) < b^(2k)
  1588.         if((n.data[maxLength-1] & 0x80000000) != 0)   // negative n
  1589.                 n = -n;
  1591.                 // calculate constant = b^(2k) / m
  1592.                 BigInteger constant = new BigInteger();
  1594.                 int i = n.dataLength << 1;
  1595.                 constant.data[i] = 0x00000001;
  1596.                 constant.dataLength = i + 1;
  1598.                 constant = constant / n;
  1599.                 int totalBits = exp.bitCount();
  1600.                 int count = 0;
  1602.                 // perform squaring and multiply exponentiation
  1603.                 for(int pos = 0; pos < exp.dataLength; pos++)
  1604.                 {
  1605.                         uint mask = 0x01;
  1606.                         //Console.WriteLine("pos = " + pos);
  1608.                         for(int index = 0; index < 32; index++)
  1609.                         {
  1610.                                 if((exp.data[pos] & mask) != 0)
  1611.                                         resultNum = BarrettReduction(resultNum * tempNum, n, constant);
  1613.                                 mask <<= 1;
  1615.                                 tempNum = BarrettReduction(tempNum * tempNum, n, constant);
  1618.                                 if(tempNum.dataLength == 1 && tempNum.data[0] == 1)
  1619.                                 {
  1620.                                         if(thisNegative && (exp.data[0] & 0x1) != 0)    //odd exp
  1621.                                                 return -resultNum;
  1622.                                         return resultNum;
  1623.                                 }
  1624.                                 count++;
  1625.                                 if(count == totalBits)
  1626.                                         break;
  1627.                         }
  1628.                 }
  1630.                 if(thisNegative && (exp.data[0] & 0x1) != 0)    //odd exp
  1631.                         return -resultNum;
  1633.         return resultNum;
  1634.         }
  1638.         //***********************************************************************
  1639.         // Fast calculation of modular reduction using Barrett's reduction.
  1640.         // Requires x < b^(2k), where b is the base.  In this case, base is
  1641.         // 2^32 (uint).
  1642.         //
  1643.         // Reference [4]
  1644.         //***********************************************************************
  1646.         private BigInteger BarrettReduction(BigInteger x, BigInteger n, BigInteger constant)
  1647.         {
  1648.                 int k = n.dataLength,
  1649.                     kPlusOne = k+1,
  1650.                     kMinusOne = k-1;
  1652.                 BigInteger q1 = new BigInteger();
  1654.                 // q1 = x / b^(k-1)
  1655.                 for(int i = kMinusOne, j = 0; i < x.dataLength; i++, j++)
  1656.                         q1.data[j] = x.data[i];
  1657.                 q1.dataLength = x.dataLength - kMinusOne;
  1658.                 if(q1.dataLength <= 0)
  1659.                         q1.dataLength = 1;
  1662.                 BigInteger q2 = q1 * constant;
  1663.                 BigInteger q3 = new BigInteger();
  1665.                 // q3 = q2 / b^(k+1)
  1666.                 for(int i = kPlusOne, j = 0; i < q2.dataLength; i++, j++)
  1667.                         q3.data[j] = q2.data[i];
  1668.                 q3.dataLength = q2.dataLength - kPlusOne;
  1669.                 if(q3.dataLength <= 0)
  1670.                         q3.dataLength = 1;
  1673.                 // r1 = x mod b^(k+1)
  1674.                 // i.e. keep the lowest (k+1) words
  1675.                 BigInteger r1 = new BigInteger();
  1676.                 int lengthToCopy = (x.dataLength > kPlusOne) ? kPlusOne : x.dataLength;
  1677.                 for(int i = 0; i < lengthToCopy; i++)
  1678.                         r1.data[i] = x.data[i];
  1679.                 r1.dataLength = lengthToCopy;
  1682.                 // r2 = (q3 * n) mod b^(k+1)
  1683.                 // partial multiplication of q3 and n
  1685.                 BigInteger r2 = new BigInteger();
  1686.                 for(int i = 0; i < q3.dataLength; i++)
  1687.                 {
  1688.                         if(q3.data[i] == 0)     continue;
  1690.                         ulong mcarry = 0;
  1691.                         int t = i;
  1692.                         for(int j = 0; j < n.dataLength && t < kPlusOne; j++, t++)
  1693.                         {
  1694.                                 // t = i + j
  1695.                                 ulong val = ((ulong)q3.data[i] * (ulong)n.data[j]) +
  1696.                                              (ulong)r2.data[t] + mcarry;
  1698.                                 r2.data[t] = (uint)(val & 0xFFFFFFFF);
  1699.                                 mcarry = (val >> 32);
  1700.                         }
  1702.                         if(t < kPlusOne)
  1703.                                 r2.data[t] = (uint)mcarry;
  1704.                 }
  1705.                 r2.dataLength = kPlusOne;
  1706.                 while(r2.dataLength > 1 && r2.data[r2.dataLength-1] == 0)
  1707.                         r2.dataLength--;
  1709.                 r1 -= r2;
  1710.                 if((r1.data[maxLength-1] & 0x80000000) != 0)        // negative
  1711.                 {
  1712.                         BigInteger val = new BigInteger();
  1713.                         val.data[kPlusOne] = 0x00000001;
  1714.                         val.dataLength = kPlusOne + 1;
  1715.                         r1 += val;
  1716.                 }
  1718.                 while(r1 >= n)
  1719.                         r1 -= n;
  1721.                 return r1;
  1722.         }
  1725.         //***********************************************************************
  1726.         // Returns gcd(this, bi)
  1727.         //***********************************************************************
  1729.         public BigInteger gcd(BigInteger bi)
  1730.         {
  1731.                 BigInteger x;
  1732.                 BigInteger y;
  1734.                 if((data[maxLength-1] & 0x80000000) != 0)     // negative
  1735.                         x = -this;
  1736.                 else
  1737.                         x = this;
  1739.                 if((bi.data[maxLength-1] & 0x80000000) != 0)     // negative
  1740.                         y = -bi;
  1741.                 else
  1742.                         y = bi;
  1744.         BigInteger g = y;
  1746.         while(x.dataLength > 1 || (x.dataLength == 1 && x.data[0] != 0))
  1747.         {
  1748.         g = x;
  1749.         x = y % x;
  1750.         y = g;
  1751.          }
  1753.         return g;
  1754.         }
  1757.         //***********************************************************************
  1758.         // Populates "this" with the specified amount of random bits
  1759.         //***********************************************************************
  1761.         public void genRandomBits(int bits, Random rand)
  1762.         {
  1763.         int dwords = bits >> 5;
  1764.         int remBits = bits & 0x1F;
  1766.         if(remBits != 0)
  1767.         dwords++;
  1769.         if(dwords > maxLength)
  1770.         throw (new ArithmeticException("Number of required bits > maxLength."));
  1772.         for(int i = 0; i < dwords; i++)
  1773.         data[i] = (uint)(rand.NextDouble() * 0x100000000);
  1775.         for(int i = dwords; i < maxLength; i++)
  1776.         data[i] = 0;
  1778.         if(remBits != 0)
  1779.         {
  1780.         uint mask = (uint)(0x01 << (remBits-1));
  1781.         data[dwords-1] |= mask;
  1783.         mask = (uint)(0xFFFFFFFF >> (32 - remBits));
  1784.         data[dwords-1] &= mask;
  1785.         }
  1786.         else
  1787.         data[dwords-1] |= 0x80000000;
  1789.         dataLength = dwords;
  1791.         if(dataLength == 0)
  1792.                 dataLength = 1;
  1793.         }
  1796.         //***********************************************************************
  1797.         // Returns the position of the most significant bit in the BigInteger.
  1798.         //
  1799.         // Eg.  The result is 0, if the value of BigInteger is 0...0000 0000
  1800.         //      The result is 1, if the value of BigInteger is 0...0000 0001
  1801.         //      The result is 2, if the value of BigInteger is 0...0000 0010
  1802.         //      The result is 2, if the value of BigInteger is 0...0000 0011
  1803.         //
  1804.         //***********************************************************************
  1806.         public int bitCount()
  1807.         {
  1808.                 while(dataLength > 1 && data[dataLength-1] == 0)
  1809.                         dataLength--;
  1811.                uint value = data[dataLength - 1];
  1812.                uint mask = 0x80000000;
  1813.                int bits = 32;
  1815.                while(bits > 0 && (value & mask) == 0)
  1816.                {
  1817.                         bits--;
  1818.                         mask >>= 1;
  1819.                }
  1820.                bits += ((dataLength - 1) << 5);
  1822.                return bits;
  1823.         }
  1826.         //***********************************************************************
  1827.         // Probabilistic prime test based on Fermat's little theorem
  1828.         //
  1829.         // for any a < p (p does not divide a) if
  1830.         //      a^(p-1) mod p != 1 then p is not prime.
  1831.         //
  1832.         // Otherwise, p is probably prime (pseudoprime to the chosen base).
  1833.         //
  1834.         // Returns
  1835.         // -------
  1836.         // True if "this" is a pseudoprime to randomly chosen
  1837.         // bases.  The number of chosen bases is given by the "confidence"
  1838.         // parameter.
  1839.         //
  1840.         // False if "this" is definitely NOT prime.
  1841.         //
  1842.         // Note - this method is fast but fails for Carmichael numbers except
  1843.         // when the randomly chosen base is a factor of the number.
  1844.         //
  1845.         //***********************************************************************
  1847.         public bool FermatLittleTest(int confidence)
  1848.         {
  1849.                 BigInteger thisVal;
  1850.                 if((this.data[maxLength-1] & 0x80000000) != 0)        // negative
  1851.                         thisVal = -this;
  1852.                 else
  1853.                         thisVal = this;
  1855.                 if(thisVal.dataLength == 1)
  1856.                 {
  1857.                         // test small numbers
  1858.                         if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
  1859.                                 return false;
  1860.                         else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
  1861.                                 return true;
  1862.                 }
  1864.                 if((thisVal.data[0] & 0x1) == 0)     // even numbers
  1865.                         return false;
  1867.         int bits = thisVal.bitCount();
  1868.         BigInteger a = new BigInteger();
  1869.         BigInteger p_sub1 = thisVal - (new BigInteger(1));
  1870.         Random rand = new Random();
  1872.         for(int round = 0; round < confidence; round++)
  1873.         {
  1874.         bool done = false;
  1876.         while(!done) // generate a < n
  1877.         {
  1878.         int testBits = 0;
  1880.         // make sure "a" has at least 2 bits
  1881.         while(testBits < 2)
  1882.         testBits = (int)(rand.NextDouble() * bits);
  1884.         a.genRandomBits(testBits, rand);
  1886.         int byteLen = a.dataLength;
  1888.                                 // make sure "a" is not 0
  1889.         if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
  1890.                                         done = true;
  1891.         }
  1893.                         // check whether a factor exists (fix for version 1.03)
  1894.         BigInteger gcdTest = a.gcd(thisVal);
  1895.                         if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
  1896.                                 return false;
  1898.         // calculate a^(p-1) mod p
  1899.         BigInteger expResult = a.modPow(p_sub1, thisVal);
  1901.         int resultLen = expResult.dataLength;
  1903.                         // is NOT prime is a^(p-1) mod p != 1
  1905.         if(resultLen > 1 || (resultLen == 1 && expResult.data[0] != 1))
  1906.         {
  1907.                 //Console.WriteLine("a = " + a.ToString());
  1908.         return false;
  1909.                         }
  1910.         }
  1912.         return true;
  1913.         }
  1916.         //***********************************************************************
  1917.         // Probabilistic prime test based on Rabin-Miller's
  1918.         //
  1919.         // for any p > 0 with p - 1 = 2^s * t
  1920.         //
  1921.         // p is probably prime (strong pseudoprime) if for any a < p,
  1922.         // 1) a^t mod p = 1 or
  1923.         // 2) a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
  1924.         //
  1925.         // Otherwise, p is composite.
  1926.         //
  1927.         // Returns
  1928.         // -------
  1929.         // True if "this" is a strong pseudoprime to randomly chosen
  1930.         // bases.  The number of chosen bases is given by the "confidence"
  1931.         // parameter.
  1932.         //
  1933.         // False if "this" is definitely NOT prime.
  1934.         //
  1935.         //***********************************************************************
  1937.         public bool RabinMillerTest(int confidence)
  1938.         {
  1939.                 BigInteger thisVal;
  1940.                 if((this.data[maxLength-1] & 0x80000000) != 0)        // negative
  1941.                         thisVal = -this;
  1942.                 else
  1943.                         thisVal = this;
  1945.                 if(thisVal.dataLength == 1)
  1946.                 {
  1947.                         // test small numbers
  1948.                         if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
  1949.                                 return false;
  1950.                         else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
  1951.                                 return true;
  1952.                 }
  1954.                 if((thisVal.data[0] & 0x1) == 0)     // even numbers
  1955.                         return false;
  1958.                 // calculate values of s and t
  1959.                 BigInteger p_sub1 = thisVal - (new BigInteger(1));
  1960.                 int s = 0;
  1962.                 for(int index = 0; index < p_sub1.dataLength; index++)
  1963.                 {
  1964.                         uint mask = 0x01;
  1966.                         for(int i = 0; i < 32; i++)
  1967.                         {
  1968.                                 if((p_sub1.data[index] & mask) != 0)
  1969.                                 {
  1970.                                         index = p_sub1.dataLength;      // to break the outer loop
  1971.                                         break;
  1972.                                 }
  1973.                                 mask <<= 1;
  1974.                                 s++;
  1975.                         }
  1976.                 }
  1978.                 BigInteger t = p_sub1 >> s;
  1980.         int bits = thisVal.bitCount();
  1981.         BigInteger a = new BigInteger();
  1982.         Random rand = new Random();
  1984.         for(int round = 0; round < confidence; round++)
  1985.         {
  1986.         bool done = false;
  1988.         while(!done) // generate a < n
  1989.         {
  1990.         int testBits = 0;
  1992.         // make sure "a" has at least 2 bits
  1993.         while(testBits < 2)
  1994.         testBits = (int)(rand.NextDouble() * bits);
  1996.         a.genRandomBits(testBits, rand);
  1998.         int byteLen = a.dataLength;
  2000.                                 // make sure "a" is not 0
  2001.         if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
  2002.         done = true;
  2003.         }
  2005.                         // check whether a factor exists (fix for version 1.03)
  2006.         BigInteger gcdTest = a.gcd(thisVal);
  2007.                         if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
  2008.                                 return false;
  2010.                         BigInteger b = a.modPow(t, thisVal);
  2012.                         /*
  2013.                         Console.WriteLine("a = " + a.ToString(10));
  2014.                         Console.WriteLine("b = " + b.ToString(10));
  2015.                         Console.WriteLine("t = " + t.ToString(10));
  2016.                         Console.WriteLine("s = " + s);
  2017.                         */
  2019.                         bool result = false;
  2021.                         if(b.dataLength == 1 && b.data[0] == 1)         // a^t mod p = 1
  2022.                                 result = true;
  2024.                         for(int j = 0; result == false && j < s; j++)
  2025.                         {
  2026.                                 if(b == p_sub1)         // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
  2027.                                 {
  2028.                                         result = true;
  2029.                                         break;
  2030.                                 }
  2032.                                 b = (b * b) % thisVal;
  2033.                         }
  2035.                         if(result == false)
  2036.                                 return false;
  2037.                 }
  2038.         return true;
  2039.         }
  2042.         //***********************************************************************
  2043.         // Probabilistic prime test based on Solovay-Strassen (Euler Criterion)
  2044.         //
  2045.         // p is probably prime if for any a < p (a is not multiple of p),
  2046.         // a^((p-1)/2) mod p = J(a, p)
  2047.         //
  2048.         // where J is the Jacobi symbol.
  2049.         //
  2050.         // Otherwise, p is composite.
  2051.         //
  2052.         // Returns
  2053.         // -------
  2054.         // True if "this" is a Euler pseudoprime to randomly chosen
  2055.         // bases.  The number of chosen bases is given by the "confidence"
  2056.         // parameter.
  2057.         //
  2058.         // False if "this" is definitely NOT prime.
  2059.         //
  2060.         //***********************************************************************
  2062.         public bool SolovayStrassenTest(int confidence)
  2063.         {
  2064.                 BigInteger thisVal;
  2065.                 if((this.data[maxLength-1] & 0x80000000) != 0)        // negative
  2066.                         thisVal = -this;
  2067.                 else
  2068.                         thisVal = this;
  2070.                 if(thisVal.dataLength == 1)
  2071.                 {
  2072.                         // test small numbers
  2073.                         if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
  2074.                                 return false;
  2075.                         else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
  2076.                                 return true;
  2077.                 }
  2079.                 if((thisVal.data[0] & 0x1) == 0)     // even numbers
  2080.                         return false;
  2083.         int bits = thisVal.bitCount();
  2084.         BigInteger a = new BigInteger();
  2085.         BigInteger p_sub1 = thisVal - 1;
  2086.         BigInteger p_sub1_shift = p_sub1 >> 1;
  2088.         Random rand = new Random();
  2090.         for(int round = 0; round < confidence; round++)
  2091.         {
  2092.         bool done = false;
  2094.         while(!done) // generate a < n
  2095.         {
  2096.         int testBits = 0;
  2098.         // make sure "a" has at least 2 bits
  2099.         while(testBits < 2)
  2100.         testBits = (int)(rand.NextDouble() * bits);
  2102.         a.genRandomBits(testBits, rand);
  2104.         int byteLen = a.dataLength;
  2106.                                 // make sure "a" is not 0
  2107.         if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
  2108.         done = true;
  2109.         }
  2111.                         // check whether a factor exists (fix for version 1.03)
  2112.         BigInteger gcdTest = a.gcd(thisVal);
  2113.                         if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
  2114.                                 return false;
  2116.         // calculate a^((p-1)/2) mod p
  2118.         BigInteger expResult = a.modPow(p_sub1_shift, thisVal);
  2119.         if(expResult == p_sub1)
  2120.                 expResult = -1;
  2122.                         // calculate Jacobi symbol
  2123.                         BigInteger jacob = Jacobi(a, thisVal);
  2125.                         //Console.WriteLine("a = " + a.ToString(10) + " b = " + thisVal.ToString(10));
  2126.                         //Console.WriteLine("expResult = " + expResult.ToString(10) + " Jacob = " + jacob.ToString(10));
  2128.                         // if they are different then it is not prime
  2129.                         if(expResult != jacob)
  2130.         return false;
  2131.         }
  2133.         return true;
  2134.         }
  2137.         //***********************************************************************
  2138.         // Implementation of the Lucas Strong Pseudo Prime test.
  2139.         //
  2140.         // Let n be an odd number with gcd(n,D) = 1, and n - J(D, n) = 2^s * d
  2141.         // with d odd and s >= 0.
  2142.         //
  2143.         // If Ud mod n = 0 or V2^r*d mod n = 0 for some 0 <= r < s, then n
  2144.         // is a strong Lucas pseudoprime with parameters (P, Q).  We select
  2145.         // P and Q based on Selfridge.
  2146.         //
  2147.         // Returns True if number is a strong Lucus pseudo prime.
  2148.         // Otherwise, returns False indicating that number is composite.
  2149.         //***********************************************************************
  2151.         public bool LucasStrongTest()
  2152.         {
  2153.                 BigInteger thisVal;
  2154.                 if((this.data[maxLength-1] & 0x80000000) != 0)        // negative
  2155.                         thisVal = -this;
  2156.                 else
  2157.                         thisVal = this;
  2159.                 if(thisVal.dataLength == 1)
  2160.                 {
  2161.                         // test small numbers
  2162.                         if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
  2163.                                 return false;
  2164.                         else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
  2165.                                 return true;
  2166.                 }
  2168.                 if((thisVal.data[0] & 0x1) == 0)     // even numbers
  2169.                         return false;
  2171.                 return LucasStrongTestHelper(thisVal);
  2172.         }
  2175.         private bool LucasStrongTestHelper(BigInteger thisVal)
  2176.         {
  2177.                 // Do the test (selects D based on Selfridge)
  2178.                 // Let D be the first element of the sequence
  2179.                 // 5, -7, 9, -11, 13, ... for which J(D,n) = -1
  2180.                 // Let P = 1, Q = (1-D) / 4
  2182.                 long D = 5, sign = -1, dCount = 0;
  2183.                 bool done = false;
  2185.                 while(!done)
  2186.                 {
  2187.                         int Jresult = BigInteger.Jacobi(D, thisVal);
  2189.                         if(Jresult == -1)
  2190.                                 done = true;    // J(D, this) = 1
  2191.                         else
  2192.                         {
  2193.                                 if(Jresult == 0 && Math.Abs(D) < thisVal)       // divisor found
  2194.                                         return false;
  2196.                                 if(dCount == 20)
  2197.                                 {
  2198.                                         // check for square
  2199.                                         BigInteger root = thisVal.sqrt();
  2200.                                         if(root * root == thisVal)
  2201.                                                 return false;
  2202.                                 }
  2204.                                 //Console.WriteLine(D);
  2205.                                 D = (Math.Abs(D) + 2) * sign;
  2206.                                 sign = -sign;
  2207.                         }
  2208.                         dCount++;
  2209.                 }
  2211.                 long Q = (1 - D) >> 2;
  2213.                 /*
  2214.                 Console.WriteLine("D = " + D);
  2215.                 Console.WriteLine("Q = " + Q);
  2216.                 Console.WriteLine("(n,D) = " + thisVal.gcd(D));
  2217.                 Console.WriteLine("(n,Q) = " + thisVal.gcd(Q));
  2218.                 Console.WriteLine("J(D|n) = " + BigInteger.Jacobi(D, thisVal));
  2219.                 */
  2221.                 BigInteger p_add1 = thisVal + 1;
  2222.                 int s = 0;
  2224.                 for(int index = 0; index < p_add1.dataLength; index++)
  2225.                 {
  2226.                         uint mask = 0x01;
  2228.                         for(int i = 0; i < 32; i++)
  2229.                         {
  2230.                                 if((p_add1.data[index] & mask) != 0)
  2231.                                 {
  2232.                                         index = p_add1.dataLength;      // to break the outer loop
  2233.                                         break;
  2234.                                 }
  2235.                                 mask <<= 1;
  2236.                                 s++;
  2237.                         }
  2238.                 }
  2240.                 BigInteger t = p_add1 >> s;
  2242.                 // calculate constant = b^(2k) / m
  2243.                 // for Barrett Reduction
  2244.                 BigInteger constant = new BigInteger();
  2246.                 int nLen = thisVal.dataLength << 1;
  2247.                 constant.data[nLen] = 0x00000001;
  2248.                 constant.dataLength = nLen + 1;
  2250.                 constant = constant / thisVal;
  2252.                 BigInteger[] lucas = LucasSequenceHelper(1, Q, t, thisVal, constant, 0);
  2253.                 bool isPrime = false;
  2255.                 if((lucas[0].dataLength == 1 && lucas[0].data[0] == 0) ||
  2256.                    (lucas[1].dataLength == 1 && lucas[1].data[0] == 0))
  2257.                 {
  2258.                         // u(t) = 0 or V(t) = 0
  2259.                         isPrime = true;
  2260.                 }
  2262.                 for(int i = 1; i < s; i++)
  2263.                 {
  2264.                         if(!isPrime)
  2265.                         {
  2266.                                 // doubling of index
  2267.                                 lucas[1] = thisVal.BarrettReduction(lucas[1] * lucas[1], thisVal, constant);
  2268.                                 lucas[1] = (lucas[1] - (lucas[2] << 1)) % thisVal;
  2270.                                 //lucas[1] = ((lucas[1] * lucas[1]) - (lucas[2] << 1)) % thisVal;
  2272.                                 if((lucas[1].dataLength == 1 && lucas[1].data[0] == 0))
  2273.                                         isPrime = true;
  2274.                         }
  2276.                         lucas[2] = thisVal.BarrettReduction(lucas[2] * lucas[2], thisVal, constant);     //Q^k
  2277.                 }
  2280.                 if(isPrime)     // additional checks for composite numbers
  2281.                 {
  2282.                         // If n is prime and gcd(n, Q) == 1, then
  2283.                         // Q^((n+1)/2) = Q * Q^((n-1)/2) is congruent to (Q * J(Q, n)) mod n
  2285.                         BigInteger g = thisVal.gcd(Q);
  2286.                         if(g.dataLength == 1 && g.data[0] == 1)         // gcd(this, Q) == 1
  2287.                         {
  2288.                                 if((lucas[2].data[maxLength-1] & 0x80000000) != 0)
  2289.                                         lucas[2] += thisVal;
  2291.                                 BigInteger temp = (Q * BigInteger.Jacobi(Q, thisVal)) % thisVal;
  2292.                                 if((temp.data[maxLength-1] & 0x80000000) != 0)
  2293.                                         temp += thisVal;
  2295.                                 if(lucas[2] != temp)
  2296.                                         isPrime = false;
  2297.                         }
  2298.                 }
  2300.                 return isPrime;
  2301.         }
  2304.         //***********************************************************************
  2305.         // Determines whether a number is probably prime, using the Rabin-Miller's
  2306.         // test.  Before applying the test, the number is tested for divisibility
  2307.         // by primes < 2000
  2308.         //
  2309.         // Returns true if number is probably prime.
  2310.         //***********************************************************************
  2312.         public bool isProbablePrime(int confidence)
  2313.         {
  2314.                 BigInteger thisVal;
  2315.                 if((this.data[maxLength-1] & 0x80000000) != 0)        // negative
  2316.                         thisVal = -this;
  2317.                 else
  2318.                         thisVal = this;
  2321.                 // test for divisibility by primes < 2000
  2322.                 for(int p = 0; p < primesBelow2000.Length; p++)
  2323.                 {
  2324.                         BigInteger divisor = primesBelow2000[p];
  2326.                         if(divisor >= thisVal)
  2327.                                 break;
  2329.                         BigInteger resultNum = thisVal % divisor;
  2330.                         if(resultNum.IntValue() == 0)
  2331.                         {
  2332.                                 /*
  2333. Console.WriteLine("Not prime!  Divisible by {0}n",
  2334.                                                   primesBelow2000[p]);
  2335.                                 */
  2336.                                 return false;
  2337.                         }
  2338.                 }
  2340.                 if(thisVal.RabinMillerTest(confidence))
  2341.                         return true;
  2342.                 else
  2343.                 {
  2344.                         //Console.WriteLine("Not prime!  Failed primality testn");
  2345.                         return false;
  2346.                 }
  2347.         }
  2350.         //***********************************************************************
  2351.         // Determines whether this BigInteger is probably prime using a
  2352.         // combination of base 2 strong pseudoprime test and Lucas strong
  2353.         // pseudoprime test.
  2354.         //
  2355.         // The sequence of the primality test is as follows,
  2356.         //
  2357.         // 1) Trial divisions are carried out using prime numbers below 2000.
  2358.         //    if any of the primes divides this BigInteger, then it is not prime.
  2359.         //
  2360.         // 2) Perform base 2 strong pseudoprime test.  If this BigInteger is a
  2361.         //    base 2 strong pseudoprime, proceed on to the next step.
  2362.         //
  2363.         // 3) Perform strong Lucas pseudoprime test.
  2364.         //
  2365.         // Returns True if this BigInteger is both a base 2 strong pseudoprime
  2366.         // and a strong Lucas pseudoprime.
  2367.         //
  2368.         // For a detailed discussion of this primality test, see [6].
  2369.         //
  2370.         //***********************************************************************
  2372.         public bool isProbablePrime()
  2373.         {
  2374.                 BigInteger thisVal;
  2375.                 if((this.data[maxLength-1] & 0x80000000) != 0)        // negative
  2376.                         thisVal = -this;
  2377.                 else
  2378.                         thisVal = this;
  2380.                 if(thisVal.dataLength == 1)
  2381.                 {
  2382.                         // test small numbers
  2383.                         if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
  2384.                                 return false;
  2385.                         else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
  2386.                                 return true;
  2387.                 }
  2389.                 if((thisVal.data[0] & 0x1) == 0)     // even numbers
  2390.                         return false;
  2393.                 // test for divisibility by primes < 2000
  2394.                 for(int p = 0; p < primesBelow2000.Length; p++)
  2395.                 {
  2396.                         BigInteger divisor = primesBelow2000[p];
  2398.                         if(divisor >= thisVal)
  2399.                                 break;
  2401.                         BigInteger resultNum = thisVal % divisor;
  2402.                         if(resultNum.IntValue() == 0)
  2403.                         {
  2404. //Console.WriteLine("Not prime!  Divisible by {0}n",
  2405.                                 //                  primesBelow2000[p]);
  2407.                                 return false;
  2408.                         }
  2409.                 }
  2411.                 // Perform BASE 2 Rabin-Miller Test
  2413.                 // calculate values of s and t
  2414.                 BigInteger p_sub1 = thisVal - (new BigInteger(1));
  2415.                 int s = 0;
  2417.                 for(int index = 0; index < p_sub1.dataLength; index++)
  2418.                 {
  2419.                         uint mask = 0x01;
  2421.                         for(int i = 0; i < 32; i++)
  2422.                         {
  2423.                                 if((p_sub1.data[index] & mask) != 0)
  2424.                                 {
  2425.                                         index = p_sub1.dataLength;      // to break the outer loop
  2426.                                         break;
  2427.                                 }
  2428.                                 mask <<= 1;
  2429.                                 s++;
  2430.                         }
  2431.                 }
  2433.                 BigInteger t = p_sub1 >> s;
  2435.         int bits = thisVal.bitCount();
  2436.         BigInteger a = 2;
  2438.                 // b = a^t mod p
  2439.                 BigInteger b = a.modPow(t, thisVal);
  2440.                 bool result = false;
  2442.                 if(b.dataLength == 1 && b.data[0] == 1)         // a^t mod p = 1
  2443.                         result = true;
  2445.                 for(int j = 0; result == false && j < s; j++)
  2446.                 {
  2447.                         if(b == p_sub1)         // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
  2448.                         {
  2449.                                 result = true;
  2450.                                 break;
  2451.                         }
  2453.                         b = (b * b) % thisVal;
  2454.                 }
  2456.                 // if number is strong pseudoprime to base 2, then do a strong lucas test
  2457.                 if(result)
  2458.                 result = LucasStrongTestHelper(thisVal);
  2460.                 return result;
  2461.         }
  2465.         //***********************************************************************
  2466.         // Returns the lowest 4 bytes of the BigInteger as an int.
  2467.         //***********************************************************************
  2469.         public int IntValue()
  2470.         {
  2471.                 return (int)data[0];
  2472.         }
  2475.         //***********************************************************************
  2476.         // Returns the lowest 8 bytes of the BigInteger as a long.
  2477.         //***********************************************************************
  2479.         public long LongValue()
  2480.         {
  2481.                 long val = 0;
  2483.                 val = (long)data[0];
  2484.                 try
  2485.                 {       // exception if maxLength = 1
  2486.                         val |= (long)data[1] << 32;
  2487.                 }
  2488.                 catch(Exception)
  2489.                 {
  2490.                         if((data[0] & 0x80000000) != 0) // negative
  2491.                                 val = (int)data[0];
  2492.                 }
  2494.                 return val;
  2495.         }
  2498.         //***********************************************************************
  2499.         // Computes the Jacobi Symbol for a and b.
  2500.         // Algorithm adapted from [3] and [4] with some optimizations
  2501.         //***********************************************************************
  2503.         public static int Jacobi(BigInteger a, BigInteger b)
  2504.         {
  2505.                 // Jacobi defined only for odd integers
  2506.                 if((b.data[0] & 0x1) == 0)
  2507.                         throw (new ArgumentException("Jacobi defined only for odd integers."));
  2509.                 if(a >= b)      a %= b;
  2510.                 if(a.dataLength == 1 && a.data[0] == 0)      return 0;  // a == 0
  2511.                 if(a.dataLength == 1 && a.data[0] == 1)      return 1;  // a == 1
  2513.                 if(a < 0)
  2514.                 {
  2515.                         if( (((b-1).data[0]) & 0x2) == 0)       //if( (((b-1) >> 1).data[0] & 0x1) == 0)
  2516.                                 return Jacobi(-a, b);
  2517.                         else
  2518.                                 return -Jacobi(-a, b);
  2519.                 }
  2521.                 int e = 0;
  2522.                 for(int index = 0; index < a.dataLength; index++)
  2523.                 {
  2524.                         uint mask = 0x01;
  2526.                         for(int i = 0; i < 32; i++)
  2527.                         {
  2528.                                 if((a.data[index] & mask) != 0)
  2529.                                 {
  2530.                                         index = a.dataLength;      // to break the outer loop
  2531.                                         break;
  2532.                                 }
  2533.                                 mask <<= 1;
  2534.                                 e++;
  2535.                         }
  2536.                 }
  2538.                 BigInteger a1 = a >> e;
  2540.                 int s = 1;
  2541.                 if((e & 0x1) != 0 && ((b.data[0] & 0x7) == 3 || (b.data[0] & 0x7) == 5))
  2542.                         s = -1;
  2544.                 if((b.data[0] & 0x3) == 3 && (a1.data[0] & 0x3) == 3)
  2545.                         s = -s;
  2547.                 if(a1.dataLength == 1 && a1.data[0] == 1)
  2548.                         return s;
  2549.                 else
  2550.                         return (s * Jacobi(b % a1, a1));
  2551.         }
  2555.         //***********************************************************************
  2556.         // Generates a positive BigInteger that is probably prime.
  2557.         //***********************************************************************
  2559.         public static BigInteger genPseudoPrime(int bits, int confidence, Random rand)
  2560.         {
  2561.         BigInteger result = new BigInteger();
  2562.         bool done = false;
  2564.         while(!done)
  2565.         {
  2566.         result.genRandomBits(bits, rand);
  2567.         result.data[0] |= 0x01; // make it odd
  2569.         // prime test
  2570.         done = result.isProbablePrime(confidence);
  2571.         }
  2572.         return result;
  2573.         }
  2576.         //***********************************************************************
  2577.         // Generates a random number with the specified number of bits such
  2578.         // that gcd(number, this) = 1
  2579.         //***********************************************************************
  2581.         public BigInteger genCoPrime(int bits, Random rand)
  2582.         {
  2583.         bool done = false;
  2584.         BigInteger result = new BigInteger();
  2586.         while(!done)
  2587.         {
  2588.                 result.genRandomBits(bits, rand);
  2589.                 //Console.WriteLine(result.ToString(16));
  2591.         // gcd test
  2592.         BigInteger g = result.gcd(this);
  2593. if(g.dataLength == 1 && g.data[0] == 1)
  2594.                                 done = true;
  2595.         }
  2597.         return result;
  2598.         }
  2601.         //***********************************************************************
  2602.         // Returns the modulo inverse of this.  Throws ArithmeticException if
  2603.         // the inverse does not exist.  (i.e. gcd(this, modulus) != 1)
  2604.         //***********************************************************************
  2606.         public BigInteger modInverse(BigInteger modulus)
  2607.         {
  2608.                 BigInteger[] p = { 0, 1 };
  2609.                 BigInteger[] q = new BigInteger[2];    // quotients
  2610.                 BigInteger[] r = { 0, 0 };             // remainders
  2612.                 int step = 0;
  2614.                 BigInteger a = modulus;
  2615.                 BigInteger b = this;
  2617.                 while(b.dataLength > 1 || (b.dataLength == 1 && b.data[0] != 0))
  2618.                 {
  2619.                         BigInteger quotient = new BigInteger();
  2620.                         BigInteger remainder = new BigInteger();
  2622.                         if(step > 1)
  2623.                         {
  2624.                                 BigInteger pval = (p[0] - (p[1] * q[0])) % modulus;
  2625.                                 p[0] = p[1];
  2626.                                 p[1] = pval;
  2627.                         }
  2629.                         if(b.dataLength == 1)
  2630.                                 singleByteDivide(a, b, quotient, remainder);
  2631.                         else
  2632.                                 multiByteDivide(a, b, quotient, remainder);
  2634.                         /*
  2635.                         Console.WriteLine(quotient.dataLength);
  2636.                         Console.WriteLine("{0} = {1}({2}) + {3}  p = {4}", a.ToString(10),
  2637.                                           b.ToString(10), quotient.ToString(10), remainder.ToString(10),
  2638.                                           p[1].ToString(10));
  2639.                         */
  2641.                         q[0] = q[1];
  2642.                         r[0] = r[1];
  2643.                         q[1] = quotient; r[1] = remainder;
  2645.                         a = b;
  2646.                         b = remainder;
  2648.                         step++;
  2649.                 }
  2651.                 if(r[0].dataLength > 1 || (r[0].dataLength == 1 && r[0].data[0] != 1))
  2652.                         throw (new ArithmeticException("No inverse!"));
  2654.                 BigInteger result = ((p[0] - (p[1] * q[0])) % modulus);
  2656.                 if((result.data[maxLength - 1] & 0x80000000) != 0)
  2657.                         result += modulus;  // get the least positive modulus
  2659.                 return result;
  2660.         }
  2663.         //***********************************************************************
  2664.         // Returns the value of the BigInteger as a byte array.  The lowest
  2665.         // index contains the MSB.
  2666.         //***********************************************************************
  2668.         public byte[] getBytes()
  2669.         {
  2670.                 int numBits = bitCount();
  2671.                 byte[] result = null;
  2673.                 if(numBits == 0)
  2674.                 {
  2675.                         result = new byte[1];
  2676.                         result[0] = 0;
  2677.                 }
  2678.                 else
  2679.                 {
  2680.                         int numBytes = numBits >> 3;
  2681.                         if((numBits & 0x7) != 0)
  2682.                                 numBytes++;
  2684.                         result = new byte[numBytes];
  2686.                         //Console.WriteLine(result.Length);
  2688.                         int numBytesInWord = numBytes & 0x3;
  2689.                         if(numBytesInWord == 0)
  2690.                                 numBytesInWord = 4;
  2692.                         int pos = 0;
  2693.                         for(int i = dataLength - 1; i >= 0; i--)
  2694.                         {
  2695.                                 uint val = data[i];
  2696.                                 for(int j = numBytesInWord - 1; j >= 0; j--)
  2697.                                 {
  2698.                                         result[pos+j] = (byte)(val & 0xFF);
  2699.                                         val >>= 8;
  2700.                                 }
  2702.                                 pos += numBytesInWord;
  2703.                                 numBytesInWord = 4;
  2704.                         }
  2705.                 }
  2706.                 return result;
  2707.         }
  2709.         //***********************************************************************
  2710.         // Sets the value of the specified bit to 1
  2711.         // The Least Significant Bit position is 0.
  2712.         //***********************************************************************
  2714.         public void setBit(uint bitNum)
  2715.         {
  2716.                 uint bytePos = bitNum >> 5;             // divide by 32
  2717.                 byte bitPos = (byte)(bitNum & 0x1F);    // get the lowest 5 bits
  2719.                 uint mask = (uint)1 << bitPos;
  2720.                 this.data[bytePos] |= mask;
  2722.                 if(bytePos >= this.dataLength)
  2723.                         this.dataLength = (int)bytePos + 1;
  2724.         }
  2727.         //***********************************************************************
  2728.         // Sets the value of the specified bit to 0
  2729.         // The Least Significant Bit position is 0.
  2730.         //***********************************************************************
  2732.         public void unsetBit(uint bitNum)
  2733.         {
  2734.                 uint bytePos = bitNum >> 5;
  2736.                 if(bytePos < this.dataLength)
  2737.                 {
  2738.                         byte bitPos = (byte)(bitNum & 0x1F);
  2740.                         uint mask = (uint)1 << bitPos;
  2741.                         uint mask2 = 0xFFFFFFFF ^ mask;
  2743.                         this.data[bytePos] &= mask2;
  2745.                         if(this.dataLength > 1 && this.data[this.dataLength - 1] == 0)
  2746.                                 this.dataLength--;
  2747.                 }
  2748.         }
  2751.         //***********************************************************************
  2752.         // Returns a value that is equivalent to the integer square root
  2753.         // of the BigInteger.
  2754.         //
  2755.         // The integer square root of "this" is defined as the largest integer n
  2756.         // such that (n * n) <= this
  2757.         //
  2758.         //***********************************************************************
  2760.         public BigInteger sqrt()
  2761.         {
  2762.                 uint numBits = (uint)this.bitCount();
  2764.                 if((numBits & 0x1) != 0)        // odd number of bits
  2765.                         numBits = (numBits >> 1) + 1;
  2766.                 else
  2767.                         numBits = (numBits >> 1);
  2769.                 uint bytePos = numBits >> 5;
  2770.                 byte bitPos = (byte)(numBits & 0x1F);
  2772.                 uint mask;
  2774.                 BigInteger result = new BigInteger();
  2775.                 if(bitPos == 0)
  2776.                         mask = 0x80000000;
  2777.                 else
  2778.                 {
  2779.                         mask = (uint)1 << bitPos;
  2780.                         bytePos++;
  2781.                 }
  2782.                 result.dataLength = (int)bytePos;
  2784.                 for(int i = (int)bytePos - 1; i >= 0; i--)
  2785.                 {
  2786.                         while(mask != 0)
  2787.                         {
  2788.                                 // guess
  2789.                                 result.data[i] ^= mask;
  2791.                                 // undo the guess if its square is larger than this
  2792.                                 if((result * result) > this)
  2793.                                         result.data[i] ^= mask;
  2795.                                 mask >>= 1;
  2796.                         }
  2797.                         mask = 0x80000000;
  2798.                 }
  2799.                 return result;
  2800.         }
  2803.         //***********************************************************************
  2804.         // Returns the k_th number in the Lucas Sequence reduced modulo n.
  2805.         //
  2806.         // Uses index doubling to speed up the process.  For example, to calculate V(k),
  2807.         // we maintain two numbers in the sequence V(n) and V(n+1).
  2808.         //
  2809.         // To obtain V(2n), we use the identity
  2810.         //      V(2n) = (V(n) * V(n)) - (2 * Q^n)
  2811.         // To obtain V(2n+1), we first write it as
  2812.         //      V(2n+1) = V((n+1) + n)
  2813.         // and use the identity
  2814.         //      V(m+n) = V(m) * V(n) - Q * V(m-n)
  2815.         // Hence,
  2816.         //      V((n+1) + n) = V(n+1) * V(n) - Q^n * V((n+1) - n)
  2817.         //                   = V(n+1) * V(n) - Q^n * V(1)
  2818.         //                   = V(n+1) * V(n) - Q^n * P
  2819.         //
  2820.         // We use k in its binary expansion and perform index doubling for each
  2821.         // bit position.  For each bit position that is set, we perform an
  2822.         // index doubling followed by an index addition.  This means that for V(n),
  2823.         // we need to update it to V(2n+1).  For V(n+1), we need to update it to
  2824.         // V((2n+1)+1) = V(2*(n+1))
  2825.         //
  2826.         // This function returns
  2827.         // [0] = U(k)
  2828.         // [1] = V(k)
  2829.         // [2] = Q^n
  2830.         //
  2831.         // Where U(0) = 0 % n, U(1) = 1 % n
  2832.         //       V(0) = 2 % n, V(1) = P % n
  2833.         //***********************************************************************
  2835.         public static BigInteger[] LucasSequence(BigInteger P, BigInteger Q,
  2836.                                                  BigInteger k, BigInteger n)
  2837.         {
  2838.                 if(k.dataLength == 1 && k.data[0] == 0)
  2839.                 {
  2840.                         BigInteger[] result = new BigInteger[3];
  2842.                         result[0] = 0; result[1] = 2 % n; result[2] = 1 % n;
  2843.                         return result;
  2844.                 }
  2846.                 // calculate constant = b^(2k) / m
  2847.                 // for Barrett Reduction
  2848.                 BigInteger constant = new BigInteger();
  2850.                 int nLen = n.dataLength << 1;
  2851.                 constant.data[nLen] = 0x00000001;
  2852.                 constant.dataLength = nLen + 1;
  2854.                 constant = constant / n;
  2856.                 // calculate values of s and t
  2857.                 int s = 0;
  2859.                 for(int index = 0; index < k.dataLength; index++)
  2860.                 {
  2861.                         uint mask = 0x01;
  2863.                         for(int i = 0; i < 32; i++)
  2864.                         {
  2865.                                 if((k.data[index] & mask) != 0)
  2866.                                 {
  2867.                                         index = k.dataLength;      // to break the outer loop
  2868.                                         break;
  2869.                                 }
  2870.                                 mask <<= 1;
  2871.                                 s++;
  2872.                         }
  2873.                 }
  2875.                 BigInteger t = k >> s;
  2877.                 //Console.WriteLine("s = " + s + " t = " + t);
  2878.                 return LucasSequenceHelper(P, Q, t, n, constant, s);
  2879.         }
  2882.         //***********************************************************************
  2883.         // Performs the calculation of the kth term in the Lucas Sequence.
  2884.         // For details of the algorithm, see reference [9].
  2885.         //
  2886.         // k must be odd.  i.e LSB == 1
  2887.         //***********************************************************************
  2889.         private static BigInteger[] LucasSequenceHelper(BigInteger P, BigInteger Q,
  2890.                                                         BigInteger k, BigInteger n,
  2891.                                                         BigInteger constant, int s)
  2892.         {
  2893.                 BigInteger[] result = new BigInteger[3];
  2895.                 if((k.data[0] & 0x00000001) == 0)
  2896.                         throw (new ArgumentException("Argument k must be odd."));
  2898.                 int numbits = k.bitCount();
  2899.                 uint mask = (uint)0x1 << ((numbits & 0x1F) - 1);
  2901.                 // v = v0, v1 = v1, u1 = u1, Q_k = Q^0
  2903.                 BigInteger v = 2 % n, Q_k = 1 % n,
  2904.                            v1 = P % n, u1 = Q_k;
  2905.                 bool flag = true;
  2907.                 for(int i = k.dataLength - 1; i >= 0 ; i--)     // iterate on the binary expansion of k
  2908.                 {
  2909.                         //Console.WriteLine("round");
  2910.                         while(mask != 0)
  2911.                         {
  2912.                                 if(i == 0 && mask == 0x00000001)        // last bit
  2913.                                         break;
  2915.                                 if((k.data[i] & mask) != 0)             // bit is set
  2916.                                 {
  2917.                                         // index doubling with addition
  2919.                                         u1 = (u1 * v1) % n;
  2921.                                         v = ((v * v1) - (P * Q_k)) % n;
  2922.                                         v1 = n.BarrettReduction(v1 * v1, n, constant);
  2923.                                         v1 = (v1 - ((Q_k * Q) << 1)) % n;
  2925.                                         if(flag)
  2926.                                                 flag = false;
  2927.                                         else
  2928.                                                 Q_k = n.BarrettReduction(Q_k * Q_k, n, constant);
  2930.                                         Q_k = (Q_k * Q) % n;
  2931.                                 }
  2932.                                 else
  2933.                                 {
  2934.                                         // index doubling
  2935.                                         u1 = ((u1 * v) - Q_k) % n;
  2937.                                         v1 = ((v * v1) - (P * Q_k)) % n;
  2938.                                         v = n.BarrettReduction(v * v, n, constant);
  2939.                                         v = (v - (Q_k << 1)) % n;
  2941.                                         if(flag)
  2942.                                         {
  2943.                                                 Q_k = Q % n;
  2944.                                                 flag = false;
  2945.                                         }
  2946.                                         else
  2947.                                                 Q_k = n.BarrettReduction(Q_k * Q_k, n, constant);
  2948.                                }
  2950.                                mask >>= 1;
  2951.                         }
  2952.                         mask = 0x80000000;
  2953.                 }
  2955.                 // at this point u1 = u(n+1) and v = v(n)
  2956.                 // since the last bit always 1, we need to transform u1 to u(2n+1) and v to v(2n+1)
  2958.                 u1 = ((u1 * v) - Q_k) % n;
  2959.                 v = ((v * v1) - (P * Q_k)) % n;
  2960.                 if(flag)
  2961.                         flag = false;
  2962.                 else
  2963.                         Q_k = n.BarrettReduction(Q_k * Q_k, n, constant);
  2965.                 Q_k = (Q_k * Q) % n;
  2968.                 for(int i = 0; i < s; i++)
  2969.                 {
  2970.                         // index doubling
  2971.                         u1 = (u1 * v) % n;
  2972.                         v = ((v * v) - (Q_k << 1)) % n;
  2974.                         if(flag)
  2975.                         {
  2976.                                 Q_k = Q % n;
  2977.                                 flag = false;
  2978.                         }
  2979.                         else
  2980.                                 Q_k = n.BarrettReduction(Q_k * Q_k, n, constant);
  2981.                 }
  2983.                 result[0] = u1;
  2984.                 result[1] = v;
  2985.                 result[2] = Q_k;
  2987.                 return result;
  2988.         }
  2991.         //***********************************************************************
  2992.         // Tests the correct implementation of the /, %, * and + operators
  2993.         //***********************************************************************
  2995.         public static void MulDivTest(int rounds)
  2996.         {
  2997.                 Random rand = new Random();
  2998.         byte[] val = new byte[64];
  2999.         byte[] val2 = new byte[64];
  3001.         for(int count = 0; count < rounds; count++)
  3002.         {
  3003.                 // generate 2 numbers of random length
  3004.         int t1 = 0;
  3005.         while(t1 == 0)
  3006.         t1 = (int)(rand.NextDouble() * 65);
  3008.         int t2 = 0;
  3009.         while(t2 == 0)
  3010.         t2 = (int)(rand.NextDouble() * 65);
  3012.         bool done = false;
  3013.         while(!done)
  3014.         {
  3015.         for(int i = 0; i < 64; i++)
  3016.         {
  3017.         if(i < t1)
  3018.         val[i] = (byte)(rand.NextDouble() * 256);
  3019.         else
  3020.         val[i] = 0;
  3022.         if(val[i] != 0)
  3023.         done = true;
  3024.         }
  3025.         }
  3027.         done = false;
  3028.         while(!done)
  3029.         {
  3030.         for(int i = 0; i < 64; i++)
  3031.         {
  3032.         if(i < t2)
  3033.         val2[i] = (byte)(rand.NextDouble() * 256);
  3034.         else
  3035.         val2[i] = 0;
  3037.         if(val2[i] != 0)
  3038.         done = true;
  3039.         }
  3040.         }
  3042.         while(val[0] == 0)
  3043.                 val[0] = (byte)(rand.NextDouble() * 256);
  3044.         while(val2[0] == 0)
  3045.                 val2[0] = (byte)(rand.NextDouble() * 256);
  3047.                         Console.WriteLine(count);
  3048.         BigInteger bn1 = new BigInteger(val, t1);
  3049.         BigInteger bn2 = new BigInteger(val2, t2);
  3052.                         // Determine the quotient and remainder by dividing
  3053.                         // the first number by the second.
  3055.         BigInteger bn3 = bn1 / bn2;
  3056.         BigInteger bn4 = bn1 % bn2;
  3058.         // Recalculate the number
  3059.         BigInteger bn5 = (bn3 * bn2) + bn4;
  3061.                         // Make sure they're the same
  3062.          if(bn5 != bn1)
  3063.          {
  3064.          Console.WriteLine("Error at " + count);
  3065.                                 Console.WriteLine(bn1 + "n");
  3066.         Console.WriteLine(bn2 + "n");
  3067.         Console.WriteLine(bn3 + "n");
  3068.                                 Console.WriteLine(bn4 + "n");
  3069.         Console.WriteLine(bn5 + "n");
  3070.         return;
  3071.         }
  3072.         }
  3073.         }
  3076.         //***********************************************************************
  3077.         // Tests the correct implementation of the modulo exponential function
  3078.         // using RSA encryption and decryption (using pre-computed encryption and
  3079.         // decryption keys).
  3080.         //***********************************************************************
  3082.         public static void RSATest(int rounds)
  3083.         {
  3084.                 Random rand = new Random(1);
  3085.         byte[] val = new byte[64];
  3087.         // private and public key
  3088.                 BigInteger bi_e = new BigInteger("a932b948feed4fb2b692609bd22164fc9edb59fae7880cc1eaff7b3c9626b7e5b241c27a974833b2622ebe09beb451917663d47232488f23a117fc97720f1e7", 16);
  3089.                 BigInteger bi_d = new BigInteger("4adf2f7a89da93248509347d2ae506d683dd3a16357e859a980c4f77a4e2f7a01fae289f13a851df6e9db5adaa60bfd2b162bbbe31f7c8f828261a6839311929d2cef4f864dde65e556ce43c89bbbf9f1ac5511315847ce9cc8dc92470a747b8792d6a83b0092d2e5ebaf852c85cacf34278efa99160f2f8aa7ee7214de07b7", 16);
  3090.                 BigInteger bi_n = new BigInteger("e8e77781f36a7b3188d711c2190b560f205a52391b3479cdb99fa010745cbeba5f2adc08e1de6bf38398a0487c4a73610d94ec36f17f3f46ad75e17bc1adfec99839589f45f95ccc94cb2a5c500b477eb3323d8cfab0c8458c96f0147a45d27e45a4d11d54d77684f65d48f15fafcc1ba208e71e921b9bd9017c16a5231af7f", 16);
  3092.                 Console.WriteLine("e =n" + bi_e.ToString(10));
  3093.                 Console.WriteLine("nd =n" + bi_d.ToString(10));
  3094.                 Console.WriteLine("nn =n" + bi_n.ToString(10) + "n");
  3096.         for(int count = 0; count < rounds; count++)
  3097.         {
  3098.                 // generate data of random length
  3099.         int t1 = 0;
  3100.         while(t1 == 0)
  3101.         t1 = (int)(rand.NextDouble() * 65);
  3103.         bool done = false;
  3104.         while(!done)
  3105.         {
  3106.         for(int i = 0; i < 64; i++)
  3107.         {
  3108.         if(i < t1)
  3109.         val[i] = (byte)(rand.NextDouble() * 256);
  3110.         else
  3111.         val[i] = 0;
  3113.         if(val[i] != 0)
  3114.         done = true;
  3115.         }
  3116.         }
  3118.         while(val[0] == 0)
  3119.                 val[0] = (byte)(rand.NextDouble() * 256);
  3121.                         Console.Write("Round = " + count);
  3123.                         // encrypt and decrypt data
  3124.         BigInteger bi_data = new BigInteger(val, t1);
  3125.                         BigInteger bi_encrypted = bi_data.modPow(bi_e, bi_n);
  3126.                         BigInteger bi_decrypted = bi_encrypted.modPow(bi_d, bi_n);
  3128.                         // compare
  3129.                         if(bi_decrypted != bi_data)
  3130.          {
  3131.          Console.WriteLine("nError at round " + count);
  3132.                                 Console.WriteLine(bi_data + "n");
  3133.         return;
  3134.         }
  3135.         Console.WriteLine(" <PASSED>.");
  3136.         }
  3138.         }
  3141.         //***********************************************************************
  3142.         // Tests the correct implementation of the modulo exponential and
  3143.         // inverse modulo functions using RSA encryption and decryption.  The two
  3144.         // pseudoprimes p and q are fixed, but the two RSA keys are generated
  3145.         // for each round of testing.
  3146.         //***********************************************************************
  3148.         public static void RSATest2(int rounds)
  3149.         {
  3150.                 Random rand = new Random();
  3151.         byte[] val = new byte[64];
  3153.                 byte[] pseudoPrime1 = {
  3154.                         (byte)0x85, (byte)0x84, (byte)0x64, (byte)0xFD, (byte)0x70, (byte)0x6A,
  3155.                         (byte)0x9F, (byte)0xF0, (byte)0x94, (byte)0x0C, (byte)0x3E, (byte)0x2C,
  3156.                         (byte)0x74, (byte)0x34, (byte)0x05, (byte)0xC9, (byte)0x55, (byte)0xB3,
  3157.                         (byte)0x85, (byte)0x32, (byte)0x98, (byte)0x71, (byte)0xF9, (byte)0x41,
  3158.                         (byte)0x21, (byte)0x5F, (byte)0x02, (byte)0x9E, (byte)0xEA, (byte)0x56,
  3159.                         (byte)0x8D, (byte)0x8C, (byte)0x44, (byte)0xCC, (byte)0xEE, (byte)0xEE,
  3160.                         (byte)0x3D, (byte)0x2C, (byte)0x9D, (byte)0x2C, (byte)0x12, (byte)0x41,
  3161.                         (byte)0x1E, (byte)0xF1, (byte)0xC5, (byte)0x32, (byte)0xC3, (byte)0xAA,
  3162.                         (byte)0x31, (byte)0x4A, (byte)0x52, (byte)0xD8, (byte)0xE8, (byte)0xAF,
  3163.                         (byte)0x42, (byte)0xF4, (byte)0x72, (byte)0xA1, (byte)0x2A, (byte)0x0D,
  3164.                         (byte)0x97, (byte)0xB1, (byte)0x31, (byte)0xB3,
  3165.                 };
  3167.                 byte[] pseudoPrime2 = {
  3168.                         (byte)0x99, (byte)0x98, (byte)0xCA, (byte)0xB8, (byte)0x5E, (byte)0xD7,
  3169.                         (byte)0xE5, (byte)0xDC, (byte)0x28, (byte)0x5C, (byte)0x6F, (byte)0x0E,
  3170.                         (byte)0x15, (byte)0x09, (byte)0x59, (byte)0x6E, (byte)0x84, (byte)0xF3,
  3171.                         (byte)0x81, (byte)0xCD, (byte)0xDE, (byte)0x42, (byte)0xDC, (byte)0x93,
  3172.                         (byte)0xC2, (byte)0x7A, (byte)0x62, (byte)0xAC, (byte)0x6C, (byte)0xAF,
  3173.                         (byte)0xDE, (byte)0x74, (byte)0xE3, (byte)0xCB, (byte)0x60, (byte)0x20,
  3174.                         (byte)0x38, (byte)0x9C, (byte)0x21, (byte)0xC3, (byte)0xDC, (byte)0xC8,
  3175.                         (byte)0xA2, (byte)0x4D, (byte)0xC6, (byte)0x2A, (byte)0x35, (byte)0x7F,
  3176.                         (byte)0xF3, (byte)0xA9, (byte)0xE8, (byte)0x1D, (byte)0x7B, (byte)0x2C,
  3177.                         (byte)0x78, (byte)0xFA, (byte)0xB8, (byte)0x02, (byte)0x55, (byte)0x80,
  3178.                         (byte)0x9B, (byte)0xC2, (byte)0xA5, (byte)0xCB,
  3179.                 };
  3182.                 BigInteger bi_p = new BigInteger(pseudoPrime1);
  3183.                 BigInteger bi_q = new BigInteger(pseudoPrime2);
  3184.                 BigInteger bi_pq = (bi_p-1)*(bi_q-1);
  3185.                 BigInteger bi_n = bi_p * bi_q;
  3187.         for(int count = 0; count < rounds; count++)
  3188.         {
  3189.                 // generate private and public key
  3190.                         BigInteger bi_e = bi_pq.genCoPrime(512, rand);
  3191.                         BigInteger bi_d = bi_e.modInverse(bi_pq);
  3193.                         Console.WriteLine("ne =n" + bi_e.ToString(10));
  3194.                         Console.WriteLine("nd =n" + bi_d.ToString(10));
  3195.                         Console.WriteLine("nn =n" + bi_n.ToString(10) + "n");
  3197.                 // generate data of random length
  3198.         int t1 = 0;
  3199.         while(t1 == 0)
  3200.         t1 = (int)(rand.NextDouble() * 65);
  3202.         bool done = false;
  3203.         while(!done)
  3204.         {
  3205.         for(int i = 0; i < 64; i++)
  3206.         {
  3207.         if(i < t1)
  3208.         val[i] = (byte)(rand.NextDouble() * 256);
  3209.         else
  3210.         val[i] = 0;
  3212.         if(val[i] != 0)
  3213.         done = true;
  3214.         }
  3215.         }
  3217.         while(val[0] == 0)
  3218.                 val[0] = (byte)(rand.NextDouble() * 256);
  3220.                         Console.Write("Round = " + count);
  3222.                         // encrypt and decrypt data
  3223.         BigInteger bi_data = new BigInteger(val, t1);
  3224.                         BigInteger bi_encrypted = bi_data.modPow(bi_e, bi_n);
  3225.                         BigInteger bi_decrypted = bi_encrypted.modPow(bi_d, bi_n);
  3227.                         // compare
  3228.                         if(bi_decrypted != bi_data)
  3229.          {
  3230.          Console.WriteLine("nError at round " + count);
  3231.                                 Console.WriteLine(bi_data + "n");
  3232.         return;
  3233.         }
  3234.         Console.WriteLine(" <PASSED>.");
  3235.         }
  3237.         }
  3240.         //***********************************************************************
  3241.         // Tests the correct implementation of sqrt() method.
  3242.         //***********************************************************************
  3244.         public static void SqrtTest(int rounds)
  3245.         {
  3246.                 Random rand = new Random();
  3247.         for(int count = 0; count < rounds; count++)
  3248.         {
  3249.                 // generate data of random length
  3250.         int t1 = 0;
  3251.         while(t1 == 0)
  3252.         t1 = (int)(rand.NextDouble() * 1024);
  3254.                         Console.Write("Round = " + count);
  3256.                         BigInteger a = new BigInteger();
  3257.                         a.genRandomBits(t1, rand);
  3259.                         BigInteger b = a.sqrt();
  3260.                         BigInteger c = (b+1)*(b+1);
  3262.                         // check that b is the largest integer such that b*b <= a
  3263.                         if(c <= a)
  3264.          {
  3265.          Console.WriteLine("nError at round " + count);
  3266.                                 Console.WriteLine(a + "n");
  3267.         return;
  3268.         }
  3269.         Console.WriteLine(" <PASSED>.");
  3270.         }
  3271.         }
  3275.         public static void Main1(string[] args)
  3276.         {
  3277.                 // Known problem -> these two pseudoprimes passes my implementation of
  3278.                 // primality test but failed in JDK's isProbablePrime test.
  3280.                 byte[] pseudoPrime1 = { (byte)0x00,
  3281.                         (byte)0x85, (byte)0x84, (byte)0x64, (byte)0xFD, (byte)0x70, (byte)0x6A,
  3282.                         (byte)0x9F, (byte)0xF0, (byte)0x94, (byte)0x0C, (byte)0x3E, (byte)0x2C,
  3283.                         (byte)0x74, (byte)0x34, (byte)0x05, (byte)0xC9, (byte)0x55, (byte)0xB3,
  3284.                         (byte)0x85, (byte)0x32, (byte)0x98, (byte)0x71, (byte)0xF9, (byte)0x41,
  3285.                         (byte)0x21, (byte)0x5F, (byte)0x02, (byte)0x9E, (byte)0xEA, (byte)0x56,
  3286.                         (byte)0x8D, (byte)0x8C, (byte)0x44, (byte)0xCC, (byte)0xEE, (byte)0xEE,
  3287.                         (byte)0x3D, (byte)0x2C, (byte)0x9D, (byte)0x2C, (byte)0x12, (byte)0x41,
  3288.                         (byte)0x1E, (byte)0xF1, (byte)0xC5, (byte)0x32, (byte)0xC3, (byte)0xAA,
  3289.                         (byte)0x31, (byte)0x4A, (byte)0x52, (byte)0xD8, (byte)0xE8, (byte)0xAF,
  3290.                         (byte)0x42, (byte)0xF4, (byte)0x72, (byte)0xA1, (byte)0x2A, (byte)0x0D,
  3291.                         (byte)0x97, (byte)0xB1, (byte)0x31, (byte)0xB3,
  3292.                 };
  3294.                 byte[] pseudoPrime2 = { (byte)0x00,
  3295.                         (byte)0x99, (byte)0x98, (byte)0xCA, (byte)0xB8, (byte)0x5E, (byte)0xD7,
  3296.                         (byte)0xE5, (byte)0xDC, (byte)0x28, (byte)0x5C, (byte)0x6F, (byte)0x0E,
  3297.                         (byte)0x15, (byte)0x09, (byte)0x59, (byte)0x6E, (byte)0x84, (byte)0xF3,
  3298.                         (byte)0x81, (byte)0xCD, (byte)0xDE, (byte)0x42, (byte)0xDC, (byte)0x93,
  3299.                         (byte)0xC2, (byte)0x7A, (byte)0x62, (byte)0xAC, (byte)0x6C, (byte)0xAF,
  3300.                         (byte)0xDE, (byte)0x74, (byte)0xE3, (byte)0xCB, (byte)0x60, (byte)0x20,
  3301.                         (byte)0x38, (byte)0x9C, (byte)0x21, (byte)0xC3, (byte)0xDC, (byte)0xC8,
  3302.                         (byte)0xA2, (byte)0x4D, (byte)0xC6, (byte)0x2A, (byte)0x35, (byte)0x7F,
  3303.                         (byte)0xF3, (byte)0xA9, (byte)0xE8, (byte)0x1D, (byte)0x7B, (byte)0x2C,
  3304.                         (byte)0x78, (byte)0xFA, (byte)0xB8, (byte)0x02, (byte)0x55, (byte)0x80,
  3305.                         (byte)0x9B, (byte)0xC2, (byte)0xA5, (byte)0xCB,
  3306.                 };
  3308.                 Console.WriteLine("List of primes < 2000n---------------------");
  3309.                 int limit = 100, count = 0;
  3310.                 for(int i = 0; i < 2000; i++)
  3311.                 {
  3312.                         if(i >= limit)
  3313.                         {
  3314.                                 Console.WriteLine();
  3315.                                 limit += 100;
  3316.                         }
  3318.                         BigInteger p = new BigInteger(-i);
  3320.                         if(p.isProbablePrime())
  3321.                         {
  3322.                                 Console.Write(i + ", ");
  3323.                                 count++;
  3324.                         }
  3325.                 }
  3326.                 Console.WriteLine("nCount = " + count);
  3329.                 BigInteger bi1 = new BigInteger(pseudoPrime1);
  3330.                 Console.WriteLine("nnPrimality testing forn" + bi1.ToString() + "n");
  3331.                 Console.WriteLine("SolovayStrassenTest(5) = " + bi1.SolovayStrassenTest(5));
  3332.                 Console.WriteLine("RabinMillerTest(5) = " + bi1.RabinMillerTest(5));
  3333.                 Console.WriteLine("FermatLittleTest(5) = " + bi1.FermatLittleTest(5));
  3334.                 Console.WriteLine("isProbablePrime() = " + bi1.isProbablePrime());
  3336.                 Console.Write("nGenerating 512-bits random pseudoprime. . .");
  3337.                 Random rand = new Random();
  3338.                 BigInteger prime = BigInteger.genPseudoPrime(512, 5, rand);
  3339.                 Console.WriteLine("n" + prime);
  3341.                 //int dwStart = System.Environment.TickCount;
  3342.                 //BigInteger.MulDivTest(100000);
  3343.                 //BigInteger.RSATest(10);
  3344.                 //BigInteger.RSATest2(10);
  3345.                 //Console.WriteLine(System.Environment.TickCount - dwStart);
  3347.         }
  3349. }