CRelation-inc.cc

Go to the documentation of this file.

inline CRelation::ProvideDynamicRelationsStream::ProvideDynamicRelationsStream(Pistream &pistream_)
 : pistream(pistream_), reuse(true)
{
  if (!pistream)
   {
     //cout << "acquired an istream!" << endl;
     pistream=DynamicRelations::IstreamPool::acquire_istream();
     reuse=false;
   } //else cout << "reusing an istream!" << endl;
}

inline CRelation::ProvideDynamicRelationsStream::~ProvideDynamicRelationsStream()
{
  if (!reuse)
   {
     DynamicRelations::IstreamPool::release_istream(pistream);
     pistream=NULL;
   }
}




// this is used to store the sieved dynamic factors.
// Remark: To collect the dynamic factors efficiently in the sieving phase, I decided to make this array global.
//         (The constructor of "CRelation" is called with the number of found dynamic factors for each relation.)
CHits Hits[CHits::MaxHits]; // collected dynamic factors

// important: The exponent need not to (and shouldn't) be set during the sieving phase. It will be evaluated
// inside the constructor (and only there!) while the relation is split into its factors.
// Also keep in mind not to place any composite numbers as factors into this struct.


#ifndef IS_SERVER

CRelation::CRelation(const signed int SievePos, short int HitCount /* =0 */)
: CProvideHelperVariables(), relevant_factor(no_factor), Relation_sparse(new CTinyFBsizetypeVector), Relation_dense(NULL),
  pDynamicRelations_from_file(NULL), pMulticombineData(NULL)
  /* constructor: insert a new relation.
     initialize "Deltas" with the value of Delta,
     (re)split the relation into its factors; thereby pick up only the factors, whose exponents are odd
     (if the exponent is even, then the factor can be replaced by factor^2 and thereby be handled as a square!)
   */
{
  // cout << "initialize relation" << endl;
  mpz_init(Delta);
  Polynom.get_values(SievePos,Delta,y);
  // in y: reduced square (which is now to be factorized...) 
  mpz_invert(Delta,Delta,n); /* we use the modular inverse of Delta,
                                this saves us an extra variable;
                                doing so, the quadratic congruence
                                is normalized to Delta^2=1 (mod n)
                              */
  
  if (mpz_sgn(y)<0) // negative numbers (handle sign)
    {
      Relation_sparse->append(0);
       // -1 must be considered to handle the sign;
       // we have to insert a "0", because StaticFactorbase::PrimeNumbers[0]=-1.
      mpz_neg(y,y); // switch sign (to make positive)
    }
  
  // special handling for the first factor of the static factorbase.
  // In MPQS we have problems to sieve for prime number 2...

  if (StaticFactorbase::PrimeNumbers[1]==2)
   {
     // special treatment for 2, since it it very easy:
     const unsigned int z = mpz_scan1(y,0);
     if (z)
      {
        mpz_tdiv_q_2exp(y,y,z);
        mpz_mul_2exp(Delta,Delta,z>>1);
        if (z&1) Relation_sparse->append(1); // mark odd exponent of the prime number
      }
   }
  else
   {
     // this is the common case (which works also for 2)  
     unsigned int z=0;
     while (mpz_div_ui(x,y,StaticFactorbase::PrimeNumbers[1])==0) { mpz_set(y,x); z++; }

     if (z&1) Relation_sparse->append(1); // mark odd exponent of the prime number
     if (z>1) // need to multiply "valid square roots" into Delta?
      {
        if (z<4) mpz_mul_ui(Delta,Delta,StaticFactorbase::PrimeNumbers[1]);
        else
         {
           mpz_set_ui(x,StaticFactorbase::PrimeNumbers[1]); mpz_powm_ui(x,x,z/2,n);
           mpz_mul(Delta,Delta,x);
         }
      }
   }

  {
    // find factors in static factorbase
    // (beginning with the 3. prime of FB (s.o) )
    vector<unsigned int> FB_Primteiler;
    CDeltaComputations::GetStaticFactorHits(FB_Primteiler,SievePos);

    // multiply factors to collect them, and then divide them in one go
    mpz_set_ui(x,1);
    for (unsigned int i=0; i<FB_Primteiler.size(); i++) mpz_mul_ui(x,x,StaticFactorbase::PrimeNumbers[FB_Primteiler[i]]);
    mpz_divexact(y,y,x);

    // factor reduction using the principle of inclusion/exclusion
    // die Faktor-Potenzen nach dem Prinzip Inklusion/Exklusion abdividieren
    vector<unsigned int> WithOddExponent, TempTeiler;
    while (mpz_cmp_ui(x,1)>0) // is there a factor from our FB?
     {
       mpz_gcd(x,x,y); // prime numbers of FB, that divide a even number of times
       mpz_divexact(y,y,x); // divide by them
       mpz_mul(Delta,Delta,x); // multiply them to our square root Delta
       for (unsigned int i=0; i<FB_Primteiler.size(); ++i)
        if (mpz_divisible_ui_p(x,StaticFactorbase::PrimeNumbers[FB_Primteiler[i]]))
          TempTeiler.push_back(FB_Primteiler[i]); // will divide again...
        else
          WithOddExponent.push_back(FB_Primteiler[i]); // this was the last time that it divided.
       FB_Primteiler.swap(TempTeiler); TempTeiler.clear();

       mpz_gcd(x,x,y); mpz_divexact(y,y,x); // odd number of times
       for (unsigned int i=0; i<FB_Primteiler.size(); ++i)
        if (mpz_divisible_ui_p(x,StaticFactorbase::PrimeNumbers[FB_Primteiler[i]]))
          TempTeiler.push_back(FB_Primteiler[i]); // will divide again
       FB_Primteiler.swap(TempTeiler); TempTeiler.clear();
     }
    mpz_mod(Delta,Delta,n);
    std::sort(WithOddExponent.begin(),WithOddExponent.end());
    for (unsigned int i=0; i<WithOddExponent.size(); ++i)
     {
       Relation_sparse->append(WithOddExponent[i]);
     }
  }


  // reduce factors from dynamic factorbase (and maybe pushed squares...)
  // multiply the factors together and divide them in one go.
  if (HitCount)
   {
     mpz_set_ui(x,Hits[0].Faktor); Hits[0].Exponent = 1;
     for (int i=1; i<HitCount; i++) { Hits[i].Exponent = 1; mpz_mul_ui(x,x,Hits[i].Faktor); }
#if defined(DEBUG)
     if (!mpz_divisible_p(y,x)) { MARK; cerr << "Wrong divisor in Hits!" << endl; exit(1); }
#endif
     mpz_divexact(y,y,x);
     mpz_gcd(x,x,y);
     if (mpz_cmp_ui(x,1)!=0) // are there higher exponents?
      {
        // find exponents of factors in dynamic factorbase (and maybe pushed squares...)
        for (int i=0; i<HitCount; ++i)
         {
           while (mpz_divisible_ui_p(y,Hits[i].Faktor))
            {
              mpz_divexact_ui(y,y,Hits[i].Faktor);
              Hits[i].Exponent++; // increment exponent of factor
            }
#ifdef DEBUG
           if (Hits[i].Exponent==2)
            {
              MARK;
              cout << "Square in Hits[]: " << Hits[i].Faktor;
              if (is_dynamic_factor(Hits[i].Faktor))
               cout << " (dynamic factor)" << endl;
              else
               cout << " (pushed square)" << endl;
            }
#endif
           if (Hits[i].Exponent>1)
            {
              mpz_set_ui(x, Hits[i].Faktor);
              mpz_powm_ui(x,x,Hits[i].Exponent/2, n);
              mpz_mul(Delta,Delta,x); mpz_mod(Delta,Delta,n);
              Hits[i].Exponent%=2;
            }
         }
      }
   }

  // Restfactor outside of the static factorbase...
  const bool existiert_grosser_Restfaktor = (mpz_cmp_ui(y,StaticFactorbaseSettings::BiggestPrime())>0);

  if (existiert_grosser_Restfaktor && collecting_phase_finished)
    { relevant_factor=special_factor; return; } // premature cancellation

  if (!existiert_grosser_Restfaktor)
    {
      if (mpz_cmp_ui(y,1)!=0) 
        {
          MARK;
          cerr << "relation is inconsistent / BUG in program:" << endl;
          cerr << y << " should be 1!" << endl;
          exit(1);
        }
      relevant_factor=largest_factor_in_Relation();
      // relevant factor can be eliminated later (by utilizing this relation)
    }

#if 0 || defined(SIEVING_MORE_LARGE_SQUARES)
  // dynamic factor sanity check
  for (int i=0; i<HitCount; ++i) if(Hits[i].Exponent!=0)
    {
      if (!is_dynamic_factor(Hits[i].Faktor))
        {
          cerr << "Inconsistency in dynamic factorbase! " << Hits[i].Faktor << " not found as known dynamic factor!" << endl;
          // This is actually an error OR the radix of a pushed square has
          // divided with an odd number of times, and the radix isn't a SLP
          // yet (so we cannot resolve the resulting relation to a static,
          // dynamic or special relation).  This shouldn't happen too often,
          // but it can happen.  Since this is unlikely, we can exit with an
          // error to watch this special case instead of just skipping the
          // relation.
          exit(1); // not necessary, because it should also be safe just to skip this relation
          relevant_factor=dynamic_factor; return; // skip the relation
        }
    }
#else
#ifdef DEBUG
 #warning "dynamic factor sanity check disabled! (just want to mention it)"
#endif
#endif

  if (existiert_grosser_Restfaktor)
    {
      const bool is_possible_dynamic = (mpz_cmp_ui(y, SingleLargePrime_Threshold)<=0);
      if ( !is_possible_dynamic && CmpqsFactor::DLP_rejected(y) )
        {
          // We should first filter out invalid big numbers, especially the
          // primes! It doesn't harm (except for performance) if some composite
          // numbers are filtered out as primes.
          // Important is that "DLP_reject(y)" is not too expensive!
          relevant_factor=special_factor; // ignored factor (because we do not insert any relation)
          return;
        }
        
      if (is_possible_dynamic && probab_prime(mpz_get_ui(y)) )
        {
          // this is a new dynamic factor
          relevant_factor=dynamic_factor;
          TDynamicFactorRelation relation;
          relation.factor=mpz_get_ui(y);

          // the found factor could be a rediscovered SingleLargePrime
          // We should detect this and take appropriate action!
          if (is_dynamic_factor(relation.factor))
           {
             Hits[HitCount].Faktor=relation.factor; Hits[HitCount].Exponent=1; ++HitCount;
             relevant_factor=largest_factor_in_Relation();
             goto done_with_grosser_Restfaktor;
           }
          relation.append_for_sieving();

#ifndef IS_CLIENT
          relation.fpos = save(DynamicRelations::DynamicRelations_to_file,relation.factor, HitCount);
#ifdef SAFEMODE
          // validate the newly generated dynamic factor relation.
          // also the new dynamic factor needs to be feed to the validation routine!
          {
           const streampos rpos=DynamicRelations::DynamicRelations_from_file.tellg();
           DynamicRelations::DynamicRelations_from_file.seekg(relation.fpos);
           CRelation::SanityCheck(DynamicRelations::DynamicRelations_from_file); // exit if relation is invalid (->this would be an internal error!)
           DynamicRelations::DynamicRelations_from_file.seekg(rpos);
          }
#endif
#else /* IS_CLIENT */
          // send it to the output file
          relation.fpos=save(communication_stream,relation.factor, HitCount);
#endif
          DynamicFactorRelations.insert(relation);
          statistical_data::directly_sieved_DynamicFactors++;
#ifndef IS_CLIENT
          SpecialRelations::split_by_primefactor(relation.factor);
#endif
          ++statistical_data::relations_sieved_so_far; // one more relation found
          return;
        }
        
      // it's a special factor, which isn't a prime
      {
        relevant_factor=special_factor;
        TSpecialFactorRelation relation;
        if (!relation.factor.DLP_get(y))
          {
            //cerr << "Hint: Special Factor " << y << " invalid." << endl;
            return; // Don't take over this hit, since it is invalid.
          }
#ifndef IS_CLIENT
        if (!SpecialRelations::insert(relation.factor,this,HitCount))
          {
            relevant_factor=largest_factor_in_Relation();
            // if factor hasn't been marked, then this means, that it
            // has been neutralised. -> we have found a normal relation.

            // ööö/FIXME: nachfolgendes sollte vielleicht besser in SpecialRelations::insert() getan werden?
            //            -> in English: I'm not sure whether the following block should eventually be move into SpecialRelations::insert()
            // kombiniere Faktoren der dynamic Factorbase

            static CRelation::SMulticombineData MD; // static is faster as long as this is no critical resource!
            set_MulticombineData(&MD);
            multi_combine_init();
            for (int i=0; i<HitCount; ++i) if(Hits[i].Exponent!=0)
             {
               //cout << "combining dynamic factor " << Hits[i].Faktor << endl;
               TDynamicFactorRelation FaRelSearch;
               FaRelSearch.factor=Hits[i].Faktor;
               const TDynamicFactorRelations::const_iterator p = DynamicFactorRelations.find(FaRelSearch);
               mpz_mul_ui(Delta,Delta,(*p).factor); mpz_mod(Delta,Delta,n);
               multi_combine_main(DynamicRelations::DynamicRelations_from_file,(*p).fpos);
               //cout << "combined: " << *pos << endl;
             }
            multi_combine_exit();
            invalidate_MulticombineData();
            ++statistical_data::relations_sieved_so_far; // one more relation found
            return;
          }
#else
        // send to output file
        relation.fpos=save(communication_stream, relation.factor, HitCount);
#endif
        statistical_data::directly_sieved_SpecialFactors++;

//ööö 2004-12:
        // activate this small block only for performance tuning & profiling: 
        //cout << (*this) << endl;
        //if (statistical_data::directly_sieved_SpecialFactors>49) exit(0);

        ++statistical_data::relations_sieved_so_far; // one more relation found
        return;
      }
    } // end of "if (existiert_grosser_Restfaktor)"
 done_with_grosser_Restfaktor:

#ifndef IS_CLIENT
  // combining factors of the dynamic factorbase
  static CRelation::SMulticombineData MD; // static is faster as long as this is no critical resource!
  set_MulticombineData(&MD);
  multi_combine_init();
  for (int i=0; i<HitCount; ++i) if(Hits[i].Exponent!=0)
   {
     //cout << "combining dynamic factor " << Hits[i].Faktor << endl;
     TDynamicFactorRelation FaRelSearch;
     FaRelSearch.factor=Hits[i].Faktor;
     const TDynamicFactorRelations::const_iterator p = DynamicFactorRelations.find(FaRelSearch);
     mpz_mul_ui(Delta,Delta,(*p).factor); mpz_mod(Delta,Delta,n);
     multi_combine_main(DynamicRelations::DynamicRelations_from_file,(*p).fpos);
     //cout << "combined: " << *pos << endl;
   }
  multi_combine_exit();
  invalidate_MulticombineData();
#else
  // output to file
  save(communication_stream,1, HitCount);
#endif

  ++statistical_data::relations_sieved_so_far; // one more relation found
  statistical_data::DynamicFactorRating.increment_Hits_at_position(HitCount);
  /* for statistical evaluation on how the dynamic factorbase
     is responsible for the finding of relations:
      [0]-> no dynamic factor is involved,
      [1]-> one dynamic factor is involved
      [2]-> two dynamic factors are involved
      [3]-> three dynamic factors are involved
      [n]-> n dynamic factors are involved
      [mysize-1]-> at least mysize-1 dynamic factors are involved
   */

  //cout << "relation: " << *this << endl;
  //cout << "relevant factor: " << relevant_factor << endl;
  //cout << "Finished initialization of this relation! (leaving constructor)" << endl;
}

