// BigInt.cpp: implementation of the BigInt class.
//
//////////////////////////////////////////////////////////////////////


#include "stdafx.h"
#include "Rsa.h"
#include "BigInt.h"
#include <stdlib.h>
#include <ctype.h>
#include <time.h>
#include "RsaDlg.h"

const int BASE = 10;

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif


// Oi arithmoi BigInts ylopoiountai xrisimopoiontas ena Vector<char> 
// gia na tin apothikevsi ton psifion tou BigInt.
// Diladi enas arithmos opos o 5,879 apothikevetai 
// os to vector {9,7,8,5}
// Ara, to ligotero simantiko psifio einai to proto psifio sto vector
// p.x i synartisi GetDigit(0) epistrefei 9 and i getDigit(3) epistrefei 5.
// Oles oi prakseis sta psifia ginontai xrisimopoiontas tis parakato idiotikes
// boithitikes synartiseis:
//
// int  GetDigit(k)        -- epistrefei k-osto psifio
// void ChangeDigit(k,val) -- vazei sto k-osto psifio tin timi val
// void AddSigDigit(val)   -- prosthetei neo pio simantiko psifio val
//
// 
// 
// Oi eksodos enos BigInt diefkolynetai apo tin synartisi ToString() 
// i opoia metatrepei enan BigInt se anaparastasi string (ASCII) */

BigInt::BigInt()
// postcondition: bigint initialized to 0
   : mySign(positive),
     myDigits(1,'0'),
     myNumDigits(1)
{
   // all fields initialized in initializer list
}


BigInt::BigInt(int num)
// postcondition: bigint initialized to num
   : mySign(positive),
     myDigits(1,'0'),
     myNumDigits(0)
{ 
    // check if num is negative, change state and num accordingly
    
    if (num < 0)
    {
        mySign = negative;
        num = -1 * num;
    }

    // handle least-significant digit of num (handles num == 0)
    
    AddSigDigit(num % BASE);
    num = num / BASE;
    
    // handle remaining digits of num
    
    while (num != 0)
    {
        AddSigDigit(num % BASE);
        num = num / BASE;
    }
}



BigInt::BigInt(const string & s)
// precondition: s consists of digits only, optionally preceded by + or - 
// postcondition: bigint initialized to integer represented by s
//                if s is not a well-formed BigInt (e.g., contains non-digit
//                characters) then an error message is printed and abort called
  : mySign(positive),
    myDigits(s.length(),'0'),
    myNumDigits(0)
{
    int k;
    int limit = 0;
   
    if (s.length() == 0)
    {
        myDigits.resize(1);
        AddSigDigit(0);
        return;
    }
    if (s[0] == '-')
    {
        mySign = negative;
        limit = 1;
    }
    if (s[0] == '+')
    {
        limit = 1;
    }
    // start at least significant digit
    
    for(k=s.length() - 1; k >= limit; k--)
    {
        if (! isdigit(s[k]))
        {
            cerr << "badly formed BigInt value = " << s << endl;
            abort();
        }
        AddSigDigit(s[k]-'0');
    }
    Normalize();
}

BigInt& BigInt::operator=(const string& s)
{
    int k;
    int limit = 0;

   //arxikopoiisi timon
   mySign = positive;
   myNumDigits = 0;
   myDigits.clear();
   for (k=0;k<s.length();k++)
      myDigits.push_back('0'); 


    if (s.length() == 0)
    {
        myDigits.resize(1);
        AddSigDigit(0);
        return *this;
    }
    if (s[0] == '-')
    {
        mySign = negative;
        limit = 1;
    }
    if (s[0] == '+')
    {
        limit = 1;
    }
    // start at least significant digit
    
    for(k=s.length() - 1; k >= limit; k--)
    {
        if (! isdigit(s[k]))
        {
            cerr << "badly formed BigInt value = " << s << endl;
            abort();
        }
        AddSigDigit(s[k]-'0');
    }
    Normalize();

   return *this;
}


bool BigInt::equals ( const BigInt & other )  const
{
   if (mySign != other.mySign) return false;

   if (myNumDigits != other.myNumDigits) return false;

   int len = myNumDigits;
   for (int k=0; k < len; k++)
      if (GetDigit(k) != other.GetDigit(k)) return false;

   return true;
}

bool operator==(const BigInt & lhs, const BigInt & rhs)
{
   return lhs.equals(rhs);
}

