// Rascal, the Advanced Scientific CALculator
// Copyright (C) 2001, Sebastian Ritterbusch (Rascal@Ritterbusch.de)
//
// This program 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 2
// of the License, or (at your option) any later version.
//
// This program 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 detauls.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//

// Long Integer Library
// (C) 1999 Jochen Suckfüll
// (C) 2001 Sebastian Ritterbusch

#include "langzahl.hpp"
#include <stdio.h>

init_rand randomstate;

#ifdef RESPECT_RASCAL_USER_STOP_VARIABLE
   #define LZ_USER_STOP_CONDITION   && !rascal_user_stop
#else
   #define LZ_USER_STOP_CONDITION
#endif

langzahl::langzahl(LONG32 i) throw()
{
   if(i==0)
   {
      dat=0;
      longs=0;
      sign=0;
      return;
   }
   if(i<0)
   {
      sign=-1;
      i=-i;
   } else 
      sign=0;

   if(i>=100000000)
      longs=2;
   else
      longs=1;
   
   dat=new LONG32[longs];

   dat[0]=i%100000000;
   if(longs==2)
      dat[1]=i/100000000;
}

langzahl::langzahl(const lsize &s) throw():longs(s.size()),sign(0)
{
   dat=new LONG32[longs];
   for(int i=0;i<longs;i++)
      dat[i]=0;
}

langzahl::langzahl(const string &s) throw()
{
   LONG32 fak,st;
   if(s[0]=='-')
      sign=-1;
   else
      sign=0;
   longs=(s.length()-1)/8+1;
   dat=new LONG32[longs];
   st=s.length()-(longs-1)*8;
   dat[longs-1]=0;

   for(int i=st-1,fak=1;(i>=-sign) LZ_USER_STOP_CONDITION;i--,fak*=10)
      dat[longs-1]+=(s[i]-'0')*fak;

   st-=sign;
   for(int i=0;(i<longs-1) LZ_USER_STOP_CONDITION;i++)
   {
      fak=1;
      dat[i]=0;
      for(int j=1;j<=8;j++,fak*=10)
         dat[i]+=(s[st+(longs-1-i)*8-j]-'0')*fak;
   }
   kuerze();
}

langzahl::langzahl(const langzahl &l) throw():longs(l.longs),sign(l.sign)
{
   dat=new LONG32[longs];
   for(int i=0;i<longs;i++)
      dat[i]=l.dat[i];
}

inline void langzahl::kuerze() throw()
{
   for(;longs&&dat[longs-1]==0;longs--);
   if(longs==0)
      sign=0;      
}

istream &operator >>(istream &is,langzahl &l) throw()
{
   string s;
   is>>s;
   l=langzahl(s);
   return is;
}

string &operator >>(string &is,langzahl &l) throw()
{
   l=langzahl(is);
   return (is="");
}

ostream &operator <<(ostream &os,const langzahl &l) throw()
{
   if(l.sign) os<<'-';
   if(l.longs) os<<l.dat[l.longs-1];
   else os<<"0";
   for(int i=l.longs-2;(i>=0) LZ_USER_STOP_CONDITION;i--)
      os<<std::setw(8)<<std::setfill('0')<<l.dat[i];
   return os;
}

string langzahl_long2string(LONG32 a)
{
   char buffer[9];
   sprintf(buffer,"%i",a);
   return string(buffer);
}

string &operator <<(string &os,const langzahl &l) throw()
{
   if(l.sign) os+='-';
   if(l.longs) os+=langzahl_long2string(l.dat[l.longs-1]);
   else os+='0';
   for(int i=l.longs-2;(i>=0) LZ_USER_STOP_CONDITION;i--)
   {
      string n(langzahl_long2string(l.dat[i]));
      for(int k=0;k<8-n.length();k++)
         os+='0';
      os+=n;
   }
   return os;
}