#endif /* IS_SERVER not defined */



CmpqsFactor CRelation::combine(istream &in)
{
  //cout << "combining relation from file" << endl;
  CStreamDecoder enc_in(in);
  CmpqsFactor ret;
  string s;
  int index;
 
  // save file flags
  const ios::fmtflags oldFlags = in.flags(); // memorize old flags of the stream
  in.unsetf(ios::hex); in.setf(ios::dec); // enable decimal output (notice: because of "correction factors" there could be a recursive call!)
  in.unsetf(ios::showbase); // without any leading prefix
 
  in >> s; // starting symbol "G"
  if (s != "G")
    {
      MARK;
      cerr << "error: wrong position while reading relation" << endl;
      exit(1);
    }
  in >> ret; // read factor (dynamic-factor or special-factor of relation or 1)
  in >> s; // delta
  mpz_set_str(x, s.c_str(), mpzbase_f); // x is classwide auxiliary variable
  mpz_mul(Delta, Delta, x);
  mpz_mod(Delta, Delta, n);

  // now we start to work in hexadecimal notation:
  in.unsetf(ios::dec); in.setf(ios::hex); // hexadecimal output
  in.unsetf(ios::showbase); // without "0x"-marker
  
  /*
    compute symmetric difference of the factors in the relation
    Multiply the common part (=intersection) into square root Delta
  */
  mpz_set_ui(x,1); // for speedup: collect factors in x as long as x<n
  signed int distance; // hint: we work with differences instead of the values itself

  if (Relation_dense) // Relation is dense
    { // compute symmetric difference using dense-representation
      distance=enc_in.GetValue(); index=distance;
      while (distance >= 0)
        {
          if (Relation_dense->test(index))
            if (index>0)
              {
                mpz_mul_ui(x,x,StaticFactorbase::PrimeNumbers[index]);
                if (mpz_cmp(x,n)>=0)
                  {
                    mpz_mod(x,x,n); mpz_mul(Delta,Delta,x);
                    mpz_mod(Delta,Delta,n); mpz_set_ui(x,1);
                  }
              } //else mpz_neg(Delta,Delta);
          Relation_dense->invert(index);
          distance=enc_in.GetValue(); index+=distance;
        }
    }
  else
    { // compute symmetric difference using sparse-representation
      int p1 = 0;
      CTinyFBsizetypeVector neueMenge(StaticFactorbase::Size());
      //neueMenge.reset(); // "clear" without deallocating memory
      const CTinyFBsizetypeVector& R = *Relation_sparse;
      
      distance=enc_in.GetValue(); index=distance; 
      while (distance>=0 && p1<R.size())
        {
          while (index<R[p1])
            {
              neueMenge.append(index); distance=enc_in.GetValue(); index+=distance;
              if (distance<0) goto done;
            }
          while (R[p1]<index)
            {
              neueMenge.append(R[p1]); ++p1;
              if (p1==R.size()) goto done;
            }
          while (index==R[p1])
            {
              if (index>0)
                {
                  mpz_mul_ui(x,x,StaticFactorbase::PrimeNumbers[index]);
                  if (mpz_cmp(x,n)>=0)
                    {
                      mpz_mod(x,x,n); mpz_mul(Delta,Delta,x);
                      mpz_mod(Delta,Delta,n); mpz_set_ui(x,1);
                    }
                } //else mpz_neg(Delta,Delta);
              distance=enc_in.GetValue(); index+=distance; ++p1;
              if (distance<0) goto done;
              if (p1==R.size()) goto done;      
            }
        }
    done:
      while (distance>=0) { neueMenge.append(index); distance=enc_in.GetValue(); index+=distance; }
      while (p1!=R.size()) { neueMenge.append(R[p1]); ++p1; }
      Relation_sparse->copy_from(neueMenge); // take over new set
      //optisize(); // optimize memory usage (sparse<->dense, etc.)
    }
  
  // x contains (possibly) a remaining value, which has to be multiplied into Delta:
  mpz_mul(Delta,Delta,x); mpz_mod(Delta,Delta,n);
 
  if (distance == -2) // "correction factors" follow
    {
      /* Korrekturfaktoren sind dynamische Faktoren, die zum Zeitpunkt der Generierung
         der gelesenen Relation nicht aufgelöst wurden. Sie müssen daher jetzt verknüpft werden. */
      /* correction factors are dynamic factors, that weren't resolved at the time of generating
         this relation. They must be considered and combined now! */
      TDynamicFactorRelation FaRelSearch;
      stack<int> DeferredFactors; // breadth first search (Breitensuche) to avoid perpetually seeking on file.
      while ( (FaRelSearch.factor=enc_in.GetValue())>0 ) DeferredFactors.push(FaRelSearch.factor);
      
      ProvideDynamicRelationsStream to_me(pDynamicRelations_from_file); // constructor acquires and destructor releases pDynamicRelations_from_file...
      while (!DeferredFactors.empty())
        {
          FaRelSearch.factor=DeferredFactors.top(); DeferredFactors.pop();
          //cout << "Korrekturfaktor: " << FaRelSearch.factor << " für " << setprecision(20) << ret << endl;

          fillin_streampos(FaRelSearch);
           // fillin_streampos will throw an exception, if FaRelSearch.factor is not a member.
           // we could catch the exception and do "ret=0; break;" to skip this factor and continue with new data...

          mpz_mul_ui(Delta,Delta,FaRelSearch.factor); mpz_mod(Delta,Delta,n);
          (*pDynamicRelations_from_file).seekg(FaRelSearch.fpos);
          if ((*pDynamicRelations_from_file).peek()==EOF) seek_emergency_handler(*pDynamicRelations_from_file,FaRelSearch.fpos);
          if (combine(*pDynamicRelations_from_file).IsTypeOf(CmpqsFactor::empty)) { ret=0; break; } // combine on background storage device; return ret=0 on failure
          //cout << "finished combining " << FaRelSearch.factor << endl;
        }
    }
  
  in.flags(oldFlags); // restore memorized stream flags
 
  relevant_factor=largest_factor_in_Relation();
  //cout << "finished combining relation from file." << endl;
  return ret;
}

