< Summary

Information
Class: Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger
Assembly: Renci.SshNet
File(s): \home\appveyor\projects\ssh-net\src\Renci.SshNet\Security\BouncyCastle\math\BigInteger.cs
Line coverage
38%
Covered lines: 870
Uncovered lines: 1403
Coverable lines: 2273
Total lines: 3605
Line coverage: 38.2%
Branch coverage
30%
Covered branches: 264
Total branches: 864
Branch coverage: 30.5%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.cctor()100%6100%
.ctor(...)80%1089.18%
GetByteLength(...)100%1100%
Arbitrary(...)100%10%
.ctor(...)100%10%
.ctor(...)0%460%
.ctor(...)100%10%
.ctor(...)0%160%
MakeMagnitude(...)75%1682.5%
.ctor(...)100%1100%
.ctor(...)50%872.22%
.ctor(...)50%676.19%
.ctor(...)0%140%
Abs()100%2100%
AddMagnitudes(...)75%888.88%
Add(...)62.5%875%
AddToMagnitude(...)100%6100%
And(...)0%240%
AndNot(...)100%10%
get_BitCount()83.33%683.33%
BitCnt(...)100%1100%
CalcBitLength(...)33.33%1247.82%
get_BitLength()75%4100%
BitLen(...)100%6100%
QuickPow2Check()50%2100%
CompareTo(...)100%10%
CompareTo(...)0%80%
CompareNoLeadingZeroes(...)90%1092.85%
CompareTo(...)50%6100%
Divide(...)65.78%3870.52%
Divide(...)37.5%858.33%
DivideAndRemainder(...)0%80%
Equals(...)66.66%687.5%
IsEqualMagnitude(...)83.33%690.9%
Gcd(...)0%60%
GetHashCode()0%60%
Inc()0%40%
get_IntValue()75%4100%
IsProbablePrime(...)100%10%
IsProbablePrime(...)0%60%
CheckProbablePrime(...)0%80%
RabinMillerTest(...)100%10%
RabinMillerTest(...)0%280%
get_LongValue()66.66%690.9%
Max(...)0%20%
Min(...)0%20%
Mod(...)50%483.33%
ModInverse(...)0%80%
ModInversePow2(...)0%100%
ModInverse32(...)100%10%
ModInverse64(...)100%10%
ExtEuclid(...)0%40%
ZeroOut(...)100%10%
ModPow(...)0%160%
ModPowBarrett(...)0%120%
ReduceBarrett(...)0%80%
ModPowMonty(...)0%260%
GetWindowList(...)0%80%
CreateWindowEntry(...)0%20%
Square(...)100%8100%
Multiply(...)80%1086.2%
GetMQuote()0%20%
MontgomeryReduce(...)0%60%
MultiplyMonty(...)0%120%
SquareMonty(...)0%140%
MultiplyMontyNIsOne(...)0%20%
Multiply(...)66.66%1284.21%
Square()66.66%683.33%
Negate()50%280%
NextProbablePrime()0%60%
Not()100%10%
Pow(...)64.28%1472.41%
ProbablePrime(...)100%10%
Remainder(...)0%20%
Remainder(...)0%360%
Remainder(...)43.75%1644.82%
LastNBits(...)75%492.85%
DivideWords(...)0%20%
RemainderWords(...)0%20%
ShiftLeft(...)100%6100%
ShiftLeftOneInPlace(...)0%40%
ShiftLeft(...)71.42%1490%
ShiftRightInPlace(...)100%10100%
ShiftRightOneInPlace(...)100%2100%
ShiftRight(...)85.71%1496.66%
get_SignValue()100%1100%
Subtract(...)83.33%690%
Subtract(...)70%1085.71%
doSubBigLil(...)100%1100%
ToByteArray()100%1100%
ToByteArrayUnsigned()100%1100%
ToByteArray(...)41.66%2448.33%
ToString()100%10%
ToString(...)0%440%
ToString(...)0%100%
AppendZeroExtendedString(...)0%20%
CreateUValueOf(...)66.66%686.66%
CreateValueOf(...)0%40%
ValueOf(...)50%483.33%
GetLowestSetBit()0%20%
GetLowestSetBitMaskFirst(...)0%60%
TestBit(...)50%672.72%
Or(...)0%240%
Xor(...)57.14%2865.85%
SetBit(...)0%80%
ClearBit(...)0%80%
FlipBit(...)0%60%
FlipExistingBit(...)100%10%

File(s)

\home\appveyor\projects\ssh-net\src\Renci.SshNet\Security\BouncyCastle\math\BigInteger.cs