bool BigInt::lessThan( const BigInt & other)  const
{
   if (mySign != other.mySign)
      return IsNegative();

   // signs are the same

   if (myNumDigits < other.myNumDigits)
      if (IsNegative()) return false;   // both negative
      else return true;

   if (myNumDigits > other.myNumDigits)
      if (IsNegative()) return true;      // both positive
      else return false;

   // signs and number of digits are the same
   
   int len = myNumDigits;
   if (IsPositive()) {
      for (int k = len-1; k>=0; k--)
         if (GetDigit(k) < other.GetDigit(k))
            return true;
         else if (GetDigit(k) > other.GetDigit(k))
            return false;
      return false;
   }

   if (IsNegative()) {
      for (int k = len-1; k>=0; k--) 
         if (GetDigit(k) < other.GetDigit(k))
            return false;
         else if (GetDigit(k) > other.GetDigit(k))
            return true;
      
      return false;
   }

   return false;
}

bool operator<(const BigInt & lhs, const BigInt & rhs)
{
   return lhs.lessThan(rhs);
}
const BigInt & BigInt::operator -=(const BigInt & rhs)
// postcondition: returns value of bigint - rhs after subtraction
{
    int diff;
    int borrow = 0;
    int k;
    int len = NumDigits();
   
    if (this == &rhs)         // subtracting self?
    {
        *this = (int) 0;
        return *this;
    }

    if (rhs == 0){
      return *this;
    }

    // signs opposite? then lhs - (-rhs) = lhs + rhs
    
    if (IsNegative() != rhs.IsNegative())
    {
        *this +=(-1 * rhs);
        return *this;
    }
    // signs are the same, check which number is larger
    // and switch to get larger number "on top" if necessary
    // since sign can change when subtracting
    // examples: 7 - 3 no sign change,     3 - 7 sign changes
    //          -7 - (-3) no sign change, -3 -(-7) sign changes
    if (IsPositive() && (*this) < rhs ||
        IsNegative() && (*this) > rhs)
    {
        *this = rhs - *this;
      if (IsPositive()) mySign = negative;
      else              mySign = positive;   // toggle sign 
        return *this;
    }
    // same sign and larger number on top
    
    for(k=0; k < len; k++)
    {
        diff = GetDigit(k) - rhs.GetDigit(k) - borrow;
        borrow = 0;
        if (diff < 0)
        {
            diff += 10;
            borrow = 1;
        }
        ChangeDigit(k,diff);
    }
    Normalize();
    return *this;
}

const BigInt & BigInt::operator +=(const BigInt & rhs)
// postcondition: returns value of bigint + rhs after addition
{

    int sum;
    int carry = 0;

    int k;
    int len = NumDigits();         // length of larger addend

    if (this == &rhs)              // to add self, multiply by 2
    {
       *this *= 2;
       return *this;
    }
    
    if (rhs == 0){
      return *this;
    }

    if (IsPositive() != rhs.IsPositive())    // signs not the same, subtract
    {
        *this -= (-1 * rhs);
        return *this;
    }

    // process both numbers until one is exhausted

    if (len < rhs.NumDigits())
    {
        len = rhs.NumDigits();
    }
    for(k=0; k < len; k++)
    {
        sum = GetDigit(k) + rhs.GetDigit(k) + carry;
        carry = sum / BASE;
        sum = sum % BASE;

        if (k < myNumDigits)
        {
            ChangeDigit(k,sum);
        }
        else
        {
            AddSigDigit(sum);
        }
    }
    if (carry != 0)
    {
        AddSigDigit(carry);
    }
    return *this;    
}

BigInt operator +(const BigInt & lhs, const BigInt & rhs)
// postcondition: returns a bigint whose value is lhs + rhs
{
    BigInt result(lhs);
    result += rhs;   
    return result;
}

BigInt operator -(const BigInt & lhs, const BigInt & rhs)
// postcondition: returns a bigint whose value is lhs + rhs
{
    BigInt result(lhs);
    result -= rhs;
    return result;
}

void BigInt::Print(ostream & os) const
// postcondition: BigInt inserted onto stream os
{
    os << ToString();
}

string BigInt::ToString() const
// postcondition: returns string equivalent of BigInt
{
    int k;
    int len = NumDigits();    
    string s = "";

    if (IsNegative())
    {
        s = '-';
    }
    for(k=len-1; k >= 0; k--)
    {
        s += char('0'+GetDigit(k));
    }
    return s;
}

int BigInt::ToInt() const
// precondition: INT_MIN <= self <= INT_MAX
// postcondition: returns int equivalent of self
{
    int result = 0;
    int k;
    if (INT_MAX < *this) return INT_MAX;
    if (*this < INT_MIN) return INT_MIN;
    
    for(k=NumDigits()-1; k >= 0; k--)
    {
        result = result * 10 + GetDigit(k);
    }
    if (IsNegative())
    {
        result *= -1;
    }
    return result;
}

