From 7167ce41b61d2ba2cdb526777a4233eb84a3b66a Mon Sep 17 00:00:00 2001 From: Unit 193 Date: Sat, 6 Dec 2014 17:33:25 -0500 Subject: Imported Upstream version 2.99.6 --- SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp | 1151 +++++++++++++++++++++++++ 1 file changed, 1151 insertions(+) create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp (limited to 'SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp') diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp b/SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp new file mode 100644 index 0000000..0579add --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp @@ -0,0 +1,1151 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * BigInt.cpp + * + * Author: Nedim Srndic + * Release date: 14th of March 2008 + * + * This file contains the implementation for the BigInt class. + * + * There are two static constants defined in this file: + * + * - ULongMax : ULONG_MAX (defined in climits) of type BigInt + * Mainly used for speedup in the multiply() private member function. + * Represents the largest unsigned long integer a particular platform can + * handle. If a BigInt is <= ULongMax, it can be converted to unsigned + * long int. This is platform-specific. + * - SqrtUlongMax : sqrt(ULONG_MAX) of type BigInt + * Mainly used for speedup in the multiply() private member function. + * Represents the square root of the largest unsigned long integer a + * particular platform can handle. If two BigInts are <= SqrtULongMax, + * they can be converted to unsigned long int and safely multiplied + * by the CPU. This is platform-specific. + * + * **************************************************************************** + */ + +//comment the following line if you want to use long multiplication +//#define KARATSUBA + +#include "BigInt.h" +#include //strlen() +#include //ULONG_MAX +#include //vector +#include //operator std::string() +#include //reverse_copy(), copy(), copy_backward(), + //fill(), fill_n() + +using std::cout; +using std::endl; + +//define and initialize BigInt::FACTOR +const double BigInt::FACTOR = 1.6; + +//A BigInt number with the value of ULONG_MAX +static const BigInt ULongMax(ULONG_MAX); +//A BigInt number with the value of sqrt(ULONG_MAX) +static const BigInt SqrtULongMax + (static_cast(sqrt(static_cast(ULONG_MAX)))); + +/* Transforms the number from unsigned long int to unsigned char[] + * and pads the result with zeroes. Returns the number of digits. */ +unsigned long int BigInt::int2uchar(unsigned long int number, + unsigned char *digits, + unsigned long int padding = 0L) +{ + int i(0); + do + { + //the number is stored in reverse + //(i.e. long int 456 is stored as unsigned char[] {[6][5][4]}) + digits[i++] = (unsigned char) (number % 10); + number /= 10; + } while (number > 0L); + + std::fill_n(digits + i, padding, 0); + return i; +} + +/* Converts ASCII digits to equivalent unsigned char numeric values. */ +void BigInt::char2uchar(unsigned char *array, + unsigned long int length) +{ + for (unsigned long int i(0L); i < length; i++) + array[i] -= '0'; +} + +/* Check if all ASCII values are digits '0' to '9'. */ +bool BigInt::allCharsAreDigits( const char *array, + unsigned long int length) +{ + for (unsigned long int i(0L); i < length; i++) + if (array[i] < '0' || array[i] > '9') + return false; + + return true; +} + +/* Compares two BigInt. If the last two arguments are + * omitted, the comparison is sign-insensitive (comparison by + * absolute value). Returns 0 if a == b, 1 if a > b, 2 if a < b. */ +int BigInt::compareNumbers( unsigned char *a, unsigned long int na, + unsigned char *b, unsigned long int nb, + bool aPositive, bool bPositive) +{ + if (na < nb || (!aPositive && bPositive)) + //a < b + return 2; + else if (na > nb || (aPositive && !bPositive)) + //a > b + return 1; + + //check the digits one by one starting from the most significant one + for (long int i = na - 1; i >= 0L; i--) + //compare the digits + if (a[i] != b[i]) + { + if (a[i] < b[i]) // |a| < |b| + if (aPositive) + return 2; // a < b + else + return 1; // a > b + else // |a| > |b| + if (aPositive) + return 1; // a > b + else + return 2; // a < b + } + + //a == b + return 0; +} + +/* Multiplies two unsigned char[] using the Divide and Conquer + * a.k.a. Karatsuba algorithm .*/ +void BigInt::karatsubaMultiply( unsigned char *a, unsigned char *b, + unsigned long int n, unsigned char *buf1) +{ + //if *a <= SqrtULongMax && *b <= SqrtULongMax, + //the CPU can do the multiplication + if (compareNumbers(a, n, SqrtULongMax.digits, SqrtULongMax.digitCount) != 1 + && + compareNumbers(b, n, SqrtULongMax.digits, SqrtULongMax.digitCount) != 1 + ) + { + int2uchar(toInt(a, n) * toInt(b, n), buf1, n << 1); + return; + } + + //nh = higher half digits, nl = lower half digits + //nh == nl || nh + 1 == nl + //nt is used to avoid too much nl + 1 addition operations + unsigned long int nh(n >> 1), nl(n - nh), nt(nl + 1); + //t1 is a temporary pointer, points to p1 + unsigned char *t1(buf1 + (n << 1)); + + BigInt::add(a + nl, nh, a, nl, buf1, nt); + BigInt::add(b + nl, nh, b, nl, buf1 + nt, nt); + BigInt::karatsubaMultiply(a + nl, b + nl, nh, t1); //p1 + BigInt::karatsubaMultiply(a, b, nl, t1 + (nh << 1)); //p2 + BigInt::karatsubaMultiply(buf1, buf1 + nt, nt, t1 + (n << 1));//p3 + + //for leftshifting p3 and p1 + unsigned long int power(n); + if (power & 1) + power++; + //since the original multiplier is not needed any more, we can reuse a + a = buf1 + (power >> 1); + //copy and shift left p3 by power / 2 and pad right to n * 2 with zeroes + std::fill(buf1, a, 0); + std::copy(t1 + (n << 1), t1 + ((n + nl) << 1) + 1, a); + std::fill(a + (nl << 1) + 1, t1, 0); + + //shifted p3 -= p2 + //a = shifted p3, b = p2 + BigInt::quickSub(a, t1 + (nh << 1), t1, nl); + + //shifted p3 -= p1 + //a = shifted p3, b = p1 + BigInt::quickSub(a, t1, t1, nh); + + //shifted p3 += shifted p1 + //a = p3[power], b = p1 + a = buf1 + power; + BigInt::quickAdd(a, t1, nh); + + //p3 += p2 + //a = p3, b = p2 + unsigned char carry = BigInt::quickAdd(buf1, t1 + (nh << 1), nl); + a = buf1 + (nl << 1); + for (unsigned long int i(0L); carry; i++) + { + a[i] += 1; + carry = a[i] / 10; + a[i] %= 10; + } +} + +/* Multiplies two unsigned char[] the long way. */ +void BigInt::longMultiply( unsigned char *a, unsigned long int na, + unsigned char *b, unsigned long int nb, + unsigned char *result) +{ + std::fill_n(result, na + nb, 0); + unsigned char mult(0); + int carry(0); + + for (unsigned long int i(0L); i < na; i++) + { + for (unsigned long int j(0L); j < nb; j++) + { + mult = a[i] * b[j] + result[i + j] + carry; + result[i + j] = static_cast(mult) % 10; + carry = static_cast(mult) / 10; + } + if (carry) + { + result[i + nb] += carry; + carry = 0; + } + } +} + +/* Simple addition, used by the multiply function. + * Returns the remaining carry. */ +unsigned char BigInt::quickAdd( unsigned char *a, unsigned char *b, + unsigned long int n) +{ + unsigned char carry(0), sum(0); + for (unsigned long int i(0L); i < (n << 1); i++) + { + sum = a[i] + b[i] + carry; + carry = sum / 10; + a[i] = sum % 10; + } + return carry; +} + +/* Simple subtraction, used by the multiply function. */ +void BigInt::quickSub( unsigned char *a, unsigned char *b, + unsigned char *end, unsigned long int n) +{ + unsigned char carry(0), sum(0); + for (unsigned long int i(0L); i < (n << 1); i++) + { + sum = 10 + a[i] - (b[i] + carry); + if (sum < 10) //carry + { + a[i] = sum; + carry = 1; + } + else + { + a[i] = sum % 10; + carry = 0; + } + } + a = &a[n << 1]; + for (; carry && a < end; a++) + if (*a) + { + (*a)--; + break; + } + else + *a = 9; +} + +/* Divides two BigInt numbers by the formula + * dividend = divisor * quotient + remainder*/ +void BigInt::divide(const BigInt ÷nd, const BigInt &divisor, + BigInt "ient, BigInt &remainder) +{ + BigInt Z1, R, X(dividend.Abs()); + /* Make sure quotient and remainder are zero. + * The lack of this assignment introduces a bug if the actual parameters + * are not zero when calling this function. */ + quotient = BigIntZero; + remainder = BigIntZero; + + // while |X| >= |divisor| + while (BigInt::compareNumbers( X.digits, X.digitCount, + divisor.digits, divisor.digitCount, + true, true) != 2) + { + unsigned long int O(X.digitCount - divisor.digitCount); + if (O <= ULongMax.digitCount - 2) + { + unsigned long int i; + if (X.digitCount > ULongMax.digitCount - 1) + i = ULongMax.digitCount - 1; + else + i = X.digitCount; + unsigned long int j(i - O); + Z1 = toInt(X.digits + X.digitCount - i, i) / + toInt(divisor.digits + divisor.digitCount - j, j); + } + else + { + unsigned long int i(ULongMax.digitCount - 1); + unsigned long int j; + if (divisor.digitCount > ULongMax.digitCount - 2) + j = ULongMax.digitCount - 2; + else + j = divisor.digitCount; + Z1 = toInt(X.digits + X.digitCount - i, i) / + toInt(divisor.digits + divisor.digitCount - j, j); + Z1.shiftLeft(O - Z1.digitCount); + } + + predictZ1: + R = (Z1 * divisor).Abs(); + + if (X >= R) + { + X = X - R; + quotient += Z1; + } + else + { + if (Z1.digitCount > 1) + Z1.shiftRight(1); + else + --Z1; + goto predictZ1; + } + } + + remainder = X; +} + +/* Returns the value of the specified unsigned char[] as long int. */ +unsigned long int BigInt::toInt(unsigned char *digits, int n) +{ + unsigned long int newInt(0L); + unsigned long int powerOf10(1); + for (int i(0); i < n; i++) + { + newInt += digits[i] * powerOf10; + powerOf10 *= 10; + } + return newInt; +} + +/* Saves the sum of two unsigned char* shorter and longer into result. + * It must be nShorter <= nLonger. If doFill == true, it fills the + * remaining free places with zeroes (used in KaratsubaMultiply()). + * Returns true if there was an overflow at the end (meaning that + * the result.digitCount was longer.digitCount + 1. */ +bool BigInt::add(unsigned char *shorter, unsigned long int nShorter, + unsigned char *longer, unsigned long int nLonger, + unsigned char *result, int nResult, bool doFill) +{ + //single digitwise sum and carry + unsigned char subSum(0); + unsigned char subCarry(0); + + //count the digits + unsigned long int i(0L); + + //add the digits + for (; i < nShorter; i++) + { + subSum = longer[i] + shorter[i] + subCarry; + subCarry = subSum / 10; + result[i] = subSum % 10; + } + + for (; i < nLonger; i++) + { + subSum = longer[i] + subCarry; + subCarry = subSum / 10; + result[i] = subSum % 10; + } + + if (doFill) + std::fill_n(result + i, nResult - i, 0); + + if (subCarry) + { + result[i++] = 1; + return true; + } + return false; +} + +/* Shifts the digits n places left. */ +BigInt &BigInt::shiftLeft(unsigned long int n) +{ + //if the number is 0, we won't shift it + if (EqualsZero()) + return *this; + if (length <= digitCount + n + 2) + expandTo(digitCount + n + 2); + + std::copy_backward(digits, digits + digitCount, digits + n + digitCount); + std::fill_n(digits, n, 0); + digitCount += n; + return *this; +} + +/* Shifts the digits n places right. */ +BigInt &BigInt::shiftRight(unsigned long int n) +{ + if (n >= digitCount) + throw "Error BIGINT00: Overflow on shift right."; + + std::copy_backward( digits + n, digits + digitCount, + digits + digitCount - n); + digitCount -= n; + return *this; +} + +/* Expands the digits* to n. */ +void BigInt::expandTo(unsigned long int n) +{ + unsigned long int oldLength(length); + length = n; + unsigned char *oldDigits(digits); + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete[] digits; + digits = oldDigits; + length = oldLength; + throw "Error BIGINT01: BigInt creation error (out of memory?)."; + } + + std::copy(oldDigits, oldDigits + digitCount, digits); + delete[] oldDigits; +} + +BigInt::BigInt() : digits(0), length(10), digitCount(1), positive(true) +{ + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete[] digits; + throw "Error BIGINT02: BigInt creation error (out of memory?)."; + } + + //initialize to 0 + digits[0] = 0; +} + +BigInt::BigInt(const char * charNum) : digits(0) +{ + digitCount = (unsigned long int) strlen(charNum); + + if (digitCount == 0L) + throw "Error BIGINT03: Input string empty."; + else + { + switch (charNum[0]) + { + case '+': + digitCount--; + charNum++; + positive = true; + break; + case '-': + digitCount--; + charNum++; + positive = false; + break; + default: + positive = true; + } + } + + //get rid of the leading zeroes + while (charNum[0] == '0') + { + charNum++; + digitCount --; + } + + //check if the string contains only decimal digits + if (! BigInt::allCharsAreDigits(charNum, digitCount)) + throw "Error BIGINT04: Input string contains characters" + " other than digits."; + + //the input string was like ('+' or '-')"00...00\0" + if (charNum[0] == '\0') + { + digitCount = 1; + charNum--; + positive = true; + } + + length = (unsigned long int)(digitCount * BigInt::FACTOR + 1); + + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete[] digits; + throw "Error BIGINT05: BigInt creation error (out of memory?)."; + } + + //copy the digits backwards to the new BigInt + std::reverse_copy(charNum, charNum + digitCount, digits); + //convert them to unsigned char + BigInt::char2uchar(digits, digitCount); +} + +BigInt::BigInt(unsigned long int intNum) : digits(0) +{ + positive = true; + + //we don't know how many digits there are in intNum since + //sizeof(long int) is platform dependent (2^128 ~ 39 digits), so we'll + //first save them in a temporary unsigned char[], and later copy them + unsigned char tempDigits[40] = {0}; + + digitCount = int2uchar(intNum, tempDigits); + length = (unsigned long int)(digitCount * BigInt::FACTOR + 1); + + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete [] digits; + throw "Error BIGINT06: BigInt creation error (out of memory?)."; + } + + std::copy(tempDigits, tempDigits + digitCount, digits); +} + +BigInt::BigInt(const std::string &str) : digits(0), length(10), + digitCount(1), positive(true) +{ + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete[] digits; + throw "Error BIGINT07: BigInt creation error (out of memory?)."; + } + + //initialize to 0 + digits[0] = 0; + BigInt a(str.c_str()); + *this = a; +} + +BigInt::BigInt(const BigInt &rightNumber) : length(rightNumber.length), +digitCount(rightNumber.digitCount), positive(rightNumber.positive) +{ + //make sure we have just enough space + if (length <= digitCount + 2 || length > (digitCount << 2)) + length = (unsigned long int) (digitCount * BigInt::FACTOR + 1); + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete[] digits; + throw "Error BIGINT08: BigInt creation error (out of memory?)."; + } + + std::copy(rightNumber.digits, rightNumber.digits + digitCount, digits); +} + +BigInt::operator std::string() const +{ + return ToString(); +} + +BigInt &BigInt::operator =(const BigInt &rightNumber) +{ + //if the right-hand operand is longer than the left-hand one or + //twice as small + if (length < rightNumber.digitCount + 2 || + length > (rightNumber.digitCount << 2)) + { + length = (unsigned long int) + (rightNumber.digitCount * BigInt::FACTOR + 1); + //keep a pointer to the current digits, in case + //there is not enough memory to allocate for the new digits + unsigned char *tempDigits(digits); + + try + { + digits = new unsigned char[length]; + } + catch (...) + { + //clean up the mess + delete[] digits; + //restore the digits + digits = tempDigits; + throw "Error BIGINT09: BigInt assignment error (out of memory?)."; + } + //it turns out we don't need this any more + delete[] tempDigits; + } + //destructive self-assignment protection + else if (this == &rightNumber) + return *this; + + //copy the values + digitCount = rightNumber.digitCount; + positive = rightNumber.positive; + std::copy(rightNumber.digits, rightNumber.digits + digitCount, digits); + return *this; +} + +std::ostream &operator <<(std::ostream &cout, const BigInt &number) +{ + if (!number.positive) + cout << '-'; + for (int i = number.digitCount - 1; i >= 0; i--) + cout << (int(number.digits[i])); + + return cout; +} + +std::istream &operator >>(std::istream &cin, BigInt &number) +{ + std::string newNumber; + std::cin >> std::ws >> newNumber; + if (!cin) + { + cin.clear(); + throw "Error BIGINT16: Input stream error."; + } + + number = newNumber; + return cin; +} + +bool operator <(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive) == 2) + return true; + return false; +} + +bool operator <=(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive) == 1) + return false; + return true; +} + +bool operator >(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive) == 1) + return true; + return false; +} + +bool operator >=(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive) == 2) + return false; + return true; +} + +bool operator ==(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive)) + return false; + return true; +} + +bool operator !=(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive)) + return true; + return false; +} + +BigInt operator +(const BigInt &a, const BigInt &b) +{ + if (a.positive && !b.positive) + return a - (-b); + else if (!a.positive && b.positive) + return b - (-a); + + //find the longer of the operands + const BigInt *shorter, *longer; + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount) == 1) + { + shorter = &b; + longer = &a; + } + else + { + shorter = &a; + longer = &b; + } + + //Copies the "positive" field too. That is good because now either a and b + //are both positive or both negative, so the result has the same sign. + BigInt sum(*longer); + + bool overflow = BigInt::add(shorter->digits, shorter->digitCount, + longer->digits, longer->digitCount, + sum.digits, 0, false); + if (overflow) + sum.digitCount++; + + return sum; +} + +/*overloaded ++ operator, prefix version*/ +BigInt &BigInt::operator++() +{ + return *this += BigIntOne; +} + +/*overloaded ++ operator, postfix version*/ +BigInt BigInt::operator++(int) +{ + BigInt temp(*this); + *this += BigIntOne; + return temp; +} + +BigInt &BigInt::operator+=(const BigInt &number) +{ + *this = *this + number; + return *this; +} + +BigInt BigInt::operator-() const +{ + if (!this->EqualsZero()) + { + BigInt temp(*this); + temp.positive = !temp.positive; + return temp; + } + return *this; +} + +BigInt operator-(const BigInt &a, const BigInt &b) +{ + if (!a.positive && b.positive) + { + return -((-a) + b); + } + if (a.positive && !b.positive) + { + return a + (-b); + } + + const int cmpAbs = BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount); + //if a == b + if ((cmpAbs == 0) && (a.positive == b.positive)) + { + return BigIntZero; + } + + //find the longer of the operands (bigger by absolute value) + const BigInt *shorter, *longer; + bool sign(a.positive); //the sign of the result + if (cmpAbs != 2) // a >= b + { + shorter = &b; + longer = &a; + } + else + { + shorter = &a; + longer = &b; + sign = !sign; + } + + BigInt result(*longer); + result.positive = sign; + //temporary variable + const BigInt shorterCopy(*shorter); + //often used temporary variable + const int rDigits(shorterCopy.digitCount); + //in case of longer digitwise carry, overflow = true + bool overflow(false); + + for (int i(0); i < rDigits; i++) + { + overflow = (longer->digits[i] - shorterCopy.digits[i]) < 0; + if (overflow) + { + result.digits[i] = longer->digits[i] + 10 - shorterCopy.digits[i]; + //transfer carry + shorterCopy.digits[i+1]++; + } + else + //make the digitwise subtraction + result.digits[i] = longer->digits[i] - shorterCopy.digits[i]; + } + + //if there is a carry and the following digit is 0 => there will + //be a carry again... + if (overflow && result.digits[rDigits] == 0) + { + result.digits[rDigits] = 9; + + int i(rDigits + 1); + for (; result.digits[i] == 0; i++) + result.digits[i] = 9; + + result.digits[i] -= 1; + } //there is a carry but there will be no more carries + else if (overflow) + result.digits[rDigits]--; + + //get rid of the leading zeroes + for (int i(result.digitCount - 1); i > 0; i--) + if (result.digits[i] == 0) + result.digitCount--; + else + break; + + return result; +} + +/*overloaded -- operator, prefix version*/ +BigInt &BigInt::operator--() +{ + *this = *this - BigIntOne; + return *this; +} + +/*overloaded -- operator, postfix version*/ +BigInt BigInt::operator--(int) +{ + BigInt temp(*this); + *this = *this - BigIntOne; + return temp; +} + +BigInt &BigInt::operator-=(const BigInt &number) +{ + *this = *this - number; + return *this; +} + +BigInt operator*(const BigInt &a, const BigInt &b) +{ + if (a.EqualsZero() || b.EqualsZero()) + return BigIntZero; + + //this controls wether Karatsuba algorithm will be used for multiplication +#ifdef KARATSUBA + int n((a.digitCount < b.digitCount ? b.digitCount : a.digitCount)); + + //we will use a temporary buffer for multiplication + unsigned char *buffer(0); + + try + { + buffer = new unsigned char[11 * n]; + } + catch (...) + { + delete[] buffer; + throw "Error BIGINT10: Not enough memory?"; + } + + unsigned char *bb(buffer + n), *bc(bb + n); + + std::copy(a.digits, a.digits + a.digitCount, buffer); + std::fill(buffer + a.digitCount, buffer + n, 0); + std::copy(b.digits, b.digits + b.digitCount, bb); + std::fill(bb + b.digitCount, bb + n, 0); + + BigInt::karatsubaMultiply(buffer, bb, n, bc); + + n <<= 1; +#else + int n = a.digitCount + b.digitCount; + + unsigned char *buffer = new unsigned char[n]; + + BigInt::longMultiply( a.digits, a.digitCount, + b.digits, b.digitCount, buffer); + + unsigned char *bc(buffer); +#endif /*KARATSUBA*/ + + BigInt bigIntResult; //we assume it's a positive number + if (a.positive != b.positive) + bigIntResult.positive = false; + bigIntResult.expandTo(n + 10); + std::copy(bc, bc + n, bigIntResult.digits); + for (unsigned long int i = n - 1; i > 0L; i--) + { + if (bigIntResult.digits[i]) + { + bigIntResult.digitCount = i + 1; + break; + } + } + delete[] buffer; + + return bigIntResult; +} + +BigInt &BigInt::operator*=(const BigInt &number) +{ + *this = *this * number; + return *this; +} + +BigInt operator /(const BigInt &a, const BigInt &b) +{ + if (b.EqualsZero()) + throw "Error BIGINT11: Attempt to divide by zero."; + + //we don't want to call this function twice + int comparison(BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount)); + + //if a == 0 or |a| < |b| + if (a.EqualsZero() || comparison == 2) + return BigIntZero; + + //if a == b + if (comparison == 0) + { + if (a.positive == b.positive) + return BigIntOne; + else + return -BigIntOne; + } + + BigInt quotient, remainder; + BigInt::divide(a, b, quotient, remainder); + //adjust the sign (positive by default) + if (a.positive != b.positive) + quotient.positive = false; + return quotient; +} + +BigInt &BigInt::operator /=(const BigInt &number) +{ + *this = *this / number; + return *this; +} + +BigInt operator%(const BigInt &a, const BigInt &b) +{ + if (b.EqualsZero()) + throw "Error BIGINT12: Attempt to divide by zero."; + + //we don't want to call this function twice + int comparison(BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount)); + + //a == b + if (comparison == 0) + return BigIntZero; + + //if a < b + if (comparison == 2 && a.positive) + return a; + + BigInt quotient, remainder; + BigInt::divide(a, b, quotient, remainder); + if (!a.positive && !remainder.EqualsZero()) + remainder.positive = false; + return remainder; +} + +BigInt &BigInt::operator%=(const BigInt &number) +{ + *this = *this % number; + return *this; +} + +/* Returns *this to the power of n + * using the fast Square and Multiply algorithm. */ +BigInt BigInt::GetPower(unsigned long int n) const +{ + BigInt result(BigIntOne); + BigInt base(*this); + + while (n) + { + //if n is odd + if (n & 1) + { + result = result * base; + n--; + } + n /= 2; + base = base * base; + } + + //number was negative and the exponent is odd, the result is negative + if (!positive && (n & 1)) + result.positive = false; + return result; +} + +/* *this = *this to the power of n. */ +void BigInt::SetPower(unsigned long int n) +{ + *this = (*this).GetPower(n); +} + +/* Returns *this to the power of n + * using the fast Square and Multiply algorithm. */ +BigInt BigInt::GetPower(BigInt n) const +{ + if (!n.positive) + throw "Error BIGINT13: Negative exponents not supported!"; + + BigInt result(BigIntOne); + BigInt base(*this); + BigInt bigIntTwo(BigIntOne + BigIntOne); + + while (!n.EqualsZero()) + { + //if n is odd + if (n.digits[0] & 1) + { + result = result * base; + n--; + } + n = n / bigIntTwo; + base = base * base; + } + + //number was negative and the exponent is odd, the result is negative + if (!positive && (n.digits[0] & 1)) + result.positive = false; + return result; +} + +/* *this = *this to the power of n. */ +void BigInt::SetPower(BigInt n) +{ + *this = (*this).GetPower(n); +} + +/* Returns (*this to the power of b) mod n. */ +BigInt BigInt::GetPowerMod(const BigInt &b, const BigInt &n) const +{ + BigInt a(*this); + a.SetPowerMod(b, n); + return a; +} + +/* *this = (*this to the power of b) mod n. */ +void BigInt::SetPowerMod(const BigInt &b, const BigInt &n) +{ + if (!b.positive) + throw "Error BIGINT14: Negative exponent not supported."; + //we will need this value later, since *this is going to change + const BigInt a(*this); + //temporary variables + BigInt bCopy(b), q, r; + const BigInt two(BigIntOne + BigIntOne); + + //first we will find the binary representation of b + std::vector bits; + while (!bCopy.EqualsZero()) + { + BigInt::divide(bCopy, two, q, r); + bCopy = q; + if (r.EqualsZero()) + bits.push_back(false); + else + bits.push_back(true); + } + + //do the exponentiating + *this = BigIntOne; + for (int i = (int) bits.size() - 1; i >= 0; i--) + { + BigInt::divide(*this * *this, n, q, *this); + if (bits[i]) + BigInt::divide(*this * a, n, q, *this); + } +} + +/* Returns the nth digit read-only, zero-based, right-to-left. */ +unsigned char BigInt::GetDigit(unsigned long int index) const +{ + if (index >= digitCount) + throw "Error BIGINT15: Index out of range."; + + return digits[index]; +} + +/* Returns the nth digit, zero-based, right-to-left. */ +void BigInt::SetDigit(unsigned long int index, unsigned char value) +{ + if (index >= digitCount) + throw "Error BIGINT15: Index out of range."; + if (value > 9) + throw "Error BIGINT16: Digit value out of range."; + + digits[index] = value; +} + +/* Returns the value of BigInt as std::string. */ +std::string BigInt::ToString(bool forceSign) const +{ + (void)forceSign; // avoid unused warning + std::string number; + if (!positive) + number.push_back('-'); + for (int i = digitCount - 1; i >= 0; i--) + number.push_back(char(digits[i]) + '0'); + + return number; +} + +/* Returns the absolute value. */ +BigInt BigInt::Abs() const +{ + return ((positive) ? *this : -(*this)); +} -- cgit v1.2.3