langzahl &langzahl::operator =(const langzahl &l2) throw()
{
   longs=l2.longs;
   sign=l2.sign;
   LONG32 * newdat=new LONG32[longs];
   for(int i=0;i<longs;i++)
      newdat[i]=l2.dat[i];
   delete [] dat;
   dat=newdat;
   return *this;
}

langzahl &langzahl::operator =(LONG32 i) throw()
{
   delete [] dat;
   if(i==0)
   {
      dat=0;
      longs=0;
      sign=0;
      return *this;
   }
   if(i<0)
   {
      sign=-1;
      i=-i;
   }

   if(i>=100000000)
      longs=2;
   else
      longs=1;
   
   dat=new LONG32[longs];

   dat[0]=i%100000000;
   if(longs==2)
      dat[1]=i/100000000;

   return *this;
}

langzahl &langzahl::operator =(const char *c) throw()
{
   *this=string(c);
   return *this;
}

bool operator ==(const langzahl &l1,const langzahl &l2) throw()
{
   if(l1.sign!=l2.sign) return false; 
   if(l1.longs!=l2.longs) return false;
   for(int i=0;i<l1.longs;i++)
      if(l1.dat[i]!=l2.dat[i]) return false;
   return true;
}

bool operator !=(const langzahl &l1,const langzahl &l2) throw()
{
   if(l1.sign!=l2.sign) return true; 
   if(l1.longs!=l2.longs) return true;
   for(int i=0;i<l1.longs;i++)
      if(l1.dat[i]!=l2.dat[i]) return true;
   return false;
}

bool operator <=(const langzahl &l1,const langzahl &l2) throw()
{
   if(l1.sign<l2.sign) return true;
   if(l1.sign>l2.sign) return false;
   if(l1.longs>l2.longs) return l1.sign==0?false:true;
   if(l1.longs<l2.longs) return l1.sign==0?true:false;
   for(int i=l1.longs-1;i>=0;i--)
   {
      if(l1.dat[i]>l2.dat[i]) return l1.sign==0?false:true;
      if(l1.dat[i]<l2.dat[i]) return l1.sign==0?true:false;
   }
   return true;
}

bool operator >=(const langzahl &l1,const langzahl &l2) throw()
{
   if(l1.sign<l2.sign) return false;
   if(l1.sign>l2.sign) return true;
   if(l1.longs<l2.longs) return l1.sign==0?false:true;
   if(l1.longs>l2.longs) return l1.sign==0?true:false;
   for(int i=l1.longs-1;i>=0;i--)
   {
      if(l1.dat[i]<l2.dat[i]) return l1.sign==0?false:true;
      if(l1.dat[i]>l2.dat[i]) return l1.sign==0?true:false;
   }
   return true;
}

bool operator <(const langzahl &l1,const langzahl &l2) throw()
{
   if(l1.sign<l2.sign) return true;
   if(l1.sign>l2.sign) return false;
   if(l1.longs>l2.longs) return l1.sign==0?false:true;
   if(l1.longs<l2.longs) return l1.sign==0?true:false;
   for(int i=l1.longs-1;i>=0;i--)
   {
      if(l1.dat[i]>l2.dat[i]) return l1.sign==0?false:true;
      if(l1.dat[i]<l2.dat[i]) return l1.sign==0?true:false;
   }
   return false;
}

bool operator >(const langzahl &l1,const langzahl &l2) throw()
{
   if(l1.sign<l2.sign) return false;
   if(l1.sign>l2.sign) return true;
   if(l1.longs<l2.longs) return l1.sign==0?false:true;
   if(l1.longs>l2.longs) return l1.sign==0?true:false;
   for(int i=l1.longs-1;i>=0;i--)
   {
      if(l1.dat[i]<l2.dat[i]) return l1.sign==0?false:true;
      if(l1.dat[i]>l2.dat[i]) return l1.sign==0?true:false;
   }
   return false;
}

bool eqzero(const langzahl &l) throw()
{
   if(l.longs>1) return false;
   if(l.longs==0||l.dat[0]==0) return true;
   return false;
}