#LineLine coverage
 1using System;
 2using System.Collections;
 3using System.Collections.Generic;
 4using System.Diagnostics;
 5using System.Globalization;
 6using System.Text;
 7
 8using Renci.SshNet.Security.Org.BouncyCastle.Security;
 9using Renci.SshNet.Security.Org.BouncyCastle.Utilities;
 10
 11namespace Renci.SshNet.Security.Org.BouncyCastle.Math
 12{
 13#if FEATURE_BINARY_SERIALIZATION
 14    [Serializable]
 15#endif
 16    internal class BigInteger
 17    {
 18        // The first few odd primes
 19        /*
 20                3   5   7   11  13  17  19  23  29
 21            31  37  41  43  47  53  59  61  67  71
 22            73  79  83  89  97  101 103 107 109 113
 23            127 131 137 139 149 151 157 163 167 173
 24            179 181 191 193 197 199 211 223 227 229
 25            233 239 241 251 257 263 269 271 277 281
 26            283 293 307 311 313 317 331 337 347 349
 27            353 359 367 373 379 383 389 397 401 409
 28            419 421 431 433 439 443 449 457 461 463
 29            467 479 487 491 499 503 509 521 523 541
 30            547 557 563 569 571 577 587 593 599 601
 31            607 613 617 619 631 641 643 647 653 659
 32            661 673 677 683 691 701 709 719 727 733
 33            739 743 751 757 761 769 773 787 797 809
 34            811 821 823 827 829 839 853 857 859 863
 35            877 881 883 887 907 911 919 929 937 941
 36            947 953 967 971 977 983 991 997 1009
 37            1013 1019 1021 1031 1033 1039 1049 1051
 38            1061 1063 1069 1087 1091 1093 1097 1103
 39            1109 1117 1123 1129 1151 1153 1163 1171
 40            1181 1187 1193 1201 1213 1217 1223 1229
 41            1231 1237 1249 1259 1277 1279 1283 1289
 42        */
 43
 44        // Each list has a product < 2^31
 145        internal static readonly int[][] primeLists = new int[][]
 146        {
 147            new int[]{ 3, 5, 7, 11, 13, 17, 19, 23 },
 148            new int[]{ 29, 31, 37, 41, 43 },
 149            new int[]{ 47, 53, 59, 61, 67 },
 150            new int[]{ 71, 73, 79, 83 },
 151            new int[]{ 89, 97, 101, 103 },
 152
 153            new int[]{ 107, 109, 113, 127 },
 154            new int[]{ 131, 137, 139, 149 },
 155            new int[]{ 151, 157, 163, 167 },
 156            new int[]{ 173, 179, 181, 191 },
 157            new int[]{ 193, 197, 199, 211 },
 158
 159            new int[]{ 223, 227, 229 },
 160            new int[]{ 233, 239, 241 },
 161            new int[]{ 251, 257, 263 },
 162            new int[]{ 269, 271, 277 },
 163            new int[]{ 281, 283, 293 },
 164
 165            new int[]{ 307, 311, 313 },
 166            new int[]{ 317, 331, 337 },
 167            new int[]{ 347, 349, 353 },
 168            new int[]{ 359, 367, 373 },
 169            new int[]{ 379, 383, 389 },
 170
 171            new int[]{ 397, 401, 409 },
 172            new int[]{ 419, 421, 431 },
 173            new int[]{ 433, 439, 443 },
 174            new int[]{ 449, 457, 461 },
 175            new int[]{ 463, 467, 479 },
 176
 177            new int[]{ 487, 491, 499 },
 178            new int[]{ 503, 509, 521 },
 179            new int[]{ 523, 541, 547 },
 180            new int[]{ 557, 563, 569 },
 181            new int[]{ 571, 577, 587 },
 182
 183            new int[]{ 593, 599, 601 },
 184            new int[]{ 607, 613, 617 },
 185            new int[]{ 619, 631, 641 },
 186            new int[]{ 643, 647, 653 },
 187            new int[]{ 659, 661, 673 },
 188
 189            new int[]{ 677, 683, 691 },
 190            new int[]{ 701, 709, 719 },
 191            new int[]{ 727, 733, 739 },
 192            new int[]{ 743, 751, 757 },
 193            new int[]{ 761, 769, 773 },
 194
 195            new int[]{ 787, 797, 809 },
 196            new int[]{ 811, 821, 823 },
 197            new int[]{ 827, 829, 839 },
 198            new int[]{ 853, 857, 859 },
 199            new int[]{ 863, 877, 881 },
 1100
 1101            new int[]{ 883, 887, 907 },
 1102            new int[]{ 911, 919, 929 },
 1103            new int[]{ 937, 941, 947 },
 1104            new int[]{ 953, 967, 971 },
 1105            new int[]{ 977, 983, 991 },
 1106
 1107            new int[]{ 997, 1009, 1013 },
 1108            new int[]{ 1019, 1021, 1031 },
 1109            new int[]{ 1033, 1039, 1049 },
 1110            new int[]{ 1051, 1061, 1063 },
 1111            new int[]{ 1069, 1087, 1091 },
 1112
 1113            new int[]{ 1093, 1097, 1103 },
 1114            new int[]{ 1109, 1117, 1123 },
 1115            new int[]{ 1129, 1151, 1153 },
 1116            new int[]{ 1163, 1171, 1181 },
 1117            new int[]{ 1187, 1193, 1201 },
 1118
 1119            new int[]{ 1213, 1217, 1223 },
 1120            new int[]{ 1229, 1231, 1237 },
 1121            new int[]{ 1249, 1259, 1277 },
 1122            new int[]{ 1279, 1283, 1289 },
 1123        };
 124
 125        internal static readonly int[] primeProducts;
 126
 127        private const long IMASK = 0xFFFFFFFFL;
 128        private const ulong UIMASK = 0xFFFFFFFFUL;
 129
 1130        private static readonly int[] ZeroMagnitude = new int[0];
 1131        private static readonly byte[] ZeroEncoding = new byte[0];
 132
 1133        private static readonly BigInteger[] SMALL_CONSTANTS = new BigInteger[17];
 134        public static readonly BigInteger Zero;
 135        public static readonly BigInteger One;
 136        public static readonly BigInteger Two;
 137        public static readonly BigInteger Three;
 138        public static readonly BigInteger Ten;
 139
 140        //private readonly static byte[] BitCountTable =
 141        //{
 142        //    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
 143        //    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 144        //    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 145        //    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 146        //    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 147        //    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 148        //    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 149        //    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 150        //    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 151        //    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 152        //    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 153        //    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 154        //    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 155        //    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 156        //    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 157        //    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
 158        //};
 159
 1160        private readonly static byte[] BitLengthTable =
 1161        {
 1162            0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
 1163            5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 1164            6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 1165            6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 1166            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 1167            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 1168            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 1169            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 1170            8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 1171            8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 1172            8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 1173            8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 1174            8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 1175            8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 1176            8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 1177            8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
 1178        };
 179
 180        // TODO Parse radix-2 64 bits at a time and radix-8 63 bits at a time
 181        private const int chunk2 = 1, chunk8 = 1, chunk10 = 19, chunk16 = 16;
 182        private static readonly BigInteger radix2, radix2E, radix8, radix8E, radix10, radix10E, radix16, radix16E;
 183
 1184        private static readonly SecureRandom RandomSource = new SecureRandom();
 185
 186        /*
 187         * These are the threshold bit-lengths (of an exponent) where we increase the window size.
 188         * They are calculated according to the expected savings in multiplications.
 189         * Some squares will also be saved on average, but we offset these against the extra storage costs.
 190         */
 1191        private static readonly int[] ExpWindowThresholds = { 7, 25, 81, 241, 673, 1793, 4609, Int32.MaxValue };
 192
 193        private const int BitsPerByte = 8;
 194        private const int BitsPerInt = 32;
 195        private const int BytesPerInt = 4;
 196
 197        static BigInteger()
 1198        {
 1199            Zero = new BigInteger(0, ZeroMagnitude, false);
 2200            Zero.nBits = 0; Zero.nBitLength = 0;
 201
 1202            SMALL_CONSTANTS[0] = Zero;
 34203            for (uint i = 1; i < SMALL_CONSTANTS.Length; ++i)
 16204            {
 16205                SMALL_CONSTANTS[i] = CreateUValueOf(i);
 16206            }
 207
 1208            One = SMALL_CONSTANTS[1];
 1209            Two = SMALL_CONSTANTS[2];
 1210            Three = SMALL_CONSTANTS[3];
 1211            Ten = SMALL_CONSTANTS[10];
 212
 1213            radix2 = ValueOf(2);
 1214            radix2E = radix2.Pow(chunk2);
 215
 1216            radix8 = ValueOf(8);
 1217            radix8E = radix8.Pow(chunk8);
 218
 1219            radix10 = ValueOf(10);
 1220            radix10E = radix10.Pow(chunk10);
 221
 1222            radix16 = ValueOf(16);
 1223            radix16E = radix16.Pow(chunk16);
 224
 1225            primeProducts = new int[primeLists.Length];
 226
 130227            for (int i = 0; i < primeLists.Length; ++i)
 64228            {
 64229                int[] primeList = primeLists[i];
 64230                int product = primeList[0];
 416231                for (int j = 1; j < primeList.Length; ++j)
 144232                {
 144233                    product *= primeList[j];
 144234                }
 64235                primeProducts[i] = product;
 64236            }
 1237        }
 238
 239        private int[] magnitude; // array of ints with [0] being the most significant
 240        private int sign; // -1 means -ve; +1 means +ve; 0 means 0;
 579136241        private int nBits = -1; // cache BitCount() value
 579136242        private int nBitLength = -1; // cache BitLength() value
 579136243        private int mQuote = 0; // -m^(-1) mod b, b = 2^32 (see Montgomery mult.), 0 when uninitialised
 244
 245        private static int GetByteLength(
 246            int nBits)
 438247        {
 438248            return (nBits + BitsPerByte - 1) / BitsPerByte;
 438249        }
 250
 251        internal static BigInteger Arbitrary(int sizeInBits)
 0252        {
 0253            return new BigInteger(sizeInBits, RandomSource);
 0254        }
 255
 577876256        private BigInteger(
 577876257            int    signum,
 577876258            int[]  mag,
 577876259            bool  checkMag)
 577876260        {
 577876261            if (checkMag)
 343812262            {
 343812263                int i = 0;
 455650264                while (i < mag.Length && mag[i] == 0)
 111838265                {
 111838266                    ++i;
 111838267                }
 268
 343812269                if (i == mag.Length)
 0270                {
 0271                    this.sign = 0;
 0272                    this.magnitude = ZeroMagnitude;
 0273                }
 274                else
 343812275                {
 343812276                    this.sign = signum;
 277
 343812278                    if (i == 0)
 247602279                    {
 247602280                        this.magnitude = mag;
 247602281                    }
 282                    else
 96210283                    {
 284                        // strip leading 0 words
 96210285                        this.magnitude = new int[mag.Length - i];
 96210286                        Array.Copy(mag, i, this.magnitude, 0, this.magnitude.Length);
 96210287                    }
 343812288                }
 343812289            }
 290            else
 234064291            {
 234064292                this.sign = signum;
 234064293                this.magnitude = mag;
 234064294            }
 577876295        }
 296
 297        public BigInteger(
 298            string value)
 0299            : this(value, 10)
 0300        {
 0301        }
 302
 0303        public BigInteger(
 0304            string  str,
 0305            int    radix)
 0306        {
 0307            if (str.Length == 0)
 0308                throw new FormatException("Zero length BigInteger");
 309
 310            NumberStyles style;
 311            int chunk;
 312            BigInteger r;
 313            BigInteger rE;
 314
 0315            switch (radix)
 316            {
 317                case 2:
 318                    // Is there anyway to restrict to binary digits?
 0319                    style = NumberStyles.Integer;
 0320                    chunk = chunk2;
 0321                    r = radix2;
 0322                    rE = radix2E;
 0323                    break;
 324                case 8:
 325                    // Is there anyway to restrict to octal digits?
 0326                    style = NumberStyles.Integer;
 0327                    chunk = chunk8;
 0328                    r = radix8;
 0329                    rE = radix8E;
 0330                    break;
 331                case 10:
 332                    // This style seems to handle spaces and minus sign already (our processing redundant?)
 0333                    style = NumberStyles.Integer;
 0334                    chunk = chunk10;
 0335                    r = radix10;
 0336                    rE = radix10E;
 0337                    break;
 338                case 16:
 339                    // TODO Should this be HexNumber?
 0340                    style = NumberStyles.AllowHexSpecifier;
 0341                    chunk = chunk16;
 0342                    r = radix16;
 0343                    rE = radix16E;
 0344                    break;
 345                default:
 0346                    throw new FormatException("Only bases 2, 8, 10, or 16 allowed");
 347            }
 348
 349
 0350            int index = 0;
 0351            sign = 1;
 352
 0353            if (str[0] == '-')
 0354            {
 0355                if (str.Length == 1)
 0356                    throw new FormatException("Zero length BigInteger");
 357
 0358                sign = -1;
 0359                index = 1;
 0360            }
 361
 362            // strip leading zeros from the string str
 0363            while (index < str.Length && Int32.Parse(str[index].ToString(), style) == 0)
 0364            {
 0365                index++;
 0366            }
 367
 0368            if (index >= str.Length)
 0369            {
 370                // zero value - we're done
 0371                sign = 0;
 0372                magnitude = ZeroMagnitude;
 0373                return;
 374            }
 375
 376            //////
 377            // could we work out the max number of ints required to store
 378            // str.Length digits in the given base, then allocate that
 379            // storage in one hit?, then Generate the magnitude in one hit too?
 380            //////
 381
 0382            BigInteger b = Zero;
 383
 384
 0385            int next = index + chunk;
 386
 0387            if (next <= str.Length)
 0388            {
 389                do
 0390                {
 0391                    string s = str.Substring(index, chunk);
 0392                    ulong i = ulong.Parse(s, style);
 0393                    BigInteger bi = CreateUValueOf(i);
 394
 0395                    switch (radix)
 396                    {
 397                        case 2:
 398                            // TODO Need this because we are parsing in radix 10 above
 0399                            if (i >= 2)
 0400                                throw new FormatException("Bad character in radix 2 string: " + s);
 401
 402                            // TODO Parse 64 bits at a time
 0403                            b = b.ShiftLeft(1);
 0404                            break;
 405                        case 8:
 406                            // TODO Need this because we are parsing in radix 10 above
 0407                            if (i >= 8)
 0408                                throw new FormatException("Bad character in radix 8 string: " + s);
 409
 410                            // TODO Parse 63 bits at a time
 0411                            b = b.ShiftLeft(3);
 0412                            break;
 413                        case 16:
 0414                            b = b.ShiftLeft(64);
 0415                            break;
 416                        default:
 0417                            b = b.Multiply(rE);
 0418                            break;
 419                    }
 420
 0421                    b = b.Add(bi);
 422
 0423                    index = next;
 0424                    next += chunk;
 0425                }
 0426                while (next <= str.Length);
 0427            }
 428
 0429            if (index < str.Length)
 0430            {
 0431                string s = str.Substring(index);
 0432                ulong i = ulong.Parse(s, style);
 0433                BigInteger bi = CreateUValueOf(i);
 434
 0435                if (b.sign > 0)
 0436                {
 0437                    if (radix == 2)
 0438                    {
 439                        // NB: Can't reach here since we are parsing one char at a time
 0440                        Debug.Assert(false);
 441
 442                        // TODO Parse all bits at once
 443//            b = b.ShiftLeft(s.Length);
 0444                    }
 0445                    else if (radix == 8)
 0446                    {
 447                        // NB: Can't reach here since we are parsing one char at a time
 0448                        Debug.Assert(false);
 449
 450                        // TODO Parse all bits at once
 451//            b = b.ShiftLeft(s.Length * 3);
 0452                    }
 0453                    else if (radix == 16)
 0454                    {
 0455                        b = b.ShiftLeft(s.Length << 2);
 0456                    }
 457                    else
 0458                    {
 0459                        b = b.Multiply(r.Pow(s.Length));
 0460                    }
 461
 0462                    b = b.Add(bi);
 0463                }
 464                else
 0465                {
 0466                    b = bi;
 0467                }
 0468            }
 469
 470            // Note: This is the previous (slower) algorithm
 471//      while (index < value.Length)
 472//            {
 473//        char c = value[index];
 474//        string s = c.ToString();
 475//        int i = Int32.Parse(s, style);
 476//
 477//                b = b.Multiply(r).Add(ValueOf(i));
 478//                index++;
 479//            }
 480
 0481            magnitude = b.magnitude;
 0482        }
 483
 484        public BigInteger(
 485            byte[] bytes)
 0486            : this(bytes, 0, bytes.Length)
 0487        {
 0488        }
 489
 0490        public BigInteger(
 0491            byte[]  bytes,
 0492            int    offset,
 0493            int    length)
 0494        {
 0495            if (length == 0)
 0496                throw new FormatException("Zero length BigInteger");
 497
 498            // TODO Move this processing into MakeMagnitude (provide sign argument)
 0499            if ((sbyte)bytes[offset] < 0)
 0500            {
 0501                this.sign = -1;
 502
 0503                int end = offset + length;
 504
 505                int iBval;
 506                // strip leading sign bytes
 0507                for (iBval = offset; iBval < end && ((sbyte)bytes[iBval] == -1); iBval++)
 0508                {
 0509                }
 510
 0511                if (iBval >= end)
 0512                {
 0513                    this.magnitude = One.magnitude;
 0514                }
 515                else
 0516                {
 0517                    int numBytes = end - iBval;
 0518                    byte[] inverse = new byte[numBytes];
 519
 0520                    int index = 0;
 0521                    while (index < numBytes)
 0522                    {
 0523                        inverse[index++] = (byte)~bytes[iBval++];
 0524                    }
 525
 0526                    Debug.Assert(iBval == end);
 527
 0528                    while (inverse[--index] == byte.MaxValue)
 0529                    {
 0530                        inverse[index] = byte.MinValue;
 0531                    }
 532
 0533                    inverse[index]++;
 534
 0535                    this.magnitude = MakeMagnitude(inverse, 0, inverse.Length);
 0536                }
 0537            }
 538            else
 0539            {
 540                // strip leading zero bytes and return magnitude bytes
 0541                this.magnitude = MakeMagnitude(bytes, offset, length);
 0542                this.sign = this.magnitude.Length > 0 ? 1 : 0;
 0543            }
 0544        }
 545
 546        private static int[] MakeMagnitude(
 547            byte[]  bytes,
 548            int    offset,
 549            int    length)
 1260550        {
 1260551            int end = offset + length;
 552
 553            // strip leading zeros
 554            int firstSignificant;
 2798555            for (firstSignificant = offset; firstSignificant < end
 1816556                && bytes[firstSignificant] == 0; firstSignificant++)
 278557            {
 278558            }
 559
 1260560            if (firstSignificant >= end)
 0561            {
 0562                return ZeroMagnitude;
 563            }
 564
 1260565            int nInts = (end - firstSignificant + 3) / BytesPerInt;
 1260566            int bCount = (end - firstSignificant) % BytesPerInt;
 1260567            if (bCount == 0)
 702568            {
 702569                bCount = BytesPerInt;
 702570            }
 571
 1260572            if (nInts < 1)
 0573            {
 0574                return ZeroMagnitude;
 575            }
 576
 1260577            int[] mag = new int[nInts];
 578
 1260579            int v = 0;
 1260580            int magnitudeIndex = 0;
 133632581            for (int i = firstSignificant; i < end; ++i)
 65556582            {
 65556583                v <<= 8;
 65556584                v |= bytes[i] & 0xff;
 65556585                bCount--;
 65556586                if (bCount <= 0)
 16730587                {
 16730588                    mag[magnitudeIndex] = v;
 16730589                    magnitudeIndex++;
 16730590                    bCount = BytesPerInt;
 16730591                    v = 0;
 16730592                }
 65556593            }
 594
 1260595            if (magnitudeIndex < mag.Length)
 0596            {
 0597                mag[magnitudeIndex] = v;
 0598            }
 599
 1260600            return mag;
 1260601        }
 602
 603        public BigInteger(
 604            int    sign,
 605            byte[]  bytes)
 1227606            : this(sign, bytes, 0, bytes.Length)
 1227607        {
 1227608        }
 609
 1251610        public BigInteger(
 1251611            int    sign,
 1251612            byte[]  bytes,
 1251613            int    offset,
 1251614            int    length)
 1251615        {
 1251616            if (sign < -1 || sign > 1)
 0617                throw new FormatException("Invalid sign value");
 618
 1251619            if (sign == 0)
 0620            {
 0621                this.sign = 0;
 0622                this.magnitude = ZeroMagnitude;
 0623            }
 624            else
 1251625            {
 626                // copy bytes
 1251627                this.magnitude = MakeMagnitude(bytes, offset, length);
 1251628                this.sign = this.magnitude.Length < 1 ? 0 : sign;
 1251629            }
 1251630        }
 631
 9632        public BigInteger(
 9633            int    sizeInBits,
 9634            Random  random)
 9635        {
 9636            if (sizeInBits < 0)
 0637                throw new ArgumentException("sizeInBits must be non-negative");
 638
 9639            this.nBits = -1;
 9640            this.nBitLength = -1;
 641
 9642            if (sizeInBits == 0)
 0643            {
 0644                this.sign = 0;
 0645                this.magnitude = ZeroMagnitude;
 0646                return;
 647            }
 648
 9649            int nBytes = GetByteLength(sizeInBits);
 9650            byte[] b = new byte[nBytes];
 651#pragma warning disable CA5394 // Do not use insecure randomness
 9652            random.NextBytes(b);
 653#pragma warning restore CA5394 // Do not use insecure randomness
 654
 655            // strip off any excess bits in the MSB
 9656            int xBits = BitsPerByte * nBytes - sizeInBits;
 9657            b[0] &= (byte)(255U >> xBits);
 658
 9659            this.magnitude = MakeMagnitude(b, 0, b.Length);
 9660            this.sign = this.magnitude.Length < 1 ? 0 : 1;
 9661        }
 662
 663#pragma warning disable CA5394 // Do not use insecure randomness
 0664        public BigInteger(
 0665            int    bitLength,
 0666            int    certainty,
 0667            Random  random)
 0668        {
 0669            if (bitLength < 2)
 0670                throw new ArithmeticException("bitLength < 2");
 671
 0672            this.sign = 1;
 0673            this.nBitLength = bitLength;
 674
 0675            if (bitLength == 2)
 0676            {
 0677                this.magnitude = random.Next(2) == 0
 0678                    ?  Two.magnitude
 0679                    :  Three.magnitude;
 0680                return;
 681            }
 682
 0683            int nBytes = GetByteLength(bitLength);
 0684            byte[] b = new byte[nBytes];
 685
 0686            int xBits = BitsPerByte * nBytes - bitLength;
 0687            byte mask = (byte)(255U >> xBits);
 0688            byte lead = (byte)(1 << (7 - xBits));
 689
 690            for (;;)
 0691            {
 0692                random.NextBytes(b);
 693
 694                // strip off any excess bits in the MSB
 0695                b[0] &= mask;
 696
 697                // ensure the leading bit is 1 (to meet the strength requirement)
 0698                b[0] |= lead;
 699
 700                // ensure the trailing bit is 1 (i.e. must be odd)
 0701                b[nBytes - 1] |= 1;
 702
 0703                this.magnitude = MakeMagnitude(b, 0, b.Length);
 0704                this.nBits = -1;
 0705                this.mQuote = 0;
 706
 0707                if (certainty < 1)
 0708                    break;
 709
 0710                if (CheckProbablePrime(certainty, random, true))
 0711                    break;
 712
 0713                for (int j = 1; j < (magnitude.Length - 1); ++j)
 0714                {
 0715                    this.magnitude[j] ^= random.Next();
 716
 0717                    if (CheckProbablePrime(certainty, random, true))
 0718                        return;
 0719                }
 0720            }
 0721        }
 722#pragma warning restore CA5394 // Do not use insecure randomness
 723
 724        public BigInteger Abs()
 91565725        {
 91565726            return sign >= 0 ? this : Negate();
 91565727        }
 728
 729        /**
 730         * return a = a + b - b preserved.
 731         */
 732        private static int[] AddMagnitudes(
 733            int[] a,
 734            int[] b)
 106094735        {
 106094736            int tI = a.Length - 1;
 106094737            int vI = b.Length - 1;
 106094738            long m = 0;
 739
 1480935740            while (vI >= 0)
 1374841741            {
 1374841742                m += ((long)(uint)a[tI] + (long)(uint)b[vI--]);
 1374841743                a[tI--] = (int)m;
 1374841744                m = (long)((ulong)m >> 32);
 1374841745            }
 746
 106094747            if (m != 0)
 26918748            {
 26918749                while (tI >= 0 && ++a[tI--] == 0)
 0750                {
 0751                }
 26918752            }
 753
 106094754            return a;
 106094755        }
 756
 757        public BigInteger Add(
 758            BigInteger value)
 116182759        {
 116182760            if (this.sign == 0)
 0761                return value;
 762
 116182763            if (this.sign != value.sign)
 10248764            {
 10248765                if (value.sign == 0)
 0766                    return this;
 767
 10248768                if (value.sign < 0)
 0769                    return Subtract(value.Negate());
 770
 10248771                return value.Subtract(Negate());
 772            }
 773
 105934774            return AddToMagnitude(value.magnitude);
 116182775        }
 776
 777        private BigInteger AddToMagnitude(
 778            int[] magToAdd)
 105934779        {
 780            int[] big, small;
 105934781            if (this.magnitude.Length < magToAdd.Length)
 20305782            {
 20305783                big = magToAdd;
 20305784                small = this.magnitude;
 20305785            }
 786            else
 85629787            {
 85629788                big = this.magnitude;
 85629789                small = magToAdd;
 85629790            }
 791
 792            // Conservatively avoid over-allocation when no overflow possible
 105934793            uint limit = uint.MaxValue;
 105934794            if (big.Length == small.Length)
 66304795                limit -= (uint) small[0];
 796
 105934797            bool possibleOverflow = (uint) big[0] >= limit;
 798
 799            int[] bigCopy;
 105934800            if (possibleOverflow)
 11601801            {
 11601802                bigCopy = new int[big.Length + 1];
 11601803                big.CopyTo(bigCopy, 1);
 11601804            }
 805            else
 94333806            {
 94333807                bigCopy = (int[]) big.Clone();
 94333808            }
 809
 105934810            bigCopy = AddMagnitudes(bigCopy, small);
 811
 105934812            return new BigInteger(this.sign, bigCopy, possibleOverflow);
 105934813        }
 814
 815        public BigInteger And(
 816            BigInteger value)
 0817        {
 0818            if (this.sign == 0 || value.sign == 0)
 0819            {
 0820                return Zero;
 821            }
 822
 0823            int[] aMag = this.sign > 0
 0824                ? this.magnitude
 0825                : Add(One).magnitude;
 826
 0827            int[] bMag = value.sign > 0
 0828                ? value.magnitude
 0829                : value.Add(One).magnitude;
 830
 0831            bool resultNeg = sign < 0 && value.sign < 0;
 0832            int resultLength = System.Math.Max(aMag.Length, bMag.Length);
 0833            int[] resultMag = new int[resultLength];
 834
 0835            int aStart = resultMag.Length - aMag.Length;
 0836            int bStart = resultMag.Length - bMag.Length;
 837
 0838            for (int i = 0; i < resultMag.Length; ++i)
 0839            {
 0840                int aWord = i >= aStart ? aMag[i - aStart] : 0;
 0841                int bWord = i >= bStart ? bMag[i - bStart] : 0;
 842
 0843                if (this.sign < 0)
 0844                {
 0845                    aWord = ~aWord;
 0846                }
 847
 0848                if (value.sign < 0)
 0849                {
 0850                    bWord = ~bWord;
 0851                }
 852
 0853                resultMag[i] = aWord & bWord;
 854
 0855                if (resultNeg)
 0856                {
 0857                    resultMag[i] = ~resultMag[i];
 0858                }
 0859            }
 860
 0861            BigInteger result = new BigInteger(1, resultMag, true);
 862
 863            // TODO Optimise this case
 0864            if (resultNeg)
 0865            {
 0866                result = result.Not();
 0867            }
 868
 0869            return result;
 0870        }
 871
 872        public BigInteger AndNot(
 873            BigInteger val)
 0874        {
 0875            return And(val.Not());
 0876        }
 877
 878        public int BitCount
 879        {
 880            get
 9881            {
 9882                if (nBits == -1)
 9883                {
 9884                    if (sign < 0)
 0885                    {
 886                        // TODO Optimise this case
 0887                        nBits = Not().BitCount;
 0888                    }
 889                    else
 9890                    {
 9891                        int sum = 0;
 246892                        for (int i = 0; i < magnitude.Length; ++i)
 114893                        {
 114894                            sum += BitCnt(magnitude[i]);
 114895                        }
 9896                        nBits = sum;
 9897                    }
 9898                }
 899
 9900                return nBits;
 9901            }
 902        }
 903
 904        public static int BitCnt(int i)
 114905        {
 114906            uint u = (uint)i;
 114907            u = u - ((u >> 1) & 0x55555555);
 114908            u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
 114909            u = (u + (u >> 4)) & 0x0f0f0f0f;
 114910            u += (u >> 8);
 114911            u += (u >> 16);
 114912            u &= 0x3f;
 114913            return (int)u;
 114914        }
 915
 916        private static int CalcBitLength(int sign, int indx, int[]  mag)
 142382917        {
 918            for (;;)
 142382919            {
 142382920                if (indx >= mag.Length)
 0921                    return 0;
 922
 142382923                if (mag[indx] != 0)
 142382924                    break;
 925
 0926                ++indx;
 0927            }
 928
 929            // bit length for everything after the first int
 142382930            int bitLength = 32 * ((mag.Length - indx) - 1);
 931
 932            // and determine bitlength of first int
 142382933            int firstMag = mag[indx];
 142382934            bitLength += BitLen(firstMag);
 935
 936            // Check for negative powers of two
 142382937            if (sign < 0 && ((firstMag & -firstMag) == firstMag))
 0938            {
 939                do
 0940                {
 0941                    if (++indx >= mag.Length)
 0942                    {
 0943                        --bitLength;
 0944                        break;
 945                    }
 0946                }
 0947                while (mag[indx] == 0);
 0948            }
 949
 142382950            return bitLength;
 142382951        }
 952
 953        public int BitLength
 954        {
 955            get
 461106956            {
 461106957                if (nBitLength == -1)
 142380958                {
 142380959                    nBitLength = sign == 0
 142380960                        ? 0
 142380961                        : CalcBitLength(sign, 0, magnitude);
 142380962                }
 963
 461106964                return nBitLength;
 461106965            }
 966        }
 967
 968        //
 969        // BitLen(value) is the number of bits in value.
 970        //
 971        internal static int BitLen(int w)
 142542972        {
 142542973            uint v = (uint)w;
 142542974            uint t = v >> 24;
 142542975            if (t != 0)
 84433976                return 24 + BitLengthTable[t];
 58109977            t = v >> 16;
 58109978            if (t != 0)
 14307979                return 16 + BitLengthTable[t];
 43802980            t = v >> 8;
 43802981            if (t != 0)
 33600982                return 8 + BitLengthTable[t];
 10202983            return BitLengthTable[v];
 142542984        }
 985
 986        private bool QuickPow2Check()
 321615987        {
 321615988            return sign > 0 && nBits == 1;
 321615989        }
 990
 991        public int CompareTo(
 992            object obj)
 0993        {
 0994            return CompareTo((BigInteger)obj);
 0995        }
 996
 997        /**
 998         * unsigned comparison on two arrays - note the arrays may
 999         * start with leading zeros.
 1000         */
 1001        private static int CompareTo(
 1002            int    xIndx,
 1003            int[]  x,
 1004            int    yIndx,
 1005            int[]  y)
 01006        {
 01007            while (xIndx != x.Length && x[xIndx] == 0)
 01008            {
 01009                xIndx++;
 01010            }
 1011
 01012            while (yIndx != y.Length && y[yIndx] == 0)
 01013            {
 01014                yIndx++;
 01015            }
 1016
 01017            return CompareNoLeadingZeroes(xIndx, x, yIndx, y);
 01018        }
 1019
 1020        private static int CompareNoLeadingZeroes(
 1021            int    xIndx,
 1022            int[]  x,
 1023            int    yIndx,
 1024            int[]  y)
 4046541025        {
 4046541026            int diff = (x.Length - y.Length) - (xIndx - yIndx);
 1027
 4046541028            if (diff != 0)
 1172711029            {
 1172711030                return diff < 0 ? -1 : 1;
 1031            }
 1032
 1033            // lengths of magnitudes the same, test the magnitude values
 1034
 3112701035            while (xIndx < x.Length)
 3112701036            {
 3112701037                uint v1 = (uint)x[xIndx++];
 3112701038                uint v2 = (uint)y[yIndx++];
 1039
 3112701040                if (v1 != v2)
 2873831041                    return v1 < v2 ? -1 : 1;
 238871042            }
 1043
 01044            return 0;
 4046541045        }
 1046
 1047        public int CompareTo(
 1048            BigInteger value)
 2354131049        {
 2354131050            return sign < value.sign ? -1
 2354131051                : sign > value.sign ? 1
 2354131052                : sign == 0 ? 0
 2354131053                : sign * CompareNoLeadingZeroes(0, magnitude, 0, value.magnitude);
 2354131054        }
 1055
 1056        /**
 1057         * return z = x / y - done in place (z value preserved, x contains the
 1058         * remainder)
 1059         */
 1060        private int[] Divide(
 1061            int[]  x,
 1062            int[]  y)
 11063        {
 11064            int xStart = 0;
 11065            while (xStart < x.Length && x[xStart] == 0)
 01066            {
 01067                ++xStart;
 01068            }
 1069
 11070            int yStart = 0;
 11071            while (yStart < y.Length && y[yStart] == 0)
 01072            {
 01073                ++yStart;
 01074            }
 1075
 11076            Debug.Assert(yStart < y.Length);
 1077
 11078            int xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
 1079            int[] count;
 1080
 11081            if (xyCmp > 0)
 11082            {
 11083                int yBitLength = CalcBitLength(1, yStart, y);
 11084                int xBitLength = CalcBitLength(1, xStart, x);
 11085                int shift = xBitLength - yBitLength;
 1086
 1087                int[] iCount;
 11088                int iCountStart = 0;
 1089
 1090                int[] c;
 11091                int cStart = 0;
 11092                int cBitLength = yBitLength;
 11093                if (shift > 0)
 11094                {
 1095//          iCount = ShiftLeft(One.magnitude, shift);
 11096                    iCount = new int[(shift >> 5) + 1];
 11097                    iCount[0] = 1 << (shift % 32);
 1098
 11099                    c = ShiftLeft(y, shift);
 11100                    cBitLength += shift;
 11101                }
 1102                else
 01103                {
 01104                    iCount = new int[] { 1 };
 1105
 01106                    int len = y.Length - yStart;
 01107                    c = new int[len];
 01108                    Array.Copy(y, yStart, c, 0, len);
 01109                }
 1110
 11111                count = new int[iCount.Length];
 1112
 1113                for (;;)
 1661114                {
 1661115                    if (cBitLength < xBitLength
 1661116                        || CompareNoLeadingZeroes(xStart, x, cStart, c) >= 0)
 1601117                    {
 1601118                        Subtract(xStart, x, cStart, c);
 1601119                        AddMagnitudes(count, iCount);
 1120
 1691121                        while (x[xStart] == 0)
 91122                        {
 91123                            if (++xStart == x.Length)
 01124                                return count;
 91125                        }
 1126
 1127                        //xBitLength = CalcBitLength(xStart, x);
 1601128                        xBitLength = 32 * (x.Length - xStart - 1) + BitLen(x[xStart]);
 1129
 1601130                        if (xBitLength <= yBitLength)
 11131                        {
 11132                            if (xBitLength < yBitLength)
 11133                                return count;
 1134
 01135                            xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
 1136
 01137                            if (xyCmp <= 0)
 01138                                break;
 01139                        }
 1591140                    }
 1141
 1651142                    shift = cBitLength - xBitLength;
 1143
 1144                    // NB: The case where c[cStart] is 1-bit is harmless
 1651145                    if (shift == 1)
 41146                    {
 41147                        uint firstC = (uint) c[cStart] >> 1;
 41148                        uint firstX = (uint) x[xStart];
 41149                        if (firstC > firstX)
 01150                            ++shift;
 41151                    }
 1152
 1651153                    if (shift < 2)
 1631154                    {
 1631155                        ShiftRightOneInPlace(cStart, c);
 1631156                        --cBitLength;
 1631157                        ShiftRightOneInPlace(iCountStart, iCount);
 1631158                    }
 1159                    else
 21160                    {
 21161                        ShiftRightInPlace(cStart, c, shift);
 21162                        cBitLength -= shift;
 21163                        ShiftRightInPlace(iCountStart, iCount, shift);
 21164                    }
 1165
 1166                    //cStart = c.Length - ((cBitLength + 31) / 32);
 1741167                    while (c[cStart] == 0)
 91168                    {
 91169                        ++cStart;
 91170                    }
 1171
 1731172                    while (iCount[iCountStart] == 0)
 81173                    {
 81174                        ++iCountStart;
 81175                    }
 1651176                }
 01177            }
 1178            else
 01179            {
 01180                count = new int[1];
 01181            }
 1182
 01183            if (xyCmp == 0)
 01184            {
 01185                AddMagnitudes(count, One.magnitude);
 01186                Array.Clear(x, xStart, x.Length - xStart);
 01187            }
 1188
 01189            return count;
 11190        }
 1191
 1192        public BigInteger Divide(
 1193            BigInteger val)
 11194        {
 11195            if (val.sign == 0)
 01196                throw new ArithmeticException("Division by zero error");
 1197
 11198            if (sign == 0)
 01199                return Zero;
 1200
 11201            if (val.QuickPow2Check()) // val is power of two
 01202            {
 01203                BigInteger result = this.Abs().ShiftRight(val.Abs().BitLength - 1);
 01204                return val.sign == this.sign ? result : result.Negate();
 1205            }
 1206
 11207            int[] mag = (int[]) this.magnitude.Clone();
 1208
 11209            return new BigInteger(this.sign * val.sign, Divide(mag, val.magnitude), true);
 11210        }
 1211
 1212        public BigInteger[] DivideAndRemainder(
 1213            BigInteger val)
 01214        {
 01215            if (val.sign == 0)
 01216                throw new ArithmeticException("Division by zero error");
 1217
 01218            BigInteger[] biggies = new BigInteger[2];
 1219
 01220            if (sign == 0)
 01221            {
 01222                biggies[0] = Zero;
 01223                biggies[1] = Zero;
 01224            }
 01225            else if (val.QuickPow2Check()) // val is power of two
 01226            {
 01227                int e = val.Abs().BitLength - 1;
 01228                BigInteger quotient = this.Abs().ShiftRight(e);
 01229                int[] remainder = this.LastNBits(e);
 1230
 01231                biggies[0] = val.sign == this.sign ? quotient : quotient.Negate();
 01232                biggies[1] = new BigInteger(this.sign, remainder, true);
 01233            }
 1234            else
 01235            {
 01236                int[] remainder = (int[]) this.magnitude.Clone();
 01237                int[] quotient = Divide(remainder, val.magnitude);
 1238
 01239                biggies[0] = new BigInteger(this.sign * val.sign, quotient, true);
 01240                biggies[1] = new BigInteger(this.sign, remainder, true);
 01241            }
 1242
 01243            return biggies;
 01244        }
 1245
 1246        public override bool Equals(
 1247            object obj)
 471711248        {
 471711249            if (obj == this)
 301250                return true;
 1251
 471411252            BigInteger biggie = obj as BigInteger;
 471411253            if (biggie == null)
 01254                return false;
 1255
 471411256            return sign == biggie.sign && IsEqualMagnitude(biggie);
 471711257        }
 1258
 1259        private bool IsEqualMagnitude(BigInteger x)
 471411260        {
 471411261            int[] xMag = x.magnitude;
 471411262            if (magnitude.Length != x.magnitude.Length)
 211041263                return false;
 1052361264            for (int i = 0; i < magnitude.Length; i++)
 265811265            {
 265811266                if (magnitude[i] != x.magnitude[i])
 01267                    return false;
 265811268            }
 260371269            return true;
 471411270        }
 1271
 1272        public BigInteger Gcd(
 1273            BigInteger value)
 01274        {
 01275            if (value.sign == 0)
 01276                return Abs();
 1277
 01278            if (sign == 0)
 01279                return value.Abs();
 1280
 1281            BigInteger r;
 01282            BigInteger u = this;
 01283            BigInteger v = value;
 1284
 01285            while (v.sign != 0)
 01286            {
 01287                r = u.Mod(v);
 01288                u = v;
 01289                v = r;
 01290            }
 1291
 01292            return u;
 01293        }
 1294
 1295        public override int GetHashCode()
 01296        {
 01297            int hc = magnitude.Length;
 01298            if (magnitude.Length > 0)
 01299            {
 01300                hc ^= magnitude[0];
 1301
 01302                if (magnitude.Length > 1)
 01303                {
 01304                    hc ^= magnitude[magnitude.Length - 1];
 01305                }
 01306            }
 1307
 01308            return sign < 0 ? ~hc : hc;
 01309        }
 1310
 1311        // TODO Make public?
 1312        private BigInteger Inc()
 01313        {
 01314            if (this.sign == 0)
 01315                return One;
 1316
 01317            if (this.sign < 0)
 01318                return new BigInteger(-1, doSubBigLil(this.magnitude, One.magnitude), true);
 1319
 01320            return AddToMagnitude(One.magnitude);
 01321        }
 1322
 1323        public int IntValue
 1324        {
 1325            get
 14461326            {
 14461327                if (sign == 0)
 21328                    return 0;
 1329
 14441330                int n = magnitude.Length;
 1331
 14441332                int v = magnitude[n - 1];
 1333
 14441334                return sign < 0 ? -v : v;
 14461335            }
 1336        }
 1337
 1338        /**
 1339         * return whether or not a BigInteger is probably prime with a
 1340         * probability of 1 - (1/2)**certainty.
 1341         * <p>From Knuth Vol 2, pg 395.</p>
 1342         */
 1343        public bool IsProbablePrime(int certainty)
 01344        {
 01345            return IsProbablePrime(certainty, false);
 01346        }
 1347
 1348        internal bool IsProbablePrime(int certainty, bool randomlySelected)
 01349        {
 01350            if (certainty <= 0)
 01351                return true;
 1352
 01353            BigInteger n = Abs();
 1354
 01355            if (!n.TestBit(0))
 01356                return n.Equals(Two);
 1357
 01358            if (n.Equals(One))
 01359                return false;
 1360
 01361            return n.CheckProbablePrime(certainty, RandomSource, randomlySelected);
 01362        }
 1363
 1364        private bool CheckProbablePrime(int certainty, Random random, bool randomlySelected)
 01365        {
 01366            Debug.Assert(certainty > 0);
 01367            Debug.Assert(CompareTo(Two) > 0);
 01368            Debug.Assert(TestBit(0));
 1369
 1370
 1371            // Try to reduce the penalty for really small numbers
 01372            int numLists = System.Math.Min(BitLength - 1, primeLists.Length);
 1373
 01374            for (int i = 0; i < numLists; ++i)
 01375            {
 01376                int test = Remainder(primeProducts[i]);
 1377
 01378                int[] primeList = primeLists[i];
 01379                for (int j = 0; j < primeList.Length; ++j)
 01380                {
 01381                    int prime = primeList[j];
 01382                    int qRem = test % prime;
 01383                    if (qRem == 0)
 01384                    {
 1385                        // We may find small numbers in the list
 01386                        return BitLength < 16 && IntValue == prime;
 1387                    }
 01388                }
 01389            }
 1390
 1391
 1392            // TODO Special case for < 10^16 (RabinMiller fixed list)
 1393//      if (BitLength < 30)
 1394//      {
 1395//        RabinMiller against 2, 3, 5, 7, 11, 13, 23 is sufficient
 1396//      }
 1397
 1398
 1399            // TODO Is it worth trying to create a hybrid of these two?
 01400            return RabinMillerTest(certainty, random, randomlySelected);
 1401//      return SolovayStrassenTest(certainty, random);
 1402
 1403//      bool rbTest = RabinMillerTest(certainty, random);
 1404//      bool ssTest = SolovayStrassenTest(certainty, random);
 1405//
 1406//      Debug.Assert(rbTest == ssTest);
 1407//
 1408//      return rbTest;
 01409        }
 1410
 1411        public bool RabinMillerTest(int certainty, Random random)
 01412        {
 01413            return RabinMillerTest(certainty, random, false);
 01414        }
 1415
 1416        internal bool RabinMillerTest(int certainty, Random random, bool randomlySelected)
 01417        {
 01418            int bits = BitLength;
 1419
 01420            Debug.Assert(certainty > 0);
 01421            Debug.Assert(bits > 2);
 01422            Debug.Assert(TestBit(0));
 1423
 01424            int iterations = ((certainty - 1) / 2) + 1;
 01425            if (randomlySelected)
 01426            {
 01427                int itersFor100Cert = bits >= 1024 ?  4
 01428                                    : bits >= 512  ?  8
 01429                                    : bits >= 256  ? 16
 01430                                    : 50;
 1431
 01432                if (certainty < 100)
 01433                {
 01434                    iterations = System.Math.Min(itersFor100Cert, iterations);
 01435                }
 1436                else
 01437                {
 01438                    iterations -= 50;
 01439                    iterations += itersFor100Cert;
 01440                }
 01441            }
 1442
 1443            // let n = 1 + d . 2^s
 01444            BigInteger n = this;
 01445            int s = n.GetLowestSetBitMaskFirst(-1 << 1);
 01446            Debug.Assert(s >= 1);
 01447            BigInteger r = n.ShiftRight(s);
 1448
 1449            // NOTE: Avoid conversion to/from Montgomery form and check for R/-R as result instead
 1450
 01451            BigInteger montRadix = One.ShiftLeft(32 * n.magnitude.Length).Remainder(n);
 01452            BigInteger minusMontRadix = n.Subtract(montRadix);
 1453
 1454            do
 01455            {
 1456                BigInteger a;
 1457                do
 01458                {
 01459                    a = new BigInteger(n.BitLength, random);
 01460                }
 01461                while (a.sign == 0 || a.CompareTo(n) >= 0
 01462                    || a.IsEqualMagnitude(montRadix) || a.IsEqualMagnitude(minusMontRadix));
 1463
 01464                BigInteger y = ModPowMonty(a, r, n, false);
 1465
 01466                if (!y.Equals(montRadix))
 01467                {
 01468                    int j = 0;
 01469                    while (!y.Equals(minusMontRadix))
 01470                    {
 01471                        if (++j == s)
 01472                            return false;
 1473
 01474                        y = ModPowMonty(y, Two, n, false);
 1475
 01476                        if (y.Equals(montRadix))
 01477                            return false;
 01478                    }
 01479                }
 01480            }
 01481            while (--iterations > 0);
 1482
 01483            return true;
 01484        }
 1485
 1486//    private bool SolovayStrassenTest(
 1487//      int    certainty,
 1488//      Random  random)
 1489//    {
 1490//      Debug.Assert(certainty > 0);
 1491//      Debug.Assert(CompareTo(Two) > 0);
 1492//      Debug.Assert(TestBit(0));
 1493//
 1494//      BigInteger n = this;
 1495//      BigInteger nMinusOne = n.Subtract(One);
 1496//      BigInteger e = nMinusOne.ShiftRight(1);
 1497//
 1498//      do
 1499//      {
 1500//        BigInteger a;
 1501//        do
 1502//        {
 1503//          a = new BigInteger(nBitLength, random);
 1504//        }
 1505//        // NB: Spec says 0 < x < n, but 1 is trivial
 1506//        while (a.CompareTo(One) <= 0 || a.CompareTo(n) >= 0);
 1507//
 1508//
 1509//        // TODO Check this is redundant given the way Jacobi() works?
 1510////        if (!a.Gcd(n).Equals(One))
 1511////          return false;
 1512//
 1513//        int x = Jacobi(a, n);
 1514//
 1515//        if (x == 0)
 1516//          return false;
 1517//
 1518//        BigInteger check = a.ModPow(e, n);
 1519//
 1520//        if (x == 1 && !check.Equals(One))
 1521//          return false;
 1522//
 1523//        if (x == -1 && !check.Equals(nMinusOne))
 1524//          return false;
 1525//
 1526//        --certainty;
 1527//      }
 1528//      while (certainty > 0);
 1529//
 1530//      return true;
 1531//    }
 1532//
 1533//    private static int Jacobi(
 1534//      BigInteger  a,
 1535//      BigInteger  b)
 1536//    {
 1537//      Debug.Assert(a.sign >= 0);
 1538//      Debug.Assert(b.sign > 0);
 1539//      Debug.Assert(b.TestBit(0));
 1540//      Debug.Assert(a.CompareTo(b) < 0);
 1541//
 1542//      int totalS = 1;
 1543//      for (;;)
 1544//      {
 1545//        if (a.sign == 0)
 1546//          return 0;
 1547//
 1548//        if (a.Equals(One))
 1549//          break;
 1550//
 1551//        int e = a.GetLowestSetBit();
 1552//
 1553//        int bLsw = b.magnitude[b.magnitude.Length - 1];
 1554//        if ((e & 1) != 0 && ((bLsw & 7) == 3 || (bLsw & 7) == 5))
 1555//          totalS = -totalS;
 1556//
 1557//        // TODO Confirm this is faster than later a1.Equals(One) test
 1558//        if (a.BitLength == e + 1)
 1559//          break;
 1560//        BigInteger a1 = a.ShiftRight(e);
 1561////        if (a1.Equals(One))
 1562////          break;
 1563//
 1564//        int a1Lsw = a1.magnitude[a1.magnitude.Length - 1];
 1565//        if ((bLsw & 3) == 3 && (a1Lsw & 3) == 3)
 1566//          totalS = -totalS;
 1567//
 1568////        a = b.Mod(a1);
 1569//        a = b.Remainder(a1);
 1570//        b = a1;
 1571//      }
 1572//      return totalS;
 1573//    }
 1574
 1575        public long LongValue
 1576        {
 1577            get
 31578            {
 31579                if (sign == 0)
 01580                    return 0;
 1581
 31582                int n = magnitude.Length;
 1583
 31584                long v = magnitude[n - 1] & IMASK;
 31585                if (n > 1)
 31586                {
 31587                    v |= (magnitude[n - 2] & IMASK) << 32;
 31588                }
 1589
 31590                return sign < 0 ? -v : v;
 31591            }
 1592        }
 1593
 1594        public BigInteger Max(
 1595            BigInteger value)
 01596        {
 01597            return CompareTo(value) > 0 ? this : value;
 01598        }
 1599
 1600        public BigInteger Min(
 1601            BigInteger value)
 01602        {
 01603            return CompareTo(value) < 0 ? this : value;
 01604        }
 1605
 1606        public BigInteger Mod(
 1607            BigInteger m)
 91608        {
 91609            if (m.sign < 1)
 01610                throw new ArithmeticException("Modulus must be positive");
 1611
 91612            BigInteger biggie = Remainder(m);
 1613
 91614            return (biggie.sign >= 0 ? biggie : biggie.Add(m));
 91615        }
 1616
 1617        public BigInteger ModInverse(
 1618            BigInteger m)
 01619        {
 01620            if (m.sign < 1)
 01621                throw new ArithmeticException("Modulus must be positive");
 1622
 1623            // TODO Too slow at the moment
 1624//      // "Fast Key Exchange with Elliptic Curve Systems" R.Schoeppel
 1625//      if (m.TestBit(0))
 1626//      {
 1627//        //The Almost Inverse Algorithm
 1628//        int k = 0;
 1629//        BigInteger B = One, C = Zero, F = this, G = m, tmp;
 1630//
 1631//        for (;;)
 1632//        {
 1633//          // While F is even, do F=F/u, C=C*u, k=k+1.
 1634//          int zeroes = F.GetLowestSetBit();
 1635//          if (zeroes > 0)
 1636//          {
 1637//            F = F.ShiftRight(zeroes);
 1638//            C = C.ShiftLeft(zeroes);
 1639//            k += zeroes;
 1640//          }
 1641//
 1642//          // If F = 1, then return B,k.
 1643//          if (F.Equals(One))
 1644//          {
 1645//            BigInteger half = m.Add(One).ShiftRight(1);
 1646//            BigInteger halfK = half.ModPow(BigInteger.ValueOf(k), m);
 1647//            return B.Multiply(halfK).Mod(m);
 1648//          }
 1649//
 1650//          if (F.CompareTo(G) < 0)
 1651//          {
 1652//            tmp = G; G = F; F = tmp;
 1653//            tmp = B; B = C; C = tmp;
 1654//          }
 1655//
 1656//          F = F.Add(G);
 1657//          B = B.Add(C);
 1658//        }
 1659//      }
 1660
 01661            if (m.QuickPow2Check())
 01662            {
 01663                return ModInversePow2(m);
 1664            }
 1665
 01666            BigInteger d = this.Remainder(m);
 1667            BigInteger x;
 01668            BigInteger gcd = ExtEuclid(d, m, out x);
 1669
 01670            if (!gcd.Equals(One))
 01671                throw new ArithmeticException("Numbers not relatively prime.");
 1672
 01673            if (x.sign < 0)
 01674            {
 01675                x = x.Add(m);
 01676            }
 1677
 01678            return x;
 01679        }
 1680
 1681        private BigInteger ModInversePow2(BigInteger m)
 01682        {
 01683            Debug.Assert(m.SignValue > 0);
 01684            Debug.Assert(m.BitCount == 1);
 1685
 01686            if (!TestBit(0))
 01687            {
 01688                throw new ArithmeticException("Numbers not relatively prime.");
 1689            }
 1690
 01691            int pow = m.BitLength - 1;
 1692
 01693            long inv64 = ModInverse64(LongValue);
 01694            if (pow < 64)
 01695            {
 01696                inv64 &= ((1L << pow) - 1);
 01697            }
 1698
 01699            BigInteger x = BigInteger.ValueOf(inv64);
 1700
 01701            if (pow > 64)
 01702            {
 01703                BigInteger d = this.Remainder(m);
 01704                int bitsCorrect = 64;
 1705
 1706                do
 01707                {
 01708                    BigInteger t = x.Multiply(d).Remainder(m);
 01709                    x = x.Multiply(Two.Subtract(t)).Remainder(m);
 01710                    bitsCorrect <<= 1;
 01711                }
 01712                while (bitsCorrect < pow);
 01713            }
 1714
 01715            if (x.sign < 0)
 01716            {
 01717                x = x.Add(m);
 01718            }
 1719
 01720            return x;
 01721        }
 1722
 1723        private static int ModInverse32(int d)
 01724        {
 1725            // Newton's method with initial estimate "correct to 4 bits"
 01726            Debug.Assert((d & 1) != 0);
 01727            int x = d + (((d + 1) & 4) << 1);   // d.x == 1 mod 2**4
 01728            Debug.Assert(((d * x) & 15) == 1);
 01729            x *= 2 - d * x;                     // d.x == 1 mod 2**8
 01730            x *= 2 - d * x;                     // d.x == 1 mod 2**16
 01731            x *= 2 - d * x;                     // d.x == 1 mod 2**32
 01732            Debug.Assert(d * x == 1);
 01733            return x;
 01734        }
 1735
 1736        private static long ModInverse64(long d)
 01737        {
 1738            // Newton's method with initial estimate "correct to 4 bits"
 01739            Debug.Assert((d & 1L) != 0);
 01740            long x = d + (((d + 1L) & 4L) << 1);    // d.x == 1 mod 2**4
 01741            Debug.Assert(((d * x) & 15L) == 1L);
 01742            x *= 2 - d * x;                         // d.x == 1 mod 2**8
 01743            x *= 2 - d * x;                         // d.x == 1 mod 2**16
 01744            x *= 2 - d * x;                         // d.x == 1 mod 2**32
 01745            x *= 2 - d * x;                         // d.x == 1 mod 2**64
 01746            Debug.Assert(d * x == 1L);
 01747            return x;
 01748        }
 1749
 1750        /**
 1751         * Calculate the numbers u1, u2, and u3 such that:
 1752         *
 1753         * u1 * a + u2 * b = u3
 1754         *
 1755         * where u3 is the greatest common divider of a and b.
 1756         * a and b using the extended Euclid algorithm (refer p. 323
 1757         * of The Art of Computer Programming vol 2, 2nd ed).
 1758         * This also seems to have the side effect of calculating
 1759         * some form of multiplicative inverse.
 1760         *
 1761         * @param a    First number to calculate gcd for
 1762         * @param b    Second number to calculate gcd for
 1763         * @param u1Out      the return object for the u1 value
 1764         * @return     The greatest common divisor of a and b
 1765         */
 1766        private static BigInteger ExtEuclid(BigInteger a, BigInteger b, out BigInteger u1Out)
 01767        {
 01768            BigInteger u1 = One, v1 = Zero;
 01769            BigInteger u3 = a, v3 = b;
 1770
 01771            if (v3.sign > 0)
 01772            {
 1773                for (;;)
 01774                {
 01775                    BigInteger[] q = u3.DivideAndRemainder(v3);
 01776                    u3 = v3;
 01777                    v3 = q[1];
 1778
 01779                    BigInteger oldU1 = u1;
 01780                    u1 = v1;
 1781
 01782                    if (v3.sign <= 0)
 01783                        break;
 1784
 01785                    v1 = oldU1.Subtract(v1.Multiply(q[0]));
 01786                }
 01787            }
 1788
 01789            u1Out = u1;
 1790
 01791            return u3;
 01792        }
 1793
 1794        private static void ZeroOut(
 1795            int[] x)
 01796        {
 01797            Array.Clear(x, 0, x.Length);
 01798        }
 1799
 1800        public BigInteger ModPow(BigInteger e, BigInteger m)
 01801        {
 01802            if (m.sign < 1)
 01803                throw new ArithmeticException("Modulus must be positive");
 1804
 01805            if (m.Equals(One))
 01806                return Zero;
 1807
 01808            if (e.sign == 0)
 01809                return One;
 1810
 01811            if (sign == 0)
 01812                return Zero;
 1813
 01814            bool negExp = e.sign < 0;
 01815            if (negExp)
 01816                e = e.Negate();
 1817
 01818            BigInteger result = this.Mod(m);
 01819            if (!e.Equals(One))
 01820            {
 01821                if ((m.magnitude[m.magnitude.Length - 1] & 1) == 0)
 01822                {
 01823                    result = ModPowBarrett(result, e, m);
 01824                }
 1825                else
 01826                {
 01827                    result = ModPowMonty(result, e, m, true);
 01828                }
 01829            }
 1830
 01831            if (negExp)
 01832                result = result.ModInverse(m);
 1833
 01834            return result;
 01835        }
 1836
 1837        private static BigInteger ModPowBarrett(BigInteger b, BigInteger e, BigInteger m)
 01838        {
 01839            int k = m.magnitude.Length;
 01840            BigInteger mr = One.ShiftLeft((k + 1) << 5);
 01841            BigInteger yu = One.ShiftLeft(k << 6).Divide(m);
 1842
 1843            // Sliding window from MSW to LSW
 01844            int extraBits = 0, expLength = e.BitLength;
 01845            while (expLength > ExpWindowThresholds[extraBits])
 01846            {
 01847                ++extraBits;
 01848            }
 1849
 01850            int numPowers = 1 << extraBits;
 01851            BigInteger[] oddPowers = new BigInteger[numPowers];
 01852            oddPowers[0] = b;
 1853
 01854            BigInteger b2 = ReduceBarrett(b.Square(), m, mr, yu);
 1855
 01856            for (int i = 1; i < numPowers; ++i)
 01857            {
 01858                oddPowers[i] = ReduceBarrett(oddPowers[i - 1].Multiply(b2), m, mr, yu);
 01859            }
 1860
 01861            int[] windowList = GetWindowList(e.magnitude, extraBits);
 01862            Debug.Assert(windowList.Length > 0);
 1863
 01864            int window = windowList[0];
 01865            int mult = window & 0xFF, lastZeroes = window >> 8;
 1866
 1867            BigInteger y;
 01868            if (mult == 1)
 01869            {
 01870                y = b2;
 01871                --lastZeroes;
 01872            }
 1873            else
 01874            {
 01875                y = oddPowers[mult >> 1];
 01876            }
 1877
 01878            int windowPos = 1;
 01879            while ((window = windowList[windowPos++]) != -1)
 01880            {
 01881                mult = window & 0xFF;
 1882
 01883                int bits = lastZeroes + BitLengthTable[mult];
 01884                for (int j = 0; j < bits; ++j)
 01885                {
 01886                    y = ReduceBarrett(y.Square(), m, mr, yu);
 01887                }
 1888
 01889                y = ReduceBarrett(y.Multiply(oddPowers[mult >> 1]), m, mr, yu);
 1890
 01891                lastZeroes = window >> 8;
 01892            }
 1893
 01894            for (int i = 0; i < lastZeroes; ++i)
 01895            {
 01896                y = ReduceBarrett(y.Square(), m, mr, yu);
 01897            }
 1898
 01899            return y;
 01900        }
 1901
 1902        private static BigInteger ReduceBarrett(BigInteger x, BigInteger m, BigInteger mr, BigInteger yu)
 01903        {
 01904            int xLen = x.BitLength, mLen = m.BitLength;
 01905            if (xLen < mLen)
 01906                return x;
 1907
 01908            if (xLen - mLen > 1)
 01909            {
 01910                int k = m.magnitude.Length;
 1911
 01912                BigInteger q1 = x.DivideWords(k - 1);
 01913                BigInteger q2 = q1.Multiply(yu); // TODO Only need partial multiplication here
 01914                BigInteger q3 = q2.DivideWords(k + 1);
 1915
 01916                BigInteger r1 = x.RemainderWords(k + 1);
 01917                BigInteger r2 = q3.Multiply(m); // TODO Only need partial multiplication here
 01918                BigInteger r3 = r2.RemainderWords(k + 1);
 1919
 01920                x = r1.Subtract(r3);
 01921                if (x.sign < 0)
 01922                {
 01923                    x = x.Add(mr);
 01924                }
 01925            }
 1926
 01927            while (x.CompareTo(m) >= 0)
 01928            {
 01929                x = x.Subtract(m);
 01930            }
 1931
 01932            return x;
 01933        }
 1934
 1935        private static BigInteger ModPowMonty(BigInteger b, BigInteger e, BigInteger m, bool convert)
 01936        {
 01937            int n = m.magnitude.Length;
 01938            int powR = 32 * n;
 01939            bool smallMontyModulus = m.BitLength + 2 <= powR;
 01940            uint mDash = (uint)m.GetMQuote();
 1941
 1942            // tmp = this * R mod m
 01943            if (convert)
 01944            {
 01945                b = b.ShiftLeft(powR).Remainder(m);
 01946            }
 1947
 01948            int[] yAccum = new int[n + 1];
 1949
 01950            int[] zVal = b.magnitude;
 01951            Debug.Assert(zVal.Length <= n);
 01952            if (zVal.Length < n)
 01953            {
 01954                int[] tmp = new int[n];
 01955                zVal.CopyTo(tmp, n - zVal.Length);
 01956                zVal = tmp;
 01957            }
 1958
 1959            // Sliding window from MSW to LSW
 1960
 01961            int extraBits = 0;
 1962
 1963            // Filter the common case of small RSA exponents with few bits set
 01964            if (e.magnitude.Length > 1 || e.BitCount > 2)
 01965            {
 01966                int expLength = e.BitLength;
 01967                while (expLength > ExpWindowThresholds[extraBits])
 01968                {
 01969                    ++extraBits;
 01970                }
 01971            }
 1972
 01973            int numPowers = 1 << extraBits;
 01974            int[][] oddPowers = new int[numPowers][];
 01975            oddPowers[0] = zVal;
 1976
 01977            int[] zSquared = Arrays.Clone(zVal);
 01978            SquareMonty(yAccum, zSquared, m.magnitude, mDash, smallMontyModulus);
 1979
 01980            for (int i = 1; i < numPowers; ++i)
 01981            {
 01982                oddPowers[i] = Arrays.Clone(oddPowers[i - 1]);
 01983                MultiplyMonty(yAccum, oddPowers[i], zSquared, m.magnitude, mDash, smallMontyModulus);
 01984            }
 1985
 01986            int[] windowList = GetWindowList(e.magnitude, extraBits);
 01987            Debug.Assert(windowList.Length > 1);
 1988
 01989            int window = windowList[0];
 01990            int mult = window & 0xFF, lastZeroes = window >> 8;
 1991
 1992            int[] yVal;
 01993            if (mult == 1)
 01994            {
 01995                yVal = zSquared;
 01996                --lastZeroes;
 01997            }
 1998            else
 01999            {
 02000                yVal = Arrays.Clone(oddPowers[mult >> 1]);
 02001            }
 2002
 02003            int windowPos = 1;
 02004            while ((window = windowList[windowPos++]) != -1)
 02005            {
 02006                mult = window & 0xFF;
 2007
 02008                int bits = lastZeroes + BitLengthTable[mult];
 02009                for (int j = 0; j < bits; ++j)
 02010                {
 02011                    SquareMonty(yAccum, yVal, m.magnitude, mDash, smallMontyModulus);
 02012                }
 2013
 02014                MultiplyMonty(yAccum, yVal, oddPowers[mult >> 1], m.magnitude, mDash, smallMontyModulus);
 2015
 02016                lastZeroes = window >> 8;
 02017            }
 2018
 02019            for (int i = 0; i < lastZeroes; ++i)
 02020            {
 02021                SquareMonty(yAccum, yVal, m.magnitude, mDash, smallMontyModulus);
 02022            }
 2023
 02024            if (convert)
 02025            {
 2026                // Return y * R^(-1) mod m
 02027                MontgomeryReduce(yVal, m.magnitude, mDash);
 02028            }
 02029            else if (smallMontyModulus && CompareTo(0, yVal, 0, m.magnitude) >= 0)
 02030            {
 02031                Subtract(0, yVal, 0, m.magnitude);
 02032            }
 2033
 02034            return new BigInteger(1, yVal, true);
 02035        }
 2036
 2037        private static int[] GetWindowList(int[] mag, int extraBits)
 02038        {
 02039            int v = mag[0];
 02040            Debug.Assert(v != 0);
 2041
 02042            int leadingBits = BitLen(v);
 2043
 02044            int resultSize = (((mag.Length - 1) << 5) + leadingBits) / (1 + extraBits) + 2;
 02045            int[] result = new int[resultSize];
 02046            int resultPos = 0;
 2047
 02048            int bitPos = 33 - leadingBits;
 02049            v <<= bitPos;
 2050
 02051            int mult = 1, multLimit = 1 << extraBits;
 02052            int zeroes = 0;
 2053
 02054            int i = 0;
 2055            for (; ; )
 02056            {
 02057                for (; bitPos < 32; ++bitPos)
 02058                {
 02059                    if (mult < multLimit)
 02060                    {
 02061                        mult = (mult << 1) | (int)((uint)v >> 31);
 02062                    }
 02063                    else if (v < 0)
 02064                    {
 02065                        result[resultPos++] = CreateWindowEntry(mult, zeroes);
 02066                        mult = 1;
 02067                        zeroes = 0;
 02068                    }
 2069                    else
 02070                    {
 02071                        ++zeroes;
 02072                    }
 2073
 02074                    v <<= 1;
 02075                }
 2076
 02077                if (++i == mag.Length)
 02078                {
 02079                    result[resultPos++] = CreateWindowEntry(mult, zeroes);
 02080                    break;
 2081                }
 2082
 02083                v = mag[i];
 02084                bitPos = 0;
 02085            }
 2086
 02087            result[resultPos] = -1;
 02088            return result;
 02089        }
 2090
 2091        private static int CreateWindowEntry(int mult, int zeroes)
 02092        {
 02093            while ((mult & 1) == 0)
 02094            {
 02095                mult >>= 1;
 02096                ++zeroes;
 02097            }
 2098
 02099            return mult | (zeroes << 8);
 02100        }
 2101
 2102        /**
 2103         * return w with w = x * x - w is assumed to have enough space.
 2104         */
 2105        private static int[] Square(
 2106            int[]  w,
 2107            int[]  x)
 223762108        {
 2109            // Note: this method allows w to be only (2 * x.Length - 1) words if result will fit
 2110//      if (w.Length != 2 * x.Length)
 2111//        throw new ArgumentException("no I don't think so...");
 2112
 2113            ulong c;
 2114
 223762115            int wBase = w.Length - 1;
 2116
 5942502117            for (int i = x.Length - 1; i > 0; --i)
 2747492118            {
 2747492119                ulong v = (uint)x[i];
 2120
 2747492121                c = v * v + (uint)w[wBase];
 2747492122                w[wBase] = (int)c;
 2747492123                c >>= 32;
 2124
 44892142125                for (int j = i - 1; j >= 0; --j)
 19698582126                {
 19698582127                    ulong prod = v * (uint)x[j];
 2128
 19698582129                    c += ((uint)w[--wBase] & UIMASK) + ((uint)prod << 1);
 19698582130                    w[wBase] = (int)c;
 19698582131                    c = (c >> 32) + (prod >> 31);
 19698582132                }
 2133
 2747492134                c += (uint)w[--wBase];
 2747492135                w[wBase] = (int)c;
 2136
 2747492137                if (--wBase >= 0)
 2649362138                {
 2649362139                    w[wBase] = (int)(c >> 32);
 2649362140                }
 2141                else
 98132142                {
 98132143                    Debug.Assert((c >> 32) == 0);
 98132144                }
 2145
 2747492146                wBase += i;
 2747492147            }
 2148
 223762149            c = (uint)x[0];
 2150
 223762151            c = c * c + (uint)w[wBase];
 223762152            w[wBase] = (int)c;
 2153
 223762154            if (--wBase >= 0)
 125602155            {
 125602156                w[wBase] += (int)(c >> 32);
 125602157            }
 2158            else
 98162159            {
 98162160                Debug.Assert((c >> 32) == 0);
 98162161            }
 2162
 223762163            return w;
 223762164        }
 2165
 2166        /**
 2167         * return x with x = y * z - x is assumed to have enough space.
 2168         */
 2169        private static int[] Multiply(int[]  x, int[] y, int[] z)
 1041712170        {
 1041712171            int i = z.Length;
 2172
 1041712173            if (i < 1)
 02174                return x;
 2175
 1041712176            int xBase = x.Length - y.Length;
 2177
 2178            do
 9132382179            {
 9132382180                long a = z[--i] & IMASK;
 9132382181                long val = 0;
 2182
 9132382183                if (a != 0)
 8340302184                {
 213668502185                    for (int j = y.Length - 1; j >= 0; j--)
 98493952186                    {
 98493952187                        val += a * (y[j] & IMASK) + (x[xBase + j] & IMASK);
 2188
 98493952189                        x[xBase + j] = (int)val;
 2190
 98493952191                        val = (long)((ulong)val >> 32);
 98493952192                    }
 8340302193                }
 2194
 9132382195                --xBase;
 2196
 9132382197                if (xBase >= 0)
 9132382198                {
 9132382199                    x[xBase] = (int)val;
 9132382200                }
 2201                else
 02202                {
 02203                    Debug.Assert(val == 0);
 02204                }
 9132382205            }
 9132382206            while (i > 0);
 2207
 1041712208            return x;
 1041712209        }
 2210
 2211        /**
 2212         * Calculate mQuote = -m^(-1) mod b with b = 2^32 (32 = word size)
 2213         */
 2214        private int GetMQuote()
 02215        {
 02216            if (mQuote != 0)
 02217            {
 02218                return mQuote; // already calculated
 2219            }
 2220
 02221            Debug.Assert(this.sign > 0);
 2222
 02223            int d = -magnitude[magnitude.Length - 1];
 2224
 02225            Debug.Assert((d & 1) != 0);
 2226
 02227            return mQuote = ModInverse32(d);
 02228        }
 2229
 2230        private static void MontgomeryReduce(int[] x, int[] m, uint mDash) // mDash = -m^(-1) mod b
 02231        {
 2232            // NOTE: Not a general purpose reduction (which would allow x up to twice the bitlength of m)
 02233            Debug.Assert(x.Length == m.Length);
 2234
 02235            int n = m.Length;
 2236
 02237            for (int i = n - 1; i >= 0; --i)
 02238            {
 02239                uint x0 = (uint)x[n - 1];
 02240                ulong t = x0 * mDash;
 2241
 02242                ulong carry = t * (uint)m[n - 1] + x0;
 02243                Debug.Assert((uint)carry == 0);
 02244                carry >>= 32;
 2245
 02246                for (int j = n - 2; j >= 0; --j)
 02247                {
 02248                    carry += t * (uint)m[j] + (uint)x[j];
 02249                    x[j + 1] = (int)carry;
 02250                    carry >>= 32;
 02251                }
 2252
 02253                x[0] = (int)carry;
 02254                Debug.Assert(carry >> 32 == 0);
 02255            }
 2256
 02257            if (CompareTo(0, x, 0, m) >= 0)
 02258            {
 02259                Subtract(0, x, 0, m);
 02260            }
 02261        }
 2262
 2263        /**
 2264         * Montgomery multiplication: a = x * y * R^(-1) mod m
 2265         * <br/>
 2266         * Based algorithm 14.36 of Handbook of Applied Cryptography.
 2267         * <br/>
 2268         * <li> m, x, y should have length n </li>
 2269         * <li> a should have length (n + 1) </li>
 2270         * <li> b = 2^32, R = b^n </li>
 2271         * <br/>
 2272         * The result is put in x
 2273         * <br/>
 2274         * NOTE: the indices of x, y, m, a different in HAC and in Java
 2275         */
 2276        private static void MultiplyMonty(int[]  a, int[] x, int[] y, int[] m, uint mDash, bool smallMontyModulus)
 2277            // mDash = -m^(-1) mod b
 02278        {
 02279            int n = m.Length;
 2280
 02281            if (n == 1)
 02282            {
 02283                x[0] = (int)MultiplyMontyNIsOne((uint)x[0], (uint)y[0], (uint)m[0], mDash);
 02284                return;
 2285            }
 2286
 02287            uint y0 = (uint)y[n - 1];
 2288            int aMax;
 2289
 02290            {
 02291                ulong xi = (uint)x[n - 1];
 2292
 02293                ulong carry = xi * y0;
 02294                ulong t = (uint)carry * mDash;
 2295
 02296                ulong prod2 = t * (uint)m[n - 1];
 02297                carry += (uint)prod2;
 02298                Debug.Assert((uint)carry == 0);
 02299                carry = (carry >> 32) + (prod2 >> 32);
 2300
 02301                for (int j = n - 2; j >= 0; --j)
 02302                {
 02303                    ulong prod1 = xi * (uint)y[j];
 02304                    prod2 = t * (uint)m[j];
 2305
 02306                    carry += (prod1 & UIMASK) + (uint)prod2;
 02307                    a[j + 2] = (int)carry;
 02308                    carry = (carry >> 32) + (prod1 >> 32) + (prod2 >> 32);
 02309                }
 2310
 02311                a[1] = (int)carry;
 02312                aMax = (int)(carry >> 32);
 02313            }
 2314
 02315            for (int i = n - 2; i >= 0; --i)
 02316            {
 02317                uint a0 = (uint)a[n];
 02318                ulong xi = (uint)x[i];
 2319
 02320                ulong prod1 = xi * y0;
 02321                ulong carry = (prod1 & UIMASK) + a0;
 02322                ulong t = (uint)carry * mDash;
 2323
 02324                ulong prod2 = t * (uint)m[n - 1];
 02325                carry += (uint)prod2;
 02326                Debug.Assert((uint)carry == 0);
 02327                carry = (carry >> 32) + (prod1 >> 32) + (prod2 >> 32);
 2328
 02329                for (int j = n - 2; j >= 0; --j)
 02330                {
 02331                    prod1 = xi * (uint)y[j];
 02332                    prod2 = t * (uint)m[j];
 2333
 02334                    carry += (prod1 & UIMASK) + (uint)prod2 + (uint)a[j + 1];
 02335                    a[j + 2] = (int)carry;
 02336                    carry = (carry >> 32) + (prod1 >> 32) + (prod2 >> 32);
 02337                }
 2338
 02339                carry += (uint)aMax;
 02340                a[1] = (int)carry;
 02341                aMax = (int)(carry >> 32);
 02342            }
 2343
 02344            a[0] = aMax;
 2345
 02346            if (!smallMontyModulus && CompareTo(0, a, 0, m) >= 0)
 02347            {
 02348                Subtract(0, a, 0, m);
 02349            }
 2350
 02351            Array.Copy(a, 1, x, 0, n);
 02352        }
 2353
 2354        private static void SquareMonty(int[] a, int[] x, int[] m, uint mDash, bool smallMontyModulus)
 2355            // mDash = -m^(-1) mod b
 02356        {
 02357            int n = m.Length;
 2358
 02359            if (n == 1)
 02360            {
 02361                uint xVal = (uint)x[0];
 02362                x[0] = (int)MultiplyMontyNIsOne(xVal, xVal, (uint)m[0], mDash);
 02363                return;
 2364            }
 2365
 02366            ulong x0 = (uint)x[n - 1];
 2367            int aMax;
 2368
 02369            {
 02370                ulong carry = x0 * x0;
 02371                ulong t = (uint)carry * mDash;
 2372
 02373                ulong prod2 = t * (uint)m[n - 1];
 02374                carry += (uint)prod2;
 02375                Debug.Assert((uint)carry == 0);
 02376                carry = (carry >> 32) + (prod2 >> 32);
 2377
 02378                for (int j = n - 2; j >= 0; --j)
 02379                {
 02380                    ulong prod1 = x0 * (uint)x[j];
 02381                    prod2 = t * (uint)m[j];
 2382
 02383                    carry += (prod2 & UIMASK) + ((uint)prod1 << 1);
 02384                    a[j + 2] = (int)carry;
 02385                    carry = (carry >> 32) + (prod1 >> 31) + (prod2 >> 32);
 02386                }
 2387
 02388                a[1] = (int)carry;
 02389                aMax = (int)(carry >> 32);
 02390            }
 2391
 02392            for (int i = n - 2; i >= 0; --i)
 02393            {
 02394                uint a0 = (uint)a[n];
 02395                ulong t = a0 * mDash;
 2396
 02397                ulong carry = t * (uint)m[n - 1] + a0;
 02398                Debug.Assert((uint)carry == 0);
 02399                carry >>= 32;
 2400
 02401                for (int j = n - 2; j > i; --j)
 02402                {
 02403                    carry += t * (uint)m[j] + (uint)a[j + 1];
 02404                    a[j + 2] = (int)carry;
 02405                    carry >>= 32;
 02406                }
 2407
 02408                ulong xi = (uint)x[i];
 2409
 02410                {
 02411                    ulong prod1 = xi * xi;
 02412                    ulong prod2 = t * (uint)m[i];
 2413
 02414                    carry += (prod1 & UIMASK) + (uint)prod2 + (uint)a[i + 1];
 02415                    a[i + 2] = (int)carry;
 02416                    carry = (carry >> 32) + (prod1 >> 32) + (prod2 >> 32);
 02417                }
 2418
 02419                for (int j = i - 1; j >= 0; --j)
 02420                {
 02421                    ulong prod1 = xi * (uint)x[j];
 02422                    ulong prod2 = t * (uint)m[j];
 2423
 02424                    carry += (prod2 & UIMASK) + ((uint)prod1 << 1) + (uint)a[j + 1];
 02425                    a[j + 2] = (int)carry;
 02426                    carry = (carry >> 32) + (prod1 >> 31) + (prod2 >> 32);
 02427                }
 2428
 02429                carry += (uint)aMax;
 02430                a[1] = (int)carry;
 02431                aMax = (int)(carry >> 32);
 02432            }
 2433
 02434            a[0] = aMax;
 2435
 02436            if (!smallMontyModulus && CompareTo(0, a, 0, m) >= 0)
 02437            {
 02438                Subtract(0, a, 0, m);
 02439            }
 2440
 02441            Array.Copy(a, 1, x, 0, n);
 02442        }
 2443
 2444        private static uint MultiplyMontyNIsOne(uint x, uint y, uint m, uint mDash)
 02445        {
 02446            ulong carry = (ulong)x * y;
 02447            uint t = (uint)carry * mDash;
 02448            ulong um = m;
 02449            ulong prod2 = um * t;
 02450            carry += (uint)prod2;
 02451            Debug.Assert((uint)carry == 0);
 02452            carry = (carry >> 32) + (prod2 >> 32);
 02453            if (carry > um)
 02454            {
 02455                carry -= um;
 02456            }
 02457            Debug.Assert(carry < um);
 02458            return (uint)carry;
 02459        }
 2460
 2461        public BigInteger Multiply(
 2462            BigInteger val)
 1267012463        {
 1267012464            if (val == this)
 223762465                return Square();
 2466
 1043252467            if ((sign & val.sign) == 0)
 1262468                return Zero;
 2469
 1041992470            if (val.QuickPow2Check()) // val is power of two
 02471            {
 02472                BigInteger result = this.ShiftLeft(val.Abs().BitLength - 1);
 02473                return val.sign > 0 ? result : result.Negate();
 2474            }
 2475
 1041992476            if (this.QuickPow2Check()) // this is power of two
 282477            {
 282478                BigInteger result = val.ShiftLeft(this.Abs().BitLength - 1);
 282479                return this.sign > 0 ? result : result.Negate();
 2480            }
 2481
 1041712482            int resLength = magnitude.Length + val.magnitude.Length;
 1041712483            int[] res = new int[resLength];
 2484
 1041712485            Multiply(res, this.magnitude, val.magnitude);
 2486
 1041712487            int resSign = sign ^ val.sign ^ 1;
 1041712488            return new BigInteger(resSign, res, true);
 1267012489        }
 2490
 2491        public BigInteger Square()
 223762492        {
 223762493            if (sign == 0)
 02494                return Zero;
 223762495            if (this.QuickPow2Check())
 02496                return ShiftLeft(Abs().BitLength - 1);
 223762497            int resLength = magnitude.Length << 1;
 223762498            if ((uint)magnitude[0] >> 16 == 0)
 98162499                --resLength;
 223762500            int[] res = new int[resLength];
 223762501            Square(res, magnitude);
 223762502            return new BigInteger(1, res, false);
 223762503        }
 2504
 2505        public BigInteger Negate()
 245652506        {
 245652507            if (sign == 0)
 02508                return this;
 2509
 245652510            return new BigInteger(-sign, magnitude, false);
 245652511        }
 2512
 2513        public BigInteger NextProbablePrime()
 02514        {
 02515            if (sign < 0)
 02516                throw new ArithmeticException("Cannot be called on value < 0");
 2517
 02518            if (CompareTo(Two) < 0)
 02519                return Two;
 2520
 02521            BigInteger n = Inc().SetBit(0);
 2522
 02523            while (!n.CheckProbablePrime(100, RandomSource, false))
 02524            {
 02525                n = n.Add(Two);
 02526            }
 2527
 02528            return n;
 02529        }
 2530
 2531        public BigInteger Not()
 02532        {
 02533            return Inc().Negate();
 02534        }
 2535
 2536        public BigInteger Pow(int exp)
 42537        {
 42538            if (exp <= 0)
 02539            {
 02540                if (exp < 0)
 02541                    throw new ArithmeticException("Negative exponent");
 2542
 02543                return One;
 2544            }
 2545
 42546            if (sign == 0)
 02547            {
 02548                return this;
 2549            }
 2550
 42551            if (QuickPow2Check())
 32552            {
 32553                long powOf2 = (long)exp * (BitLength - 1);
 32554                if (powOf2 > Int32.MaxValue)
 02555                {
 02556                    throw new ArithmeticException("Result too large");
 2557                }
 32558                return One.ShiftLeft((int)powOf2);
 2559            }
 2560
 12561            BigInteger y = One;
 12562            BigInteger z = this;
 2563
 2564            for (;;)
 52565            {
 52566                if ((exp & 0x1) == 1)
 32567                {
 32568                    y = y.Multiply(z);
 32569                }
 52570                exp >>= 1;
 62571                if (exp == 0) break;
 42572                z = z.Multiply(z);
 42573            }
 2574
 12575            return y;
 42576        }
 2577
 2578        public static BigInteger ProbablePrime(
 2579            int bitLength,
 2580            Random random)
 02581        {
 02582            return new BigInteger(bitLength, 100, random);
 02583        }
 2584
 2585        private int Remainder(
 2586            int m)
 02587        {
 02588            Debug.Assert(m > 0);
 2589
 02590            long acc = 0;
 02591            for (int pos = 0; pos < magnitude.Length; ++pos)
 02592            {
 02593                long posVal = (uint) magnitude[pos];
 02594                acc = (acc << 32 | posVal) % m;
 02595            }
 2596
 02597            return (int) acc;
 02598        }
 2599
 2600        /**
 2601         * return x = x % y - done in place (y value preserved)
 2602         */
 2603        private static int[] Remainder(
 2604            int[] x,
 2605            int[] y)
 02606        {
 02607            int xStart = 0;
 02608            while (xStart < x.Length && x[xStart] == 0)
 02609            {
 02610                ++xStart;
 02611            }
 2612
 02613            int yStart = 0;
 02614            while (yStart < y.Length && y[yStart] == 0)
 02615            {
 02616                ++yStart;
 02617            }
 2618
 02619            Debug.Assert(yStart < y.Length);
 2620
 02621            int xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
 2622
 02623            if (xyCmp > 0)
 02624            {
 02625                int yBitLength = CalcBitLength(1, yStart, y);
 02626                int xBitLength = CalcBitLength(1, xStart, x);
 02627                int shift = xBitLength - yBitLength;
 2628
 2629                int[] c;
 02630                int cStart = 0;
 02631                int cBitLength = yBitLength;
 02632                if (shift > 0)
 02633                {
 02634                    c = ShiftLeft(y, shift);
 02635                    cBitLength += shift;
 02636                    Debug.Assert(c[0] != 0);
 02637                }
 2638                else
 02639                {
 02640                    int len = y.Length - yStart;
 02641                    c = new int[len];
 02642                    Array.Copy(y, yStart, c, 0, len);
 02643                }
 2644
 2645                for (;;)
 02646                {
 02647                    if (cBitLength < xBitLength
 02648                        || CompareNoLeadingZeroes(xStart, x, cStart, c) >= 0)
 02649                    {
 02650                        Subtract(xStart, x, cStart, c);
 2651
 02652                        while (x[xStart] == 0)
 02653                        {
 02654                            if (++xStart == x.Length)
 02655                                return x;
 02656                        }
 2657
 2658                        //xBitLength = CalcBitLength(xStart, x);
 02659                        xBitLength = 32 * (x.Length - xStart - 1) + BitLen(x[xStart]);
 2660
 02661                        if (xBitLength <= yBitLength)
 02662                        {
 02663                            if (xBitLength < yBitLength)
 02664                                return x;
 2665
 02666                            xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
 2667
 02668                            if (xyCmp <= 0)
 02669                                break;
 02670                        }
 02671                    }
 2672
 02673                    shift = cBitLength - xBitLength;
 2674
 2675                    // NB: The case where c[cStart] is 1-bit is harmless
 02676                    if (shift == 1)
 02677                    {
 02678                        uint firstC = (uint) c[cStart] >> 1;
 02679                        uint firstX = (uint) x[xStart];
 02680                        if (firstC > firstX)
 02681                            ++shift;
 02682                    }
 2683
 02684                    if (shift < 2)
 02685                    {
 02686                        ShiftRightOneInPlace(cStart, c);
 02687                        --cBitLength;
 02688                    }
 2689                    else
 02690                    {
 02691                        ShiftRightInPlace(cStart, c, shift);
 02692                        cBitLength -= shift;
 02693                    }
 2694
 2695                    //cStart = c.Length - ((cBitLength + 31) / 32);
 02696                    while (c[cStart] == 0)
 02697                    {
 02698                        ++cStart;
 02699                    }
 02700                }
 02701            }
 2702
 02703            if (xyCmp == 0)
 02704            {
 02705                Array.Clear(x, xStart, x.Length - xStart);
 02706            }
 2707
 02708            return x;
 02709        }
 2710
 2711        public BigInteger Remainder(
 2712            BigInteger n)
 915392713        {
 915392714            if (n.sign == 0)
 02715                throw new ArithmeticException("Division by zero error");
 2716
 915392717            if (this.sign == 0)
 1262718                return Zero;
 2719
 2720            // For small values, use fast remainder method
 914132721            if (n.magnitude.Length == 1)
 02722            {
 02723                int val = n.magnitude[0];
 2724
 02725                if (val > 0)
 02726                {
 02727                    if (val == 1)
 02728                        return Zero;
 2729
 2730                    // TODO Make this func work on uint, and handle val == 1?
 02731                    int rem = Remainder(val);
 2732
 02733                    return rem == 0
 02734                        ?  Zero
 02735                        :  new BigInteger(sign, new int[]{ rem }, false);
 2736                }
 02737            }
 2738
 914132739            if (CompareNoLeadingZeroes(0, magnitude, 0, n.magnitude) < 0)
 5772740                return this;
 2741
 2742            int[] result;
 908362743            if (n.QuickPow2Check())  // n is power of two
 908362744            {
 2745                // TODO Move before small values branch above?
 908362746                result = LastNBits(n.Abs().BitLength - 1);
 908362747            }
 2748            else
 02749            {
 02750                result = (int[]) this.magnitude.Clone();
 02751                result = Remainder(result, n.magnitude);
 02752            }
 2753
 908362754            return new BigInteger(sign, result, true);
 915392755        }
 2756
 2757        private int[] LastNBits(
 2758            int n)
 908362759        {
 908362760            if (n < 1)
 02761                return ZeroMagnitude;
 2762
 908362763            int numWords = (n + BitsPerInt - 1) / BitsPerInt;
 908362764            numWords = System.Math.Min(numWords, this.magnitude.Length);
 908362765            int[] result = new int[numWords];
 2766
 908362767            Array.Copy(this.magnitude, this.magnitude.Length - numWords, result, 0, numWords);
 2768
 908362769            int excessBits = (numWords << 5) - n;
 908362770            if (excessBits > 0)
 256052771            {
 256052772                result[0] &= (int)(UInt32.MaxValue >> excessBits);
 256052773            }
 2774
 908362775            return result;
 908362776        }
 2777
 2778        private BigInteger DivideWords(int w)
 02779        {
 02780            Debug.Assert(w >= 0);
 02781            int n = magnitude.Length;
 02782            if (w >= n)
 02783                return Zero;
 02784            int[] mag = new int[n - w];
 02785            Array.Copy(magnitude, 0, mag, 0, n - w);
 02786            return new BigInteger(sign, mag, false);
 02787        }
 2788
 2789        private BigInteger RemainderWords(int w)
 02790        {
 02791            Debug.Assert(w >= 0);
 02792            int n = magnitude.Length;
 02793            if (w >= n)
 02794                return this;
 02795            int[] mag = new int[w];
 02796            Array.Copy(magnitude, n - w, mag, 0, w);
 02797            return new BigInteger(sign, mag, false);
 02798        }
 2799
 2800        /**
 2801         * do a left shift - this returns a new array.
 2802         */
 2803        private static int[] ShiftLeft(
 2804            int[]  mag,
 2805            int    n)
 593752806        {
 593752807            int nInts = (int)((uint)n >> 5);
 593752808            int nBits = n & 0x1f;
 593752809            int magLen = mag.Length;
 2810            int[] newMag;
 2811
 593752812            if (nBits == 0)
 333732813            {
 333732814                newMag = new int[magLen + nInts];
 333732815                mag.CopyTo(newMag, 0);
 333732816            }
 2817            else
 260022818            {
 260022819                int i = 0;
 260022820                int nBits2 = 32 - nBits;
 260022821                int highBits = (int)((uint)mag[0] >> nBits2);
 2822
 260022823                if (highBits != 0)
 22824                {
 22825                    newMag = new int[magLen + nInts + 1];
 22826                    newMag[i++] = highBits;
 22827                }
 2828                else
 260002829                {
 260002830                    newMag = new int[magLen + nInts];
 260002831                }
 2832
 260022833                int m = mag[0];
 522222834                for (int j = 0; j < magLen - 1; j++)
 1092835                {
 1092836                    int next = mag[j + 1];
 2837
 1092838                    newMag[i++] = (m << nBits) | (int)((uint)next >> nBits2);
 1092839                    m = next;
 1092840                }
 2841
 260022842                newMag[i] = mag[magLen - 1] << nBits;
 260022843            }
 2844
 593752845            return newMag;
 593752846        }
 2847
 2848        private static int ShiftLeftOneInPlace(int[] x, int carry)
 02849        {
 02850            Debug.Assert(carry == 0 || carry == 1);
 02851            int pos = x.Length;
 02852            while (--pos >= 0)
 02853            {
 02854                uint val = (uint)x[pos];
 02855                x[pos] = (int)(val << 1) | carry;
 02856                carry = (int)(val >> 31);
 02857            }
 02858            return carry;
 02859        }
 2860
 2861        public BigInteger ShiftLeft(
 2862            int n)
 594022863        {
 594022864            if (sign == 0 || magnitude.Length == 0)
 02865                return Zero;
 2866
 594022867            if (n == 0)
 282868                return this;
 2869
 593742870            if (n < 0)
 02871                return ShiftRight(-n);
 2872
 593742873            BigInteger result = new BigInteger(sign, ShiftLeft(magnitude, n), true);
 2874
 593742875            if (this.nBits != -1)
 593652876            {
 593652877                result.nBits = sign > 0
 593652878                    ?  this.nBits
 593652879                    :  this.nBits + n;
 593652880            }
 2881
 593742882            if (this.nBitLength != -1)
 593632883            {
 593632884                result.nBitLength = this.nBitLength + n;
 593632885            }
 2886
 593742887            return result;
 594022888        }
 2889
 2890        /**
 2891         * do a right shift - this does it in place.
 2892         */
 2893        private static void ShiftRightInPlace(
 2894            int    start,
 2895            int[]  mag,
 2896            int    n)
 42897        {
 42898            int nInts = (int)((uint)n >> 5) + start;
 42899            int nBits = n & 0x1f;
 42900            int magEnd = mag.Length - 1;
 2901
 42902            if (nInts != start)
 42903            {
 42904                int delta = (nInts - start);
 2905
 762906                for (int i = magEnd; i >= nInts; i--)
 342907                {
 342908                    mag[i] = mag[i - delta];
 342909                }
 162910                for (int i = nInts - 1; i >= start; i--)
 42911                {
 42912                    mag[i] = 0;
 42913                }
 42914            }
 2915
 42916            if (nBits != 0)
 22917            {
 22918                int nBits2 = 32 - nBits;
 22919                int m = mag[magEnd];
 2920
 222921                for (int i = magEnd; i > nInts; --i)
 92922                {
 92923                    int next = mag[i - 1];
 2924
 92925                    mag[i] = (int)((uint)m >> nBits) | (next << nBits2);
 92926                    m = next;
 92927                }
 2928
 22929                mag[nInts] = (int)((uint)mag[nInts] >> nBits);
 22930            }
 42931        }
 2932
 2933        /**
 2934         * do a right shift by one - this does it in place.
 2935         */
 2936        private static void ShiftRightOneInPlace(
 2937            int    start,
 2938            int[]  mag)
 3262939        {
 3262940            int i = mag.Length;
 3262941            int m = mag[i - 1];
 2942
 29312943            while (--i > start)
 26052944            {
 26052945                int next = mag[i - 1];
 26052946                mag[i] = ((int)((uint)m >> 1)) | (next << 31);
 26052947                m = next;
 26052948            }
 2949
 3262950            mag[start] = (int)((uint)mag[start] >> 1);
 3262951        }
 2952
 2953        public BigInteger ShiftRight(
 2954            int n)
 929792955        {
 929792956            if (n == 0)
 32957                return this;
 2958
 929762959            if (n < 0)
 02960                return ShiftLeft(-n);
 2961
 929762962            if (n >= BitLength)
 2032963                return (this.sign < 0 ? One.Negate() : Zero);
 2964
 2965//      int[] res = (int[]) this.magnitude.Clone();
 2966//
 2967//      ShiftRightInPlace(0, res, n);
 2968//
 2969//      return new BigInteger(this.sign, res, true);
 2970
 927732971            int resultLength = (BitLength - n + 31) >> 5;
 927732972            int[] res = new int[resultLength];
 2973
 927732974            int numInts = n >> 5;
 927732975            int numBits = n & 31;
 2976
 927732977            if (numBits == 0)
 666512978            {
 666512979                Array.Copy(this.magnitude, 0, res, 0, res.Length);
 666512980            }
 2981            else
 261222982            {
 261222983                int numBits2 = 32 - numBits;
 2984
 261222985                int magPos = this.magnitude.Length - 1 - numInts;
 9218122986                for (int i = resultLength - 1; i >= 0; --i)
 4347842987                {
 4347842988                    res[i] = (int)((uint) this.magnitude[magPos--] >> numBits);
 2989
 4347842990                    if (magPos >= 0)
 4094322991                    {
 4094322992                        res[i] |= this.magnitude[magPos] << numBits2;
 4094322993                    }
 4347842994                }
 261222995            }
 2996
 927732997            Debug.Assert(res[0] != 0);
 2998
 927732999            return new BigInteger(this.sign, res, false);
 929793000        }
 3001
 3002        public int SignValue
 3003        {
 8895633004            get { return sign; }
 3005        }
 3006
 3007        /**
 3008         * returns x = x - y - we assume x is >= y
 3009         */
 3010        private static int[] Subtract(
 3011            int    xStart,
 3012            int[]  x,
 3013            int    yStart,
 3014            int[]  y)
 779803015        {
 779803016            Debug.Assert(yStart < y.Length);
 779803017            Debug.Assert(x.Length - xStart >= y.Length - yStart);
 3018
 779803019            int iT = x.Length;
 779803020            int iV = y.Length;
 3021            long m;
 779803022            int borrow = 0;
 3023
 3024            do
 10243903025            {
 10243903026                m = (x[--iT] & IMASK) - (y[--iV] & IMASK) + borrow;
 10243903027                x[iT] = (int) m;
 3028
 3029//        borrow = (m < 0) ? -1 : 0;
 10243903030                borrow = (int)(m >> 63);
 10243903031            }
 10243903032            while (iV > yStart);
 3033
 779803034            if (borrow != 0)
 118833035            {
 118833036                while (--x[--iT] == -1)
 03037                {
 03038                }
 118833039            }
 3040
 779803041            return x;
 779803042        }
 3043
 3044        public BigInteger Subtract(
 3045            BigInteger n)
 779463046        {
 779463047            if (n.sign == 0)
 1263048                return this;
 3049
 778203050            if (this.sign == 0)
 03051                return n.Negate();
 3052
 778203053            if (this.sign != n.sign)
 03054                return Add(n.Negate());
 3055
 778203056            int compare = CompareNoLeadingZeroes(0, magnitude, 0, n.magnitude);
 778203057            if (compare == 0)
 03058                return Zero;
 3059
 3060            BigInteger bigun, lilun;
 778203061            if (compare < 0)
 109313062            {
 109313063                bigun = n;
 109313064                lilun = this;
 109313065            }
 3066            else
 668893067            {
 668893068                bigun = this;
 668893069                lilun = n;
 668893070            }
 3071
 778203072            return new BigInteger(this.sign * compare, doSubBigLil(bigun.magnitude, lilun.magnitude), true);
 779463073        }
 3074
 3075        private static int[] doSubBigLil(
 3076            int[]  bigMag,
 3077            int[]  lilMag)
 778203078        {
 778203079            int[] res = (int[]) bigMag.Clone();
 3080
 778203081            return Subtract(0, res, 0, lilMag);
 778203082        }
 3083
 3084        public byte[] ToByteArray()
 3933085        {
 3933086            return ToByteArray(false);
 3933087        }
 3088
 3089        public byte[] ToByteArrayUnsigned()
 363090        {
 363091            return ToByteArray(true);
 363092        }
 3093
 3094        private byte[] ToByteArray(
 3095            bool unsigned)
 4293096        {
 4293097            if (sign == 0)
 03098                return unsigned ? ZeroEncoding : new byte[1];
 3099
 4293100            int nBits = (unsigned && sign > 0)
 4293101                ?  BitLength
 4293102                :  BitLength + 1;
 3103
 4293104            int nBytes = GetByteLength(nBits);
 4293105            byte[] bytes = new byte[nBytes];
 3106
 4293107            int magIndex = magnitude.Length;
 4293108            int bytesIndex = bytes.Length;
 3109
 4293110            if (sign > 0)
 4293111            {
 52913112                while (magIndex > 1)
 48623113                {
 48623114                    uint mag = (uint) magnitude[--magIndex];
 48623115                    bytes[--bytesIndex] = (byte) mag;
 48623116                    bytes[--bytesIndex] = (byte)(mag >> 8);
 48623117                    bytes[--bytesIndex] = (byte)(mag >> 16);
 48623118                    bytes[--bytesIndex] = (byte)(mag >> 24);
 48623119                }
 3120
 4293121                uint lastMag = (uint) magnitude[0];
 13623122                while (lastMag > byte.MaxValue)
 9333123                {
 9333124                    bytes[--bytesIndex] = (byte) lastMag;
 9333125                    lastMag >>= 8;
 9333126                }
 3127
 4293128                bytes[--bytesIndex] = (byte) lastMag;
 4293129            }
 3130            else // sign < 0
 03131            {
 03132                bool carry = true;
 3133
 03134                while (magIndex > 1)
 03135                {
 03136                    uint mag = ~((uint) magnitude[--magIndex]);
 3137
 03138                    if (carry)
 03139                    {
 03140                        carry = (++mag == uint.MinValue);
 03141                    }
 3142
 03143                    bytes[--bytesIndex] = (byte) mag;
 03144                    bytes[--bytesIndex] = (byte)(mag >> 8);
 03145                    bytes[--bytesIndex] = (byte)(mag >> 16);
 03146                    bytes[--bytesIndex] = (byte)(mag >> 24);
 03147                }
 3148
 03149                uint lastMag = (uint) magnitude[0];
 3150
 03151                if (carry)
 03152                {
 3153                    // Never wraps because magnitude[0] != 0
 03154                    --lastMag;
 03155                }
 3156
 03157                while (lastMag > byte.MaxValue)
 03158                {
 03159                    bytes[--bytesIndex] = (byte) ~lastMag;
 03160                    lastMag >>= 8;
 03161                }
 3162
 03163                bytes[--bytesIndex] = (byte) ~lastMag;
 3164
 03165                if (bytesIndex > 0)
 03166                {
 03167                    bytes[--bytesIndex] = byte.MaxValue;
 03168                }
 03169            }
 3170
 4293171            return bytes;
 4293172        }
 3173
 3174        public override string ToString()
 03175        {
 03176            return ToString(10);
 03177        }
 3178
 3179        public string ToString(int radix)
 03180        {
 3181            // TODO Make this method work for other radices (ideally 2 <= radix <= 36 as in Java)
 3182
 03183            switch (radix)
 3184            {
 3185                case 2:
 3186                case 8:
 3187                case 10:
 3188                case 16:
 03189                    break;
 3190                default:
 03191                    throw new FormatException("Only bases 2, 8, 10, 16 are allowed");
 3192            }
 3193
 3194            // NB: Can only happen to internally managed instances
 03195            if (magnitude == null)
 03196                return "null";
 3197
 03198            if (sign == 0)
 03199                return "0";
 3200
 3201
 3202            // NOTE: This *should* be unnecessary, since the magnitude *should* never have leading zero digits
 03203            int firstNonZero = 0;
 03204            while (firstNonZero < magnitude.Length)
 03205            {
 03206                if (magnitude[firstNonZero] != 0)
 03207                {
 03208                    break;
 3209                }
 03210                ++firstNonZero;
 03211            }
 3212
 03213            if (firstNonZero == magnitude.Length)
 03214            {
 03215                return "0";
 3216            }
 3217
 3218
 03219            StringBuilder sb = new StringBuilder();
 03220            if (sign == -1)
 03221            {
 03222                sb.Append('-');
 03223            }
 3224
 03225            switch (radix)
 3226            {
 3227            case 2:
 03228            {
 03229                int pos = firstNonZero;
 03230                sb.Append(Convert.ToString(magnitude[pos], 2));
 03231                while (++pos < magnitude.Length)
 03232                {
 03233                    AppendZeroExtendedString(sb, Convert.ToString(magnitude[pos], 2), 32);
 03234                }
 03235                break;
 3236            }
 3237            case 8:
 03238            {
 03239                int mask = (1 << 30) - 1;
 03240                BigInteger u = this.Abs();
 03241                int bits = u.BitLength;
 03242                IList S = new List<object>();
 03243                while (bits > 30)
 03244                {
 03245                    S.Add(Convert.ToString(u.IntValue & mask, 8));
 03246                    u = u.ShiftRight(30);
 03247                    bits -= 30;
 03248                }
 03249                sb.Append(Convert.ToString(u.IntValue, 8));
 03250                for (int i = S.Count - 1; i >= 0; --i)
 03251                {
 03252                    AppendZeroExtendedString(sb, (string)S[i], 10);
 03253                }
 03254                break;
 3255            }
 3256            case 16:
 03257            {
 03258                int pos = firstNonZero;
 03259                sb.Append(Convert.ToString(magnitude[pos], 16));
 03260                while (++pos < magnitude.Length)
 03261                {
 03262                    AppendZeroExtendedString(sb, Convert.ToString(magnitude[pos], 16), 8);
 03263                }
 03264                break;
 3265            }
 3266            // TODO This could work for other radices if there is an alternative to Convert.ToString method
 3267            //default:
 3268            case 10:
 03269            {
 03270                BigInteger q = this.Abs();
 03271                if (q.BitLength < 64)
 03272                {
 03273                    sb.Append(Convert.ToString(q.LongValue, radix));
 03274                    break;
 3275                }
 3276
 3277                // TODO Could cache the moduli for each radix (soft reference?)
 03278                IList moduli = new List<object>();
 03279                BigInteger R = BigInteger.ValueOf(radix);
 03280                while (R.CompareTo(q) <= 0)
 03281                {
 03282                    moduli.Add(R);
 03283                    R = R.Square();
 03284                }
 3285
 03286                int scale = moduli.Count;
 03287                sb.EnsureCapacity(sb.Length + (1 << scale));
 3288
 03289                ToString(sb, radix, moduli, scale, q);
 3290
 03291                break;
 3292            }
 3293            }
 3294
 03295            return sb.ToString();
 03296        }
 3297
 3298        private static void ToString(StringBuilder sb, int radix, IList moduli, int scale, BigInteger pos)
 03299        {
 03300            if (pos.BitLength < 64)
 03301            {
 03302                string s = Convert.ToString(pos.LongValue, radix);
 03303                if (sb.Length > 1 || (sb.Length == 1 && sb[0] != '-'))
 03304                {
 03305                    AppendZeroExtendedString(sb, s, 1 << scale);
 03306                }
 03307                else if (pos.SignValue != 0)
 03308                {
 03309                    sb.Append(s);
 03310                }
 03311                return;
 3312            }
 3313
 03314            BigInteger[] qr = pos.DivideAndRemainder((BigInteger)moduli[--scale]);
 3315
 03316            ToString(sb, radix, moduli, scale, qr[0]);
 03317            ToString(sb, radix, moduli, scale, qr[1]);
 03318        }
 3319
 3320        private static void AppendZeroExtendedString(StringBuilder sb, string s, int minLength)
 03321        {
 03322            for (int len = s.Length; len < minLength; ++len)
 03323            {
 03324                sb.Append('0');
 03325            }
 03326            sb.Append(s);
 03327        }
 3328
 3329        private static BigInteger CreateUValueOf(
 3330            ulong value)
 163331        {
 163332            int msw = (int)(value >> 32);
 163333            int lsw = (int)value;
 3334
 163335            if (msw != 0)
 03336                return new BigInteger(1, new int[] { msw, lsw }, false);
 3337
 163338            if (lsw != 0)
 163339            {
 163340                BigInteger n = new BigInteger(1, new int[] { lsw }, false);
 3341                // Check for a power of two
 163342                if ((lsw & -lsw) == lsw)
 53343                {
 53344                    n.nBits = 1;
 53345                }
 163346                return n;
 3347            }
 3348
 03349            return Zero;
 163350        }
 3351
 3352        private static BigInteger CreateValueOf(
 3353            long value)
 03354        {
 03355            if (value < 0)
 03356            {
 03357                if (value == long.MinValue)
 03358                    return CreateValueOf(~value).Not();
 3359
 03360                return CreateValueOf(-value).Negate();
 3361            }
 3362
 03363            return CreateUValueOf((ulong)value);
 03364        }
 3365
 3366        public static BigInteger ValueOf(
 3367            long value)
 43368        {
 43369            if (value >= 0 && value < SMALL_CONSTANTS.Length)
 43370            {
 43371                return SMALL_CONSTANTS[value];
 3372            }
 3373
 03374            return CreateValueOf(value);
 43375        }
 3376
 3377        public int GetLowestSetBit()
 03378        {
 03379            if (this.sign == 0)
 03380                return -1;
 3381
 03382            return GetLowestSetBitMaskFirst(-1);
 03383        }
 3384
 3385        private int GetLowestSetBitMaskFirst(int firstWordMask)
 03386        {
 03387            int w = magnitude.Length, offset = 0;
 3388
 03389            uint word = (uint)(magnitude[--w] & firstWordMask);
 03390            Debug.Assert(magnitude[0] != 0);
 3391
 03392            while (word == 0)
 03393            {
 03394                word = (uint)magnitude[--w];
 03395                offset += 32;
 03396            }
 3397
 03398            while ((word & 0xFF) == 0)
 03399            {
 03400                word >>= 8;
 03401                offset += 8;
 03402            }
 3403
 03404            while ((word & 1) == 0)
 03405            {
 03406                word >>= 1;
 03407                ++offset;
 03408            }
 3409
 03410            return offset;
 03411        }
 3412
 3413        public bool TestBit(
 3414            int n)
 10263415        {
 10263416            if (n < 0)
 03417                throw new ArithmeticException("Bit position must not be negative");
 3418
 10263419            if (sign < 0)
 03420                return !Not().TestBit(n);
 3421
 10263422            int wordNum = n / 32;
 10263423            if (wordNum >= magnitude.Length)
 03424                return false;
 3425
 10263426            int word = magnitude[magnitude.Length - 1 - wordNum];
 10263427            return ((word >> (n % 32)) & 1) > 0;
 10263428        }
 3429
 3430        public BigInteger Or(
 3431            BigInteger value)
 03432        {
 03433            if (this.sign == 0)
 03434                return value;
 3435
 03436            if (value.sign == 0)
 03437                return this;
 3438
 03439            int[] aMag = this.sign > 0
 03440                ? this.magnitude
 03441                : Add(One).magnitude;
 3442
 03443            int[] bMag = value.sign > 0
 03444                ? value.magnitude
 03445                : value.Add(One).magnitude;
 3446
 03447            bool resultNeg = sign < 0 || value.sign < 0;
 03448            int resultLength = System.Math.Max(aMag.Length, bMag.Length);
 03449            int[] resultMag = new int[resultLength];
 3450
 03451            int aStart = resultMag.Length - aMag.Length;
 03452            int bStart = resultMag.Length - bMag.Length;
 3453
 03454            for (int i = 0; i < resultMag.Length; ++i)
 03455            {
 03456                int aWord = i >= aStart ? aMag[i - aStart] : 0;
 03457                int bWord = i >= bStart ? bMag[i - bStart] : 0;
 3458
 03459                if (this.sign < 0)
 03460                {
 03461                    aWord = ~aWord;
 03462                }
 3463
 03464                if (value.sign < 0)
 03465                {
 03466                    bWord = ~bWord;
 03467                }
 3468
 03469                resultMag[i] = aWord | bWord;
 3470
 03471                if (resultNeg)
 03472                {
 03473                    resultMag[i] = ~resultMag[i];
 03474                }
 03475            }
 3476
 03477            BigInteger result = new BigInteger(1, resultMag, true);
 3478
 3479            // TODO Optimise this case
 03480            if (resultNeg)
 03481            {
 03482                result = result.Not();
 03483            }
 3484
 03485            return result;
 03486        }
 3487
 3488        public BigInteger Xor(
 3489            BigInteger value)
 93490        {
 93491            if (this.sign == 0)
 03492                return value;
 3493
 93494            if (value.sign == 0)
 03495                return this;
 3496
 93497            int[] aMag = this.sign > 0
 93498                ? this.magnitude
 93499                : Add(One).magnitude;
 3500
 93501            int[] bMag = value.sign > 0
 93502                ? value.magnitude
 93503                : value.Add(One).magnitude;
 3504
 3505            // TODO Can just replace with sign != value.sign?
 93506            bool resultNeg = (sign < 0 && value.sign >= 0) || (sign >= 0 && value.sign < 0);
 93507            int resultLength = System.Math.Max(aMag.Length, bMag.Length);
 93508            int[] resultMag = new int[resultLength];
 3509
 93510            int aStart = resultMag.Length - aMag.Length;
 93511            int bStart = resultMag.Length - bMag.Length;
 3512
 2463513            for (int i = 0; i < resultMag.Length; ++i)
 1143514            {
 1143515                int aWord = i >= aStart ? aMag[i - aStart] : 0;
 1143516                int bWord = i >= bStart ? bMag[i - bStart] : 0;
 3517
 1143518                if (this.sign < 0)
 03519                {
 03520                    aWord = ~aWord;
 03521                }
 3522
 1143523                if (value.sign < 0)
 03524                {
 03525                    bWord = ~bWord;
 03526                }
 3527
 1143528                resultMag[i] = aWord ^ bWord;
 3529
 1143530                if (resultNeg)
 03531                {
 03532                    resultMag[i] = ~resultMag[i];
 03533                }
 1143534            }
 3535
 93536            BigInteger result = new BigInteger(1, resultMag, true);
 3537
 3538            // TODO Optimise this case
 93539            if (resultNeg)
 03540            {
 03541                result = result.Not();
 03542            }
 3543
 93544            return result;
 93545        }
 3546
 3547        public BigInteger SetBit(
 3548            int n)
 03549        {
 03550            if (n < 0)
 03551                throw new ArithmeticException("Bit address less than zero");
 3552
 03553            if (TestBit(n))
 03554                return this;
 3555
 3556            // TODO Handle negative values and zero
 03557            if (sign > 0 && n < (BitLength - 1))
 03558                return FlipExistingBit(n);
 3559
 03560            return Or(One.ShiftLeft(n));
 03561        }
 3562
 3563        public BigInteger ClearBit(
 3564            int n)
 03565        {
 03566            if (n < 0)
 03567                throw new ArithmeticException("Bit address less than zero");
 3568
 03569            if (!TestBit(n))
 03570                return this;
 3571
 3572            // TODO Handle negative values
 03573            if (sign > 0 && n < (BitLength - 1))
 03574                return FlipExistingBit(n);
 3575
 03576            return AndNot(One.ShiftLeft(n));
 03577        }
 3578
 3579        public BigInteger FlipBit(
 3580            int n)
 03581        {
 03582            if (n < 0)
 03583                throw new ArithmeticException("Bit address less than zero");
 3584
 3585            // TODO Handle negative values and zero
 03586            if (sign > 0 && n < (BitLength - 1))
 03587                return FlipExistingBit(n);
 3588
 03589            return Xor(One.ShiftLeft(n));
 03590        }
 3591
 3592        private BigInteger FlipExistingBit(
 3593            int n)
 03594        {
 03595            Debug.Assert(sign > 0);
 03596            Debug.Assert(n >= 0);
 03597            Debug.Assert(n < BitLength - 1);
 3598
 03599            int[] mag = (int[]) this.magnitude.Clone();
 03600            mag[mag.Length - 1 - (n >> 5)] ^= (1 << (n & 31)); // Flip bit
 3601            //mag[mag.Length - 1 - (n / 32)] ^= (1 << (n % 32));
 03602            return new BigInteger(this.sign, mag, false);
 03603        }
 3604    }
 3605}
Generated by: ReportGenerator 5.2.0.0
11/29/2023 - 11:22:39 AM
GitHub | reportgenerator.io

Methods/Properties

.cctor()
.ctor(System.Int32,System.Int32[],System.Boolean)
GetByteLength(System.Int32)
Arbitrary(System.Int32)
.ctor(System.String)
.ctor(System.String,System.Int32)
.ctor(System.Byte[])
.ctor(System.Byte[],System.Int32,System.Int32)
MakeMagnitude(System.Byte[],System.Int32,System.Int32)
.ctor(System.Int32,System.Byte[])
.ctor(System.Int32,System.Byte[],System.Int32,System.Int32)
.ctor(System.Int32,System.Random)
.ctor(System.Int32,System.Int32,System.Random)
Abs()
AddMagnitudes(System.Int32[],System.Int32[])
Add(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
AddToMagnitude(System.Int32[])
And(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
AndNot(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
get_BitCount()
BitCnt(System.Int32)
CalcBitLength(System.Int32,System.Int32,System.Int32[])
get_BitLength()
BitLen(System.Int32)
QuickPow2Check()
CompareTo(System.Object)
CompareTo(System.Int32,System.Int32[],System.Int32,System.Int32[])
CompareNoLeadingZeroes(System.Int32,System.Int32[],System.Int32,System.Int32[])
CompareTo(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
Divide(System.Int32[],System.Int32[])
Divide(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
DivideAndRemainder(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
Equals(System.Object)
IsEqualMagnitude(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
Gcd(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
GetHashCode()
Inc()
get_IntValue()
IsProbablePrime(System.Int32)
IsProbablePrime(System.Int32,System.Boolean)
CheckProbablePrime(System.Int32,System.Random,System.Boolean)
RabinMillerTest(System.Int32,System.Random)
RabinMillerTest(System.Int32,System.Random,System.Boolean)
get_LongValue()
Max(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
Min(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
Mod(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
ModInverse(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
ModInversePow2(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
ModInverse32(System.Int32)
ModInverse64(System.Int64)
ExtEuclid(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger&)
ZeroOut(System.Int32[])
ModPow(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
ModPowBarrett(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
ReduceBarrett(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
ModPowMonty(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger,System.Boolean)
GetWindowList(System.Int32[],System.Int32)
CreateWindowEntry(System.Int32,System.Int32)
Square(System.Int32[],System.Int32[])
Multiply(System.Int32[],System.Int32[],System.Int32[])
GetMQuote()
MontgomeryReduce(System.Int32[],System.Int32[],System.UInt32)
MultiplyMonty(System.Int32[],System.Int32[],System.Int32[],System.Int32[],System.UInt32,System.Boolean)
SquareMonty(System.Int32[],System.Int32[],System.Int32[],System.UInt32,System.Boolean)
MultiplyMontyNIsOne(System.UInt32,System.UInt32,System.UInt32,System.UInt32)
Multiply(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
Square()
Negate()
NextProbablePrime()
Not()
Pow(System.Int32)
ProbablePrime(System.Int32,System.Random)
Remainder(System.Int32)
Remainder(System.Int32[],System.Int32[])
Remainder(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
LastNBits(System.Int32)
DivideWords(System.Int32)
RemainderWords(System.Int32)
ShiftLeft(System.Int32[],System.Int32)
ShiftLeftOneInPlace(System.Int32[],System.Int32)
ShiftLeft(System.Int32)
ShiftRightInPlace(System.Int32,System.Int32[],System.Int32)
ShiftRightOneInPlace(System.Int32,System.Int32[])
ShiftRight(System.Int32)
get_SignValue()
Subtract(System.Int32,System.Int32[],System.Int32,System.Int32[])
Subtract(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
doSubBigLil(System.Int32[],System.Int32[])
ToByteArray()
ToByteArrayUnsigned()
ToByteArray(System.Boolean)
ToString()
ToString(System.Int32)
ToString(System.Text.StringBuilder,System.Int32,System.Collections.IList,System.Int32,Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
AppendZeroExtendedString(System.Text.StringBuilder,System.String,System.Int32)
CreateUValueOf(System.UInt64)
CreateValueOf(System.Int64)
ValueOf(System.Int64)
GetLowestSetBit()
GetLowestSetBitMaskFirst(System.Int32)
TestBit(System.Int32)
Or(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
Xor(Renci.SshNet.Security.Org.BouncyCastle.Math.BigInteger)
SetBit(System.Int32)
ClearBit(System.Int32)
FlipBit(System.Int32)
FlipExistingBit(System.Int32)