double BigInt::ToDouble() const
// precondition: DBL_MIN <= self <= DLB_MAX
// postcondition: returns double equivalent of self
{
    double result = 0.0;
    int k;
    for(k=NumDigits()-1; k >= 0; k--)
    {
        result = result * 10 + GetDigit(k);
    }
    if (IsNegative())
    {
        result *= -1;
    }
    return result;
}

ostream & operator <<(ostream & out, const BigInt & big)
// postcondition: big inserted onto stream out
{
    big.Print(out);
    return out;
}

istream & operator >> (istream & in, BigInt & big)
// postcondition: big extracted from in, must be whitespace delimited     
{
    string s;
    in >> s;
    big = BigInt(s);
    return in;
}
void BigInt::Normalize()
// postcondition: all leading zeros removed     
{
    int k;
    int len = NumDigits();
    for(k=len-1; k >= 0; k--)        // find a non-zero digit
    {
        if (GetDigit(k) != 0) break;
        myNumDigits--;               // "chop" off zeros
    }
    if (k < 0)    // all zeros
    {
        myNumDigits = 1;
        mySign = positive;
    }
}


const BigInt & BigInt::operator *=(int num)
// postcondition: returns num * value of BigInt after multiplication
{
    int carry = 0;
    int product;               // product of num and one digit + carry
    int k;
    int len = NumDigits();
    
    if (0 == num)              // treat zero as special case and stop
    {
        *this = (int) 0;
        return *this;
    }

   if (BASE < num|| num < 0)        // handle pre-condition failure
    {
        *this *= BigInt(num);
        return *this;
    }

    if (1 == num)              // treat one as special case, no work
    {
        return *this;
    }

    for(k=0; k < len; k++)     // once for each digit
    {
        product = num * GetDigit(k) + carry;
        carry = product/BASE;
        ChangeDigit(k,product % BASE);
    }
    
    while (carry != 0)         // carry all digits
    {
        AddSigDigit(carry % BASE);
        carry /= BASE;
    }
    return *this;
}


BigInt operator *(const BigInt & a, int num)
// postcondition: returns a * num     
{
    BigInt result(a);
    result *= num;
    return result;
}

BigInt operator *(int num, const BigInt & a)
// postcondition: returns num * a     
{
    BigInt result(a);
    result *= num;
    return result;
}


const BigInt & BigInt::operator *=(const BigInt & rhs)
// postcondition: returns value of bigint * rhs after multiplication
{
    // uses standard "grade school method" for multiplying
    
   if (IsNegative() != rhs.IsNegative())
   {
       mySign = negative;
   }
   else
   {
      mySign = positive;
   }

    BigInt self(*this);                        // copy of self
    BigInt sum(0);                             // to accumulate sum
    int k;
    int len = rhs.NumDigits();                 // # digits in multiplier
    
    for(k=0; k < len; k++)
    {
       sum += self * rhs.GetDigit(k);          // k-th digit * self
       self *= 10;                             // add a zero
    }
    *this = sum;
    return *this;
}

BigInt operator *(const BigInt & lhs, const BigInt & rhs)
// postcondition: returns a bigint whose value is lhs * rhs
{
    BigInt result(lhs);
    result *= rhs;
    return result;
}

int BigInt::NumDigits() const
// postcondition: returns # digits in BigInt
{
    return myNumDigits;
}

int BigInt::GetDigit(int k) const
// precondition: 0 <= k < NumDigits()
// postcondition: returns k-th digit 
//                (0 if precondition is false)
//                Note: 0th digit is least significant digit
{
    if (0 <= k && k < NumDigits())
    {
        return myDigits[k] - '0';
    }
    return 0;
}

void BigInt::ChangeDigit(int k, int value)
// precondition: 0 <= k < NumDigits()
// postcondition: k-th digit changed to value
//                Note: 0th digit is least significant digit
{
    if (0 <= k && k < NumDigits())
    {
        myDigits[k] = char('0' + value);
    }
    else
    {
        cerr << "error changeDigit " << k << " " << myNumDigits << endl;
    }
}

void BigInt::AddSigDigit(int value)
// postcondition: value added to BigInt as most significant digit
//                Note: 0th digit is least significant digit     
{
    if (myNumDigits >= myDigits.size())
    {
        myDigits.resize(myDigits.size() * 2);
    }
    myDigits[myNumDigits] = char('0' + value);
    myNumDigits++;
}