bool grzero(const langzahl &l) throw()
{
   if(l.sign||!l.longs) return false;
   if(l.longs>1||l.dat[0]>0) return true;
   return false;
}

bool ltzero(const langzahl &l) throw()
{
   if(!l.sign||!l.longs) return false;
   if(l.longs>1||l.dat[0]>0) return true;
   return false;
}

langzahl operator -(const langzahl &l) throw()
{
   langzahl e(l);
   if(e.sign)
      e.sign=0;
   else
      e.sign=-1;
   e.kuerze();
   return e;
}

langzahl operator %(langzahl l,langzahl m) throw()
{
   int len;
   langzahl fak;
   int lsign=l.sign;
   l.sign=0;
   m.sign=0;
   
   if(m.longs==0)
      return l;
   
   len=l.longs-m.longs;
   fak=1;
   while((m*fak<=l) LZ_USER_STOP_CONDITION)
      fak*=10;
   fak/=10;
   langzahl e(l);
   while((fak) LZ_USER_STOP_CONDITION)
   {
      while((m*fak<=e) LZ_USER_STOP_CONDITION)
         e-=m*fak;
      fak/=10;
   }
   if(e.sign) e=_llminus(m,e);
   if(lsign)
   {
      if(e.sign)
         e.sign=0;
      else 
         e.sign=-1;
   }
   e.kuerze();
   return e;
}

langzahl operator /(langzahl l,langzahl m) throw()
{
   if(m.longs==0) // Division by zero
      return l; 
      
   int len;
   langzahl fak;
   int sign=m.sign;
   int lsign=l.sign;
   m.sign=0;
   l.sign=0;
   
   len=l.longs-m.longs;
   fak=1;
   while((m*fak<=l) LZ_USER_STOP_CONDITION)
      fak*=10;
   fak/=10;
   langzahl e(l),d(0);
   while((fak) LZ_USER_STOP_CONDITION)
   {
      while((m*fak<=e) LZ_USER_STOP_CONDITION)
      {
         e-=m*fak;
         d+=fak;
      }
      fak/=10;
   }
   if(e.sign) d+=1;
   
   if((sign==0 && lsign==-1) || (sign==-1 && lsign==0))
   {
      if(d.sign)
         d.sign=0;
      else
         d.sign=-1;
   }
   d.kuerze();
   return d;
}