CmpqsFactor CRelation::multi_combine_main(istream &in)
{
  //cout << "multi-combine relation from file..." << endl;
  CStreamDecoder enc_in(in);
  adjust_multi_combine(); // keep aware of number of calls (do not remove; this is essential!)

  TExponentArrayElement *ExponentArray = pMulticombineData->ExponentArray;

  CmpqsFactor ret;
  string s;
  int index;
 
  // save file flags
  const ios::fmtflags oldFlags = in.flags(); // memorize old flags of the stream
  in.unsetf(ios::hex); in.setf(ios::dec); // enable decimal output (notice: because of "correction factors" there could be a recursive call!)
  in.unsetf(ios::showbase); // without any leading prefix
 
  in >> s; // starting symbol "G"
  if (s != "G")
    {
      MARK;
      cerr << "error: wrong position while reading relation" << endl;
      exit(1);
    }
  in >> ret; // read factor (dynamic-factor or special-factor of relation or 1)
  in >> s; // delta
  mpz_set_str(x, s.c_str(), mpzbase_f); // x is classwide auxiliary variable
  mpz_mul(Delta, Delta, x);
  mpz_mod(Delta, Delta, n);

  // now we start to work in hexadecimal notation:
  in.unsetf(ios::dec); in.setf(ios::hex); // hexadecimal output
  in.unsetf(ios::showbase); // without "0x"-marker
  
  /*
    compute symmetric difference of the factors in the relation
    Multiply the common part (=intersection) into square root Delta
  */
  signed int distance; // hint: we work with differences instead of the values itself

  if (Relation_dense) // Relation is dense
    { // compute symmetric difference using dense-representation
      distance=enc_in.GetValue(); index=distance;
      while (distance >= 0)
        {
          if (Relation_dense->test_and_invert(index)) ++ExponentArray[index];
          distance=enc_in.GetValue(); index+=distance;
        }
    }
  else
    { // compute symmetric difference using sparse-representation
      int p1 = 0;
      CTinyFBsizetypeVector neueMenge(StaticFactorbase::Size());
      //neueMenge.reset(); // "leeren" ohne Speicherfreigabe
      const CTinyFBsizetypeVector& R = *Relation_sparse;
      
      distance=enc_in.GetValue(); index=distance; 
      while (distance>=0 && p1<R.size())
        {
          while (index<R[p1])
            {
              neueMenge.append(index); distance=enc_in.GetValue(); index+=distance;
              if (distance<0) goto done;
            }
          while (R[p1]<index)
            {
              neueMenge.append(R[p1]); ++p1;
              if (p1==R.size()) goto done;
            }
          while (index==R[p1])
            {
              ++ExponentArray[index];
              distance=enc_in.GetValue(); index+=distance; ++p1;
              if (distance<0) goto done;
              if (p1==R.size()) goto done;      
            }
        }
    done:
      while (distance>=0) { neueMenge.append(index); distance=enc_in.GetValue(); index+=distance; }
      while (p1!=R.size()) { neueMenge.append(R[p1]); ++p1; }
      Relation_sparse->copy_from(neueMenge); // take over new set
    }

  if (distance == -2) // "correction factors" follow
    {
      /* Korrekturfaktoren sind dynamische Faktoren, die zum Zeitpunkt der Generierung
         der gelesenen Relation nicht aufgelöst wurden. Sie müssen daher jetzt verknüpft werden. */
      /* correction factors are dynamic factors, that weren't resolved at the time of generating
         this relation. They must be considered and combined now! */

      TDynamicFactorRelation FaRelSearch;
      stack<int> DeferredFactors; // breadth first search (Breitensuche) to avoid perpetually seeking on file.
      while ( (FaRelSearch.factor=enc_in.GetValue())>0 ) DeferredFactors.push(FaRelSearch.factor);

      ProvideDynamicRelationsStream to_me(pDynamicRelations_from_file); // constructor acquires and destructor releases pDynamicRelations_from_file...
      while (!DeferredFactors.empty())
        {
          FaRelSearch.factor=DeferredFactors.top(); DeferredFactors.pop();
          //cout << "Korrekturfaktor: " << FaRelSearch.factor << " für " << setprecision(20) << ret << endl;

          fillin_streampos(FaRelSearch);
           // fillin_streampos will throw an exception, if FaRelSearch.factor is not a member.
           // we could catch the exception and do "ret=0; break;" to skip this factor and continue with new data...

          mpz_mul_ui(Delta,Delta,FaRelSearch.factor); mpz_mod(Delta,Delta,n);
          (*pDynamicRelations_from_file).seekg(FaRelSearch.fpos);
          if ((*pDynamicRelations_from_file).peek()==EOF) seek_emergency_handler(*pDynamicRelations_from_file,FaRelSearch.fpos);
          if (multi_combine_main(*pDynamicRelations_from_file).IsTypeOf(CmpqsFactor::empty)) { ret=0; break; } // combine on background storage device; return ret=0 on failure
          //cout << "finished combining " << FaRelSearch.factor << endl;
        }
    }
  
  in.flags(oldFlags); // restore memorized stream flags
 
  relevant_factor=largest_factor_in_Relation();
  //cout << "finished multi-combine from file." << endl;
  return ret;
}