bool BigInt::IsNegative() const
// postcondition: returns true iff BigInt is negative
{
    return mySign == negative;
}

bool BigInt::IsPositive() const
// postcondition: returns true iff BigInt is positive
{
   return mySign == positive;
}

bool operator<=(const BigInt & lhs, const BigInt & rhs)
{
   return (lhs == rhs || lhs < rhs);
}

bool operator>(const BigInt & lhs, const BigInt & rhs)
{
   return !(lhs <= rhs);
}

bool operator>=(const BigInt & lhs, const BigInt & rhs)
{
   return !(lhs < rhs);
}

bool operator!=(const BigInt & lhs, const BigInt &rhs)
{
   return !(lhs == rhs);
}


void BigInt::ShiftRight(int k)
// postcondition:  self has been shifted to the right k decimal
//                 places
{
  int s, t = 0;

  if(k >= NumDigits()){
    *this = (int) 0;
  }
  else if (k > 0){
    for(s = k; s < NumDigits(); s++){
      ChangeDigit(t, GetDigit(s));
      t++;
    }
    for(s = NumDigits() - k; s < NumDigits(); s++){
      ChangeDigit(s,0);
    }
    Normalize();
  }
}

void BigInt::ShiftLeft(int k)
{
  int cnt, numD;
  if(k > 0){
    numD = NumDigits();
    for(cnt = 0; cnt < k; cnt++)
      AddSigDigit(0);
    for(cnt = 0; cnt < numD; cnt++)
      ChangeDigit(numD+k-1-cnt, GetDigit(numD-1-cnt));
    while(numD+k-1-cnt >= 0){
      ChangeDigit(numD+k-1-cnt, 0);
      cnt++;
    }
  }
}
   
void BigInt::Div2()
{
  int current;
  int k;
  int carryDown = 0;

  for(k = NumDigits()-1; k >=0; k--){
    current = GetDigit(k);
    ChangeDigit(k, (current/2) + carryDown);
    carryDown = (current%2) * 5;
  }
  Normalize();
}


void BigInt::Divide(const BigInt & rhs,
                    BigInt & quotient, BigInt & remainder)
{
  BigInt divisor(rhs);               // avoid alias problems
  int subCount;
  int shiftAmt;
  quotient = (int) 0;
  remainder = *this;                 // avoid alias problems
  remainder.mySign = positive;
  divisor.mySign = positive;

  if(divisor == 0){
    cerr << "Division by Zero in BigInt::Divide!" << endl;
    abort();
  }

  if (remainder < divisor){          // integer division yields 0
    quotient = (int) 0;  
    remainder.mySign = mySign;
  }
  else if (remainder == divisor){    // special case
    quotient = 1;
    remainder = (int) 0;
    if(mySign != rhs.mySign)
      quotient.mySign = negative;
  }
  else if(divisor == 2){
    quotient = remainder;
    remainder = BigInt(remainder.GetDigit(0) % 2);
    quotient.Div2();
  }
  else{
    shiftAmt = remainder.NumDigits() - divisor.NumDigits();
    divisor.ShiftLeft(shiftAmt);
    if(divisor > remainder){
      divisor.ShiftRight(1);
      shiftAmt--;
    }
    while(shiftAmt >= 0){
      subCount = 0;
      while(divisor <= remainder){
        subCount++;
        remainder -= divisor;
      }
      quotient.ShiftLeft(1);
      quotient += subCount;
      divisor.ShiftRight(1);
      shiftAmt--;
    }
    if(mySign != rhs.mySign)
      quotient.mySign = negative;
    remainder.mySign = mySign;
    quotient.Normalize();
    remainder.Normalize();
  }
}

const BigInt & BigInt::operator /= (const BigInt & rhs)
{
  BigInt q;
  BigInt r;
  Divide(rhs, q, r);
  *this = q;
  return *this;
}

const BigInt & BigInt::operator %= (const BigInt & rhs)
{
  BigInt q;
  BigInt r;
  Divide(rhs, q, r);
  *this = r;
  return *this;
}

const BigInt & BigInt::operator ++ ()
{
   return *this += 1;
}
const BigInt & BigInt::operator -- ()
{
   return *this -= 1;
}

const BigInt & BigInt::operator ++ ( int )
{
   return *this += 1;
}
const BigInt & BigInt::operator -- ( int )
{
   return *this -= 1;
}

BigInt operator /(const BigInt & lhs, const BigInt & rhs)
{
  BigInt result(lhs);
  result /= rhs;
  return result;
}

BigInt operator %(const BigInt & lhs, const BigInt & rhs)
{
  BigInt result(lhs);
  result %= rhs;
  return result;
}