inline langzahl _llplus(const langzahl &l1,const langzahl &l2) throw()
{
   int i;
   langzahl e(lsize(l1.longs+1));
   for(i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
   {
      e.dat[i]+=l1.dat[i]+l2.dat[i];
      if(e.dat[i]>99999999)
      {
         e.dat[i]-=100000000;
         e.dat[i+1]=1;
      }
   }
   for(;(i<l1.longs) LZ_USER_STOP_CONDITION;i++)
   {
      e.dat[i]+=l1.dat[i];
      if(e.dat[i]>99999999)
      {
         e.dat[i]-=100000000;
         e.dat[i+1]=1;
      }
   }
   e.kuerze();
   return e;
}

inline langzahl _llminus(const langzahl &l1,const langzahl &l2) throw()
{
   int i;
   langzahl e(lsize(l1.longs+1));
   for(i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
   {
      e.dat[i]+=l1.dat[i]-l2.dat[i];
      if(e.dat[i]<0)
      {
         e.dat[i]+=100000000;
         e.dat[i+1]=-1;
      }
   }
   for(;(i<l1.longs) LZ_USER_STOP_CONDITION;i++)
   {
      e.dat[i]+=l1.dat[i];
      if(e.dat[i]<0)
      {
         e.dat[i]+=100000000;
         e.dat[i+1]=-1;
      }
   }
   e.kuerze();
   return e;
}
   
langzahl operator +(const langzahl &l1,const langzahl &l2) throw()
{
   if(l1.sign)
   {
      if(l2.sign)
      {
         if(l1<l2)
            return -(_llplus(-l1,-l2));
         else
            return -(_llplus(-l2,-l1));
      }
      else
      {
         if((-l1)>=l2)
            return -(_llminus(-l1,l2));
         else
            return _llminus(l2,-l1);
      }
   }
   else
   {
      if(l2.sign)
      {
         if(l1>=(-l2))
            return _llminus(l1,-l2);
         else
            return -(_llminus(-l2,l1));
      }
      else
      {
         if(l1>=l2)
            return _llplus(l1,l2);
         else
            return _llplus(l2,l1);
      }
   }
}

langzahl operator -(const langzahl &l1,const langzahl &l2) throw()
{
   if(l1.sign)
   {
      if(l2.sign)
      {
         if(l2>=l1)
            return -(_llminus(-l1,-l2));
         else
            return (_llminus(-l2,-l1));
      }
      else
      {
         if((-l1)>=l2)
            return -(_llplus(-l1,l2));
         else
            return -(_llplus(l2,-l1));
      }
   }
   else
   {
      if(l2.sign)
      {
         if(l1>=(-l2))
            return _llplus(l1,-l2);
         else
            return _llplus(-l2,l1);
      }
      else
      {
         if(l1>=l2)
            return _llminus(l1,l2);
         else
            return -_llminus(l2,l1);
      }
   }
}

langzahl operator *(const langzahl &l1,const langzahl &l2) throw()
{
   langzahl e(lsize(l1.longs+l2.longs));
   int d,z,zw1;
   for(int i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
   {
      z=l2.dat[i];
      for(int j=0,fak=10000000,mod=10;(j<8) LZ_USER_STOP_CONDITION;j++,fak/=10,mod*=10)
      {
         d=z/fak;
         z-=d*fak;
         for(int k=0;(k<l1.longs) LZ_USER_STOP_CONDITION;k++)
         {
            zw1=l1.dat[k]*d;
            e.dat[i+k]+=(zw1%mod)*fak;
            e.dat[i+k+1]+=zw1/mod+(e.dat[i+k]/100000000);
            e.dat[i+k]%=100000000;
         }
      }
   }
   if(l1.sign+l2.sign==-1) e.sign=-1;
   else e.sign=0;
   e.kuerze();
   return e;
}   

inline void div2(langzahl &l) throw()
{
   int i;
   for(i=0;(i<l.longs-1) LZ_USER_STOP_CONDITION;i++)
   {
      l.dat[i]=(l.dat[i]>>1);
      if(l.dat[i+1]&1) l.dat[i]+=50000000;
   }
   l.dat[i]=l.dat[i]>>1;
   l.kuerze();
}

// Achtung: Ergebnis ist nicht gekuerzt!
inline void mul2(langzahl &l) throw()
{
   if(l.dat[l.longs-1]>=50000000)
   {
      LONG32 *ndat=new LONG32[l.longs+1];
      ndat[l.longs]=0;
      for(int i=l.longs-1;(i>=0) LZ_USER_STOP_CONDITION;i--)
      {
         ndat[i]=l.dat[i]<<1;
         if(ndat[i]>=100000000)
         {
            ndat[i]-=100000000;
            ndat[i+1]++;
         }
      }
      l.longs++;
      delete [] l.dat;
      l.dat=ndat;
   }
   else
   {
      for(int i=l.longs-1;(i>=0) LZ_USER_STOP_CONDITION;i--)
      {
         l.dat[i]=l.dat[i]<<1;
         if(l.dat[i]>=100000000)
         {
            l.dat[i]-=100000000;
            l.dat[i+1]++;
         }
      }
   }
}

langzahl &langzahl::operator +=(const langzahl &l2) throw()
{
   *this=*this+l2;
//   int i;
//   longs=MAX(longs,l2.longs)+1;
//   int *ndat=new int[longs];
//   for(i=0;i<longs;i++)
//      ndat[i]=dat[i];
//   for(;i<longs;i++)
//      ndat[i]=0;
//   for(i=0;i<l2.longs;i++)
//   {
//      ndat[i]+=l2.dat[i];
//      if(ndat[i]>99999999)
//      {
//         ndat[i]-=100000000;
//         ndat[i+1]+=1;
//      }
//   }
//   delete [] dat;
//   dat=ndat;
//   kuerze();
   return *this;
}

langzahl &langzahl::operator -=(const langzahl &l2) throw()
{
   *this=*this-l2;
//   int i;
//   longs=MAX(longs,l2.longs);
//   int *ndat=new int[longs];
//   for(i=0;i<longs;i++)
//      ndat[i]=dat[i];
//   for(;i<longs;i++)
//      ndat[i]=0;
//   for(i=0;i<l2.longs;i++)
//   {
//      ndat[i]-=l2.dat[i];
//      if(ndat[i]<0)
//      {
//         ndat[i]+=100000000;
//         ndat[i+1]-=1;
//      }
//   }
//   delete [] dat;
//   dat=ndat;
//   kuerze();
   return *this;
}

langzahl &langzahl::operator *=(const langzahl &l2) throw()
{
   LONG32 *ndat=new LONG32[longs+l2.longs];
   for(int i=0;(i<longs+l2.longs) LZ_USER_STOP_CONDITION;i++)
      ndat[i]=0;
   LONG32 d,z,zw1;
   for(int i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
   {
      z=l2.dat[i];
      for(int j=0,fak=10000000,mod=10;(j<8) LZ_USER_STOP_CONDITION;j++,fak/=10,mod*=10)
      {
         d=z/fak;
         z-=d*fak;
         for(int k=0;(k<longs) LZ_USER_STOP_CONDITION;k++)
         {
            zw1=dat[k]*d;
            ndat[i+k]+=(zw1%mod)*fak;
            ndat[i+k+1]+=zw1/mod+(ndat[i+k]/100000000);
            ndat[i+k]%=100000000;
         }
      }
   }
   if(sign+l2.sign==-1) sign=-1;
   longs+=l2.longs;
   delete [] dat;
   dat=ndat;
   kuerze();
   return *this;
}   

langzahl &langzahl::operator %=(const langzahl &m) throw()
{
   int len;
   langzahl fak;
   if(m.longs==0)
      return *this;
   len=longs-m.longs;
   fak=1;
   while((m*fak<*this) LZ_USER_STOP_CONDITION)
      fak*=10;
   fak/=10;
   while((fak) LZ_USER_STOP_CONDITION)
   {
      while((m*fak<=*this) LZ_USER_STOP_CONDITION)
         *this-=m*fak;
      fak/=10;
   }
   if(sign) *this=_llminus(m,*this);
   kuerze();
   return *this;
}

langzahl addm(const langzahl &l1,const langzahl &l2,const langzahl &m) throw()
{
   int i;
   langzahl e(lsize(l1.longs+1));
   for(i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
   {
      e.dat[i]+=l1.dat[i]+l2.dat[i];
      if(e.dat[i]>99999999)
      {
         e.dat[i]-=100000000;
         e.dat[i+1]=1;
      }
   }
   for(;(i<l1.longs) LZ_USER_STOP_CONDITION;i++)
   {
      e.dat[i]+=l1.dat[i];
      if(e.dat[i]>99999999)
      {
         e.dat[i]-=100000000;
         e.dat[i+1]=1;
      }
   }
   e.kuerze();
   return e%m;
}

//hier noch optimieren! Analog normalem Minus, mit Vorzeichenwechsel!
langzahl subm(const langzahl &l1,const langzahl &l2,const langzahl &m) throw()
{
   int i;
   langzahl e(lsize(l1.longs+1)),corr(l1);
   while((l2>corr) LZ_USER_STOP_CONDITION)
      corr=corr+m;
   for(i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
   {
      e.dat[i]+=corr.dat[i]-l2.dat[i];
      if(e.dat[i]<0)
      {
         e.dat[i]+=100000000;
         e.dat[i+1]=-1;
      }
   }
   for(;(i<corr.longs) LZ_USER_STOP_CONDITION;i++)
   {
      e.dat[i]+=corr.dat[i];
      if(e.dat[i]<0)
      {
         e.dat[i]+=100000000;
         e.dat[i+1]=-1;
      }
   }
   e.kuerze();
   return e%m;
}

langzahl multm(const langzahl &l1,const langzahl &l2,const langzahl &m) throw()
{
   langzahl e(lsize(l1.longs+l2.longs));
   LONG32 d,z,zw1;
   for(int i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
   {
      for(int k=0;(k<l1.longs) LZ_USER_STOP_CONDITION;k++)
      {
         z=l2.dat[i];
         for(int j=0,fak=10000000,mod=10;(j<8) LZ_USER_STOP_CONDITION;j++,fak/=10,mod*=10)
         {
            d=z/fak;
            z-=d*fak;
            zw1=l1.dat[k]*d;
            e.dat[i+k]+=(zw1%mod)*fak;
            e.dat[i+k+1]+=zw1/mod+(e.dat[i+k]/100000000);
            e.dat[i+k]%=100000000;
         }
      }
   }
   e.kuerze();
   return e%m;
}   

langzahl potm(const langzahl &l,const int n,const langzahl &m) throw()
{
   langzahl e(1),a(l);
   int b(n);
   while((b>1) LZ_USER_STOP_CONDITION)
   {
      if(b&1)
      {
         b--;
         e*=a; // testen, ob sich hier ein % lohnt!!  <===============
      }
      b=b>>1;
      a*=a;
      a%=m;
   }
   e*=a;
   return e%m;
}

langzahl pow(const langzahl &l,const langzahl &n) throw()
{
   langzahl e(1),a(l),b(n);
   
   while((b>1) LZ_USER_STOP_CONDITION)
   {
      if(b.dat[0]&1)
      {
         b.dat[0]--;
         e*=a;
      }
      div2(b);
      a*=a;
   }
   e*=a;
   if((n.dat[0]&1)==0 && l.sign)
      e.sign=0;
   return e;
}

langzahl potm(const langzahl &l,const langzahl &n,const langzahl &m) throw()
{
   langzahl e(1),a(l),b(n);
   while((b>1) LZ_USER_STOP_CONDITION)
   {
      if(b.dat[0]&1)
      {
         b.dat[0]--;
         e*=a; // testen, ob sich hier ein % lohnt!!  <===============
      }
      div2(b);
      a*=a;
      a%=m;
   }
   e*=a;
   return e%m;
}

langzahl pow(const langzahl &l1,const LONG32 n) throw()
{
   langzahl e(1),a(l1);
   int b=n;
   while((b>1) LZ_USER_STOP_CONDITION)
   {
      if(b&1)
      {
         b--;
         e*=a;
      }
      b>>1;
      a*=a;
   }
   e*=a;
   return e;
}

langzahl operator *=(langzahl &l1,const LONG32 n) throw()
{
   LONG32 *ndat=new LONG32[l1.longs+1];
   for(int i=0;(i<l1.longs+1) LZ_USER_STOP_CONDITION;i++)
      ndat[i]=0;
   LONG32 d,z,zw1;
   for(int k=0;(k<l1.longs) LZ_USER_STOP_CONDITION;k++)
   {
      z=n;
      for(int j=0,fak=10000000,mod=10;(j<8) LZ_USER_STOP_CONDITION;j++,fak/=10,mod*=10)
      {
         d=z/fak;
         z-=d*fak;
         zw1=l1.dat[k]*d;
         ndat[k]+=(zw1%mod)*fak;
         ndat[k+1]+=zw1/mod;
      }
   }
   l1.longs++;
   delete [] l1.dat;
   l1.dat=ndat;
   l1.kuerze();
   return l1;
}   

langzahl operator /=(langzahl &l,const LONG32 n) throw()
{
   const LONG32 mod=100000000%n;
   const LONG32 div=100000000/n;
   LONG32 rest=0;
   LONG32 *ndat=new LONG32[l.longs];
   ndat[l.longs-1]=0;
   for(int i=l.longs-1;(i>0) LZ_USER_STOP_CONDITION;i--)
   {
      ndat[i]+=(l.dat[i]+rest*mod)/n;
      rest=l.dat[i]%n;
      ndat[i-1]=div*rest;
   }
   ndat[0]+=l.dat[0]/n;
   delete [] l.dat;
   l.dat=ndat;
   l.kuerze();
   return l;
}

langzahl ggT(const langzahl &l1,const langzahl &l2) throw()
{
   langzahl a,b,c;
//   if(l1+l2==0)
//      cerr<<"Kann keinen ggT bilden von "<<l1<<" und "<<l2<<"!"<<endl;
   a=l1;
   b=l2;
   c=b;
   while((grzero(a) LZ_USER_STOP_CONDITION))
   {
      c=a;
      a=b%a;
      b=c;
   }
   return c;
}

// hier wird nur pseudoprim bzgl a getestet, man sollte mehrere a probieren!
bool pprim(const langzahl &n,const langzahl &a) throw()
{
   int i=0,k;
   langzahl m(n),b;
   m-=1;
   k=0;
   while((!(m.dat[0]&1) LZ_USER_STOP_CONDITION))
   {
      div2(m);
      k++;
   }
   if(ggT(n,a)!=1) return false; // ist der ggT wirklich noetig?
   b=potm(a,m,n);
   if(b==1||b==n-1) return true;
   for(i=1;((b!=1)&&(i<k)&&(b!=n-1)) LZ_USER_STOP_CONDITION;i++)
   {
      b*=b;
      b%=n;
   }
   if(b==1) return false;
   if(b==n-1) return true;
   return false;
}

langzahl lrandom(int n) throw()
{
   lsize size(n);
   langzahl e(size);
   for(int i=0;(i<n) LZ_USER_STOP_CONDITION;i++)
      e.dat[i]=rand()%100000000;
      
   e.kuerze();      
   return e;
}

/* die hier muss noch geprueft werden
langzahl findprim(int n) throw()
{
   lsize size(n);
   langzahl e(size),d(1);
   const int a[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59 };
   do
   {
      for(int i=0;(i<n) LZ_USER_STOP_CONDITION;i++)
         e.dat[i]=rand()%100000000;
      e.dat[0]|=1;   
      for(int i=0;i<17;i++)
         d*=a[i];
   } while(((ggT(d,e)!=1)||(!pprim(e,random()))||(!pprim(e,random()))||(!pprim(e,random()))) LZ_USER_STOP_CONDITION);
   return e;
}
*/

langzahl fak(LONG32 k) throw()
{
   langzahl e(1);
   for(;(k>1) LZ_USER_STOP_CONDITION;k--)
      e=e*k;
   return e;
}

langzahl fak(LONG32 k,const langzahl &n) throw()
{
   langzahl e(1);
   for(;(k>1) LZ_USER_STOP_CONDITION;k--)
      e=multm(e,k,n);
   return e;
}

// hier sollten noch Verfeinerungen angebracht werden
langzahl pollard(const langzahl &n) throw()
{
   langzahl e,m;
   LONG32 k(1);
   m=potm(2,fak(k),n);
   e=ggT(m-1,n);
   while(((e==1)&&(e!=n)) LZ_USER_STOP_CONDITION)
   {
      k+=2;
      m=potm(m,k*(k-1),n);
      e=ggT(m-1,n);
   }
   return e;
}

/*
void lsh3(langzahl &l) throw()
{
   LONG32 d;
   for(int i=l.longs-1;i>0;i--)
   {
      l.dat[i]=l.dat[i]<<3;
      l.dat[i]=;
*/
int langzahl::operator !() const throw()
{
   for(int i=0;i<longs;i++)
      if(dat[i]) return(false);
   return true;
}