streampos CRelation::save(ostream &out, const CmpqsFactor factor, const short int HitCount /* = 0 */) const
{
  CStreamEncoder enc_out(out);
#ifndef IS_CLIENT
  streampos pos;
  // out.seekp(0,ios::end);  // should be already at the end of the file
  pos = out.tellp(); // get file position
#endif
  char *str;

  str = new char [mpz_sizeinbase(Delta,mpzbase_f)+2]; mpz_get_str(str,mpzbase_f, Delta);
  out << "G " << setprecision(20) << factor << " " << str << " ";
  delete [] str;

  // now we start to work in hexadecimal notation:
  const ios::fmtflags oldFlags = out.flags(); // memorize old stream flags
  out << hex; // hexadecimal output
  out.unsetf(ios::showbase); // without "0x"-marker
  
  /* remark:
     Instead of storing the values theirself, we store the distances between them (which is more space-efficient!) */
  if (Relation_dense)
    { 
      int prev = 0;
      for (int i=Relation_dense->first(); i>=0; i=Relation_dense->next(i))
        {
          enc_out.PutValue(i-prev);
          prev=i;
        } 
    }
  else
    {
      int prev = 0;
      for (int i=0; i<Relation_sparse->size(); ++i)
        {
          int h = (*Relation_sparse)[i];
          enc_out.PutValue(h-prev);
          prev=h;
        }
    }

  int Count_SLP_in_relation = 0;
  for (int i=0; i<HitCount; ++i) if (Hits[i].GetExponent()>0) ++Count_SLP_in_relation;
  if (Count_SLP_in_relation>0)
    {
      enc_out.PutValue(-2);
      //cout << "Korrekturfaktoren für Relation mit Faktor " << setprecision(20) << factor << endl;
      for (int i=0; i<HitCount; ++i)
        { 
          //cout << Hits[i].Faktor << "^" << Hits[i].Exponent << endl; 
          if (Hits[i].GetExponent()>0) enc_out.PutValue(Hits[i].Faktor);
        }
    }
  enc_out.PutValue(-1); out << endl;
  out.flags(oldFlags); // restore old state of format-flags
#ifdef IS_CLIENT
  return 0;
#else
  return pos;
#endif
}



#ifndef IS_CLIENT
bool CRelation::ComputeQuadraticCongruence() const
{
  /* The determined relation satisfies the congruency (A²=1) mod n.
     Because of A²-1²=(A+1)*(A-1)=0 mod n, we can construct a factor by computing ggT(A+1,n);
     we have a good chance that this factor is not a trivial one... */

  mpz_t x,y;
  mpz_init(x); mpz_init(y);

  StatusReport(true);
#ifdef VERBOSE_NOTICE
  cout << endl << "Found a suitable relation..." << endl;
#endif

  if (!empty())
   {
     MARK;
     cerr << "Error! Relation contains unresolved members!" << endl;
   }

  mpz_powm_ui(x,Delta,2,n);

#ifdef VERBOSE_INFO
  cout << "[" << Delta << "]² = 1 (mod N)" << endl;
  cout << "-> " << x << " = 1 (mod N)" << endl;
#endif
  
  if (mpz_cmp_ui(x,1)!=0) 
    {
      cerr << "Error! Squares are NOT congruent!" << endl;
      cerr << "?? [" << Delta << "]² = 1 (mod N)" << endl;
      cerr << "?? -> " << x << " = 1 (mod N)" << endl;
      exit(1);
    }
  
  mpz_add_ui(x,Delta,1);
  mpz_gcd(x,x,n); mpz_divexact(y,n,x); // notice: n and *not* kN is the number to factorize!
  
  if ((mpz_cmp_ui(x,1)==0) || (mpz_cmp_ui(y,1)==0))
    {
#ifdef VERBOSE_NOTICE
      cout << "factorization was trivial..." << endl << endl;
#endif
    }
  else
    {
      if (mpz_cmp(x,y)>0) mpz_swap(x,y); // we want x<y

      cout << endl << "factor found!" << endl;
      cout << x << " * ";
      cout << y << endl;
      cout << "= ";
      cout << n << endl;
      
      if (mpz_probab_prime_p(x,probab_prime_checks))
        {
          mpz_divexact(n,n,x);
          cout << x << " is a factor." << endl;
          std::ostringstream comment;
          comment << " [dmpqs]";
          Factorization_to_file << MAL(x,1,comment) << flush;
        }
      else
        if (Potenztest(x)) mpz_divexact(n,n,x); // remove powers...

      if (mpz_probab_prime_p(y,probab_prime_checks))
        {
          mpz_divexact(n,n,y);
          cout << y << " is a factor." << endl;
          std::ostringstream comment;
          comment << " [dmpqs]";
          Factorization_to_file << MAL(y,1,comment) << flush;
        }
      else
        if (Potenztest(y)) mpz_divexact(n,n,y); // remove powers...
      

      if (mpz_cmp_ui(n,1)==0) // factorization complete?
        { 
          cout << "factorization successfully completed." << endl;
          Factorization_to_file << endl;
          mpz_clear(x); mpz_clear(y);
          return true; 
        }
    }
#ifdef VERBOSE_NOTICE
  cout << "continue factorization..." << endl << endl;
#endif
  mpz_clear(x); mpz_clear(y);
  return false;
}
#endif

---