int BigInt::DigitsNum()
{
	//Epistrefei ton arithmo ton psifion sto vector(myNumDigits einai private)
   return myNumDigits;
}


int random_range(int lowest_number, int highest_number)
{
	//Epistrefei enan tyxaio arithmo esto  lowset_number <= x <= highest_number
    if(lowest_number > highest_number){
        swap(lowest_number, highest_number);
    }
    int range = highest_number - lowest_number + 1;
    return lowest_number + int(range * rand()/(RAND_MAX + 1.0));
}

BigInt fastexponent(BigInt a, BigInt b, BigInt n)
{
   //Ypologizei parastaseis toy typou (a^b mod n)
   BigInt ans =1;
   BigInt powofa = a;   // powOfa == a^1.  Pairnei times toy typoy
                        // a^2, a^4, a^8 kata tin ektelesi
 
    while (b != 0) 
    {
         while ((b % 2) == 0) 
       {
          
              b /= 2;
              powofa = (powofa*powofa) % n;
       }
         b = b -1;
         ans = ans*powofa % n;
    }

    return ans;
}

BigInt GCD(const BigInt x,const BigInt y)
{
// Briskei ton megisto koino diaireti ton arithmon x,y kai 
// epistrefei to apotelesma sto g
// Akoloutheitai i methodos tou Vivliou Algorithmon.

	if (x >= y)
	{
		if (y == 0)
			return x;
		else
			return GCD(y,x % y);
	}
	else
		return GCD(y,x);
}



BigInt exteuclid(BigInt a, BigInt b, BigInt &x,  BigInt &y) 
{
//  Ylopoiisi tou Extended Euclidean Algorithm. 

    if(b == 0)
        if(a < 0) 
      {
            x = -1;
            y = (int) 0;
            return (-1*a);
        } else 
      {
            x = 1;
            y = (int) 0;
            return a;
        }
    BigInt xprime, d = exteuclid(b, a % b, xprime, x);
    y = xprime - (a / b) * x;
    return d;
}

BigInt mod(BigInt x,BigInt y)
{
	//Ylopoiei to mod kai gia arnitikous x. Ypotheto oti einai sosto(den eimai sigouros)
	// gi'afto den to exo ensomatosei stin klasi BigInt
    if (y == 0) return x;
    if (x<0) x=y+x;
    return (x % y);
}

BigInt selecte(BigInt f,int emax)
{
//Dialegei enan tyxaio arithmo metaksi esto    3 <= x <= emax
// o opoios x tha prepei na protos pros ton f.
	BigInt result,randomnum;
    bool found=false;
    
    while (!found)
    {
       randomnum=random_range(3,emax);
       result = GCD(f,randomnum);
       if (result==1)  //GCD(e,f)=1
          break;
    }
    return randomnum;
}

BigInt selectd(BigInt e,BigInt f)
{
//Ypologizei ton d etsi oste e*d=1 mod f xrisimopoiontas
//ton Ektetameno Efkleidio Algorithmo
	BigInt x,y,result;
	result = exteuclid(e,f,y,x);
	return (result==1)*mod(y,f);
}


//Gia xrisi CLI mono (an xreiastei paradeigma), yparxei i main ()

/*void main(){
   BigInt a, b;
   BigInt d,e,f,n;
   BigInt crypted;
   BigInt decrypted;

   a = findprime(0);
   cout << "\nPRIME 1:" << a << "  ( " << a.DigitsNum() << " digits ) " ;
   b = findprime(a);
   cout << "\nPRIME 2:" << b << "  ( " << b.DigitsNum() << " digits ) \n" ;

   n = a*b;
   f = (a-1)*(b-1);
   
   cout << "\nn = a*b        = " << n << "  ( " << n.DigitsNum() << " digits ) " ;
   cout << "\nf = (a-1)(b-1) = " << f << "  ( " << f.DigitsNum() << " digits ) \n\n" ;

   e = selecte(f,1000);
   d = selectd(e,f);
   cout << "e : " << e << "  ( " << e.DigitsNum() << " digits ) \n" ;
   cout << "d : " << d << "  ( " << d.DigitsNum() << " digits ) \n" ;
   
   BigInt M;
   M = "1234567890123456789012345678901234567";
   cout << "\nM :         " << M << "  ( " << M.DigitsNum() << " digits )" ;
   crypted = fastexponent(M,e,n);
   cout << "\nEncrypted : " << crypted << "  ( " << crypted.DigitsNum() << " digits )" ;
   cout << "\nOriginal  : " << fastexponent(crypted,d,n) <<endl;

}*/