ubiginteger.cs

使用非对成RSA算法的序列号验证基础库

			//result.nLength = result.nCapacity - nLenResult;
			return result;
		}

		/// <summary>
		/// 重载/运算符，进行大整数除法运算
		/// </summary>
		/// <param name="dividend">被除数</param>
		/// <param name="divisor">除数</param>
		/// <returns>返回一个大整数，它表示被除数除以除数之后的结果</returns>
		/// <remarks>如果除数为零，将引发除零异常</remarks>
		public static UBigInteger operator /(UBigInteger dividend, UBigInteger divisor)
		{
			if(divisor == 0u)
				throw new DivideByZeroException();

			if(divisor.nLength == 1)
				return (dividend / divisor.values[divisor.nCapacity - 1]);

			UBigInteger result = new UBigInteger(dividend.nCapacity);
			UBigInteger div = new UBigInteger(dividend);

			int startDivisor = divisor.nCapacity - divisor.nLength;

			ulong i64Dividend, i64Divisor;

			i64Divisor = divisor.values[startDivisor];

			while(div >= divisor)
			{
				//int nDividendLength = div.nLength;
				int startLeft = div.nCapacity - div.nLength;
				int digitPosition = div.nLength - divisor.nLength;

				i64Dividend = div.values[startLeft];
				if(i64Dividend == i64Divisor && digitPosition == 0)
				{
					result ++;
					break;
				}
				if(i64Dividend <= i64Divisor && digitPosition > 0)
				{
					i64Dividend <<= 32;
					i64Dividend += div.values[++ startLeft];
					digitPosition --;
				}

				uint nResult = (uint)(i64Dividend / (i64Divisor + 1));
				//result.values[digitPosition] += nResult;
				UBigInteger temp = (divisor * nResult);
				temp.LeftShift(digitPosition);
				div.Item = (div - temp);

				temp.Assign(nResult);
				temp.LeftShift(digitPosition);
				result.Item = (result + temp);
			}
			result.RefreshLength();
			return result;
		}

		/// <summary>
		/// 无符号大整数除以32位无符号整数
		/// </summary>
		/// <param name="dividend">被除数</param>
		/// <param name="divisor">除数</param>
		/// <returns>返回一个结果，代表被除数除以除数之后的结果</returns>
		public static UBigInteger operator /(UBigInteger dividend, uint divisor)
		{
			UBigInteger result = new UBigInteger(dividend.nLength);

			if(divisor == 0)
			{
				throw new DivideByZeroException();
			}

			int nStart = dividend.nCapacity - dividend.nLength;
			ulong temp;
			uint remainder = 0;
			int nResultStart = 0;
			while(nStart < dividend.nCapacity)
			{
				temp = remainder;
				temp <<= 32;
				temp += dividend.values[nStart];
				result.values[nResultStart++] = (uint)(temp / divisor);
				remainder = (uint)(temp % divisor);
				nStart ++;
			}
			result.RefreshLength();

			return result;
		}

		/// <summary>
		/// 重载运算符 %，返回被除数除以除数之后的余数
		/// </summary>
		/// <param name="dividend">被除数</param>
		/// <param name="divisor">除数</param>
		/// <returns>返回被除数除以除数之后的模</returns>
		public static UBigInteger operator %(UBigInteger dividend, UBigInteger divisor)
		{
			UBigInteger remainder = new UBigInteger(dividend);
			UBigInteger result = new UBigInteger(dividend.nCapacity);

			//		uint quotient;
			ulong i64Dividend, i64Divisor;

			int nStartDividend = dividend.nCapacity - dividend.nLength;
			int nStartDivisor = divisor.nCapacity - divisor.nLength;

			i64Divisor = divisor.values[nStartDivisor];
			while((remainder >= divisor))
			{
				int nPosition = remainder.nLength - divisor.nLength;
				nStartDividend = remainder.nCapacity - remainder.nLength;
				i64Dividend = remainder.values[nStartDividend];
				if(i64Dividend == i64Divisor && nPosition == 0)
				{
					remainder.Item = remainder - divisor;
					break;
				}
				if(i64Dividend <= i64Divisor && nPosition > 0)
				{
					i64Dividend <<= 32;
					i64Dividend += remainder.values[++nStartDividend];
					nPosition --;
				}

				result.Assign((uint)(i64Dividend / (i64Divisor + 1)));
				result.LeftShift(nPosition);

				UBigInteger product = (result * divisor);
				remainder.Item = (remainder - product);
			}
			return remainder;
		}

		/// <summary>
		/// 大整数除以无符号32位整数的模
		/// </summary>
		/// <param name="dividend">被除数</param>
		/// <param name="divisor">除数</param>
		/// <returns>返回大整数除以无符号32位整数的模</returns>
		public static uint operator %(UBigInteger dividend, uint divisor)
		{
			if(divisor == 0)
				return 0;

			int nStart = dividend.nCapacity - dividend.nLength;
			uint remainder = 0;
			ulong temp;
			while(nStart < dividend.nCapacity)
			{
				temp = remainder;
				temp <<= 32;
				temp += dividend.values[nStart++];
				remainder = (uint)(temp % divisor);
			}
			return remainder;
		}

		/// <summary>
		/// 重载运算符++
		/// </summary>
		/// <param name="addend">被累加的大整数</param>
		/// <returns>返回被累加的大整数</returns>
		public static UBigInteger operator++(UBigInteger addend)
		{
			return addend.Addition(1);
		}

		/// <summary>
		/// 重载运算符--
		/// </summary>
		/// <param name="minuend">递减的大整数</param>
		/// <returns>返回递减之后的无符号大整数</returns>
		public static UBigInteger operator--(UBigInteger minuend)
		{
			return minuend.Subtraction(1);
		}

		/// <summary>
		/// 重载运算符 ==，判断大整数是否与一个无符号32位整数相等
		/// </summary>
		/// <param name="left">被比较的大整数</param>
		/// <param name="right">用来比较的32位无符号整数</param>
		/// <returns>如果相等，返回真值，否则返回假</returns>
		public static bool operator ==(UBigInteger left, uint right)
		{
			if(left.nLength == 1 && left.values[left.nCapacity - 1] == right)
				return true;
			if(left.nLength == 0 && right ==0)
				return true;

			return false;
		}
		/// <summary>
		/// 重载运算符==，判断两个大整数是否相等
		/// </summary>
		/// <param name="left">相等比较运算符左边大整数</param>
		/// <param name="right">右边大整数</param>
		/// <returns>如果相等，返回真值，否则返回假</returns>
		public static bool operator ==(UBigInteger left, UBigInteger right)
		{
			// the following statements are to for overloading the == to a reference class
			if((object)left == null && (object)right == null)
				return true;
			if((object)left == null ^ (object)right == null)
				return false;

			if(left.nLength != right.nLength)
				return false;

			int nEndLeft = left.nCapacity;
			int nEndRight = right.nCapacity;

			int nNumber = left.nLength;
			while(nNumber -- > 0)
			{
				if(left.values[--nEndLeft] != right.values[--nEndRight])
					return false;
			}
			return true;
		}
		/// <summary>
		/// 重载运算符 !=，判断两个无符号大整数是否不等
		/// </summary>
		/// <param name="left">比较运算的左边大整数</param>
		/// <param name="right">运算符右边大整数</param>
		/// <returns>如果两个大整数不等，返回真值，否则返回假</returns>
		public static bool operator !=(UBigInteger left, UBigInteger right)
		{
			return !(left == right);
		}
		/// <summary>
		/// 重载运算符 !=，比较大整数是否与一个无符号32位整数不等
		/// </summary>
		/// <param name="left">不等运算符左边大整数</param>
		/// <param name="right">不等运算符右边无符号32位整数</param>
		/// <returns>如果两者不等，返回真值，否则返回假</returns>
		public static bool operator !=(UBigInteger left, uint right)
		{
			return !(left == right);
		}

		/// <summary>
		/// 重载运算符 >，判断两个大整数之间关系
		/// </summary>
		/// <param name="left">比较运算符左边大整数</param>
		/// <param name="right">比较运算符右边大整数</param>
		/// <returns>如果左边的大整数大于右边大整数，返回真值，否则返回假</returns>
		public static bool operator > (UBigInteger left, UBigInteger right)
		{
			if(left.nLength > right.nLength)
				return true;
			if(left.nLength < right.nLength)
				return false;

			int startLeft = left.nCapacity - left.nLength;
			int startRight = right.nCapacity - right.nLength;
			while(startLeft < left.nCapacity)
			{
				uint leftValue = left.values[startLeft ++];
				uint rightValue = right.values[startRight ++];

				if(leftValue > rightValue)
					return true;

				if(leftValue < rightValue)
					return false;
			}
			return false;
		}
		/// <summary>
		/// 重载预算符 >,判断一个大整数是否大于一个32位无符号整数
		/// </summary>
		/// <param name="left">运算符左边大整数</param>
		/// <param name="right">运算符右边32位无符号整数</param>
		/// <returns>如果左边大数大于右边整数，返回真值，否则返回假</returns>
		public static bool operator > (UBigInteger left, uint right)
		{
			if(left.nLength > 1)
				return true;
			if(left.nLength == 1 && left.values[left.nCapacity - 1] > right)
				return true;

			return false;
		}

		/// <summary>
		/// 重载运算符<=
		/// </summary>
		/// <param name="left"></param>
		/// <param name="right"></param>
		/// <returns></returns>
		public static bool operator <= (UBigInteger left, UBigInteger right)
		{
			return !(left > right);
		}
		/// <summary>
		/// 重载运算符<=
		/// </summary>
		/// <param name="left"></param>
		/// <param name="right"></param>
		/// <returns></returns>
		public static bool operator <= (UBigInteger left, uint right)
		{
			return !(left > right);
		}

		/// <summary>
		/// 重载运算符 <
		/// </summary>
		/// <param name="left"></param>
		/// <param name="right"></param>
		/// <returns>如果运算符左边大数小于右边大书，返回真值，否则返回假</returns>
		public static bool operator < (UBigInteger left, UBigInteger right)
		{
			if(left.nLength < right.nLength)
				return true;
			if(left.nLength > right.nLength)
				return false;

			int startLeft = left.nCapacity - left.nLength;
			int startRight = right.nCapacity - right.nLength;
			while(startLeft < left.nCapacity)
			{
				uint leftValue = left.values[startLeft ++];
				uint rightValue = right.values[startRight ++];

				if(leftValue < rightValue)
					return true;

				if(leftValue > rightValue)
					return false;
			}
			return false;
		}
		/// <summary>
		/// 重载运算符<,比较大整数和无符号32位整数
		/// </summary>
		/// <param name="left"></param>
		/// <param name="right"></param>
		/// <returns>如果左边的值小于右边的32位整数，返回真值，否则返回假</returns>
		public static bool operator < (UBigInteger left, uint right)
		{
			if(left.nLength > 1)
				return false;
			if(left.nLength == 0)
				return false;
			if(left.nLength == 1 && left.values[left.nCapacity - 1] >= right)
				return false;
			return true;
		}
		/// <summary>
		/// 重载运算符 >=
		/// </summary>
		/// <param name="left"></param>
		/// <param name="right"></param>
		/// <returns>如果左边大数大于等于右边大书，返回真值，否则返回假</returns>
		public static bool operator >= (UBigInteger left, UBigInteger right)
		{
			return !(left < right);
		}
		/// <summary>
		/// 重载运算符 >=, 表较大整数和32位无符号整数
		/// </summary>
		/// <param name="left"></param>
		/// <param name="right"></param>
		/// <returns>如果左边数据大于等于右边32位整数，返回真值，否则返回假</returns>
		public static bool operator >= (UBigInteger left, uint right)
		{
			return !(left < right);
		}
		#endregion

		#region 改变自身的运算程序
		/// <summary>
		/// 将自身取余:Num = Num.Modulus(divisor)，相当于 Num %= divisor
		/// </summary>
		/// <param name="divisor">除数</param>
		/// <returns>返回结果是被取余的自身数据</returns>
		public UBigInteger Modulus(UBigInteger divisor)
		{
			UBigInteger remainder = this;
			UBigInteger result = new UBigInteger(nCapacity);

			ulong i64Dividend;

			ulong nDivisor = divisor.values[divisor.nCapacity - divisor.nLength];
			while((remainder >= divisor))
			{
				int nPosition = remainder.nLength - divisor.nLength;
				int nStartDividend = remainder.nCapacity - remainder.nLength;

				i64Dividend = remainder.values[nStartDividend];
				if(i64Dividend == nDivisor && nPosition == 0)
				{
					remainder.Subtraction(divisor);
					break;
				}
				if(i64Dividend <= nDivisor && nPosition > 0)
				{
					i64Dividend <<= 32;
					i64Dividend += remainder.values[++nStartDividend];
					nPosition --;
				}

				result.Assign((uint)(i64Dividend / (nDivisor + 1)));
				result.LeftShift(nPosition);

				result.Multiply(divisor);
				remainder.Subtraction(result);
			}
			return remainder;
		}

		/// <summary>
		/// 完整除法，返回商和余数:num = num.Division(divisor, ref remainder)
		/// </summary>
		/// <param name="divisor">除数</param>
		/// <param name="remainder">返回的余数</param>
		/// <returns>返回的自身是它被处以除数之后的商数</returns>
		public UBigInteger Division(uint divisor, ref uint remainder)
		{
			if(divisor == 0)
			{
				throw new DivideByZeroException();
			}

			ulong dividend;
			int nStart = nCapacity - nLength;
			remainder = 0;
			while(nStart < nCapacity)
			{
				dividend = remainder;
				dividend <<= 32;
				dividend += values[nStart];
				values[nStart] = (uint)(dividend / divisor);
				remainder = (uint)(dividend % divisor);
				nStart ++;
			}
			while(nLength > 0 && values[nCapacity - nLength] == 0)
				nLength --;
			return this;
		}

		/// <summary>
		/// 完整除法，返回商和余数:num = num.Division(divisor, ref remainder)
		/// </summary>
		/// <param name="divisor">除数</param>
		/// <param name="remainder">余数</param>
		/// <returns>返回结果是自身被处以除数之后的商数</returns>
		public UBigInteger Division(UBigInteger divisor, ref UBigInteger remainder)
		{
			if(divisor == 0u)
				throw new DivideByZeroException();

			remainder = new UBigInteger(this);
			if(divisor.nLength == 1)
			{
				uint rem = 0;
				this.Division(divisor.values[divisor.nCapacity - 1], ref rem);
				remainder.Assign(rem);
				return this;
			}

			this.Assign(0);

			//int startDivisor = divisor.nCapacity - divisor.nLength;

			ulong i64Dividend;//, i64Divisor;
			ulong nDivisor = divisor.values[divisor.nCapacity - divisor.nLength];

			//i64Divisor = divisor.values[startDivisor];
			UBigInteger temp = new UBigInteger((remainder).nCapacity);
			UBigInteger div = remainder;
			while(div >= divisor)
			{
				int startLeft = div.nCapacity - div.nLength;
				int digitPosition = div.nLength - divisor.nLength;

				i64Dividend = div.values[startLeft];
				if(i64Dividend == nDivisor && digitPosition == 0)
				{
					//					op_Increment(this);
					this.Addition(1);
					div.Subtraction(divisor);
					break;
				}
				if(i64Dividend <= nDivisor && digitPosition > 0)
				{
					i64Dividend <<= 32;
					i64Dividend += div.values[++ startLeft];
					digitPosition --;
				}

				uint nResult = (uint)(i64Dividend / (nDivisor + 1));
				//result.values[digitPosition] += nResult;
				temp.Item = divisor;
				temp.Multiply(nResult);
				//UBigInteger temp = (divisor * nResult);
				temp.LeftShift(digitPosition);
				div.Subtraction(temp);

				temp.Assign(nResult);
				temp.LeftShift(digitPosition);
				this.Addition(temp);
				//			Item = (result + temp);
			}
			//		result.RefreshLength();
			return this;
		}

		// 
		/// <summary>
		/// 将指定大整数乘数:num = num.Multiply(multiplier)，相当于Num *= multiplier
		/// </summary>
		/// <param name="multiplier">乘数</param>
		/// <returns>返回自身，结果为乘以乘数之后的积</returns>
		public UBigInteger Multiply(uint multiplier)
		{
			if(multiplier == 0)
			{
				nLength = 0;
				return this;
			}

			int nLoop = nLength;
			int nEnd = nCapacity;
			ulong sum = 0;
			uint carry = 0;
			while(nLoop -- > 0)
			{
				sum = values[--nEnd];
				sum *= multiplier;
				sum += carry;
				values[nEnd] = (uint)sum;
				carry = (uint)(sum >> 32);
			}
			if(carry > 0)
			{
				if(nEnd > 0)
				{
					values[--nEnd] = carry;
				}
				else
				{
					uint[] expanded = new uint[nCapacity + 1];