elliptic_curve.H

Go to the documentation of this file.

#ifndef ECM_HEADER_
#define ECM_HEADER_

// Declaration of elliptic curves method (ecm) V1.35
// written by Thorsten Reinecke
// last change: 2007-05-21

#include <iosfwd>
#include <gmp.h>
#include "utils.H"
#include "mpz_wrapper.H"
using namespace my_mpz_wrapper;

using std::ostream;
using std::istream;

using std::cout;
using std::cerr;
using std::flush;

extern mpz_t n;


//#define DEBUG_ECM /* funktioniert nur im SLOW_WEIERSTRASS-Modus ohne NRESIDUE! */
//#define SLOW_WEIERSTRASS /* in allen Phasen in der Form (x:y:1) rechnen */


// you may choose one (or none) of the following defines:
/* 
   Hint: up to 300 digits you should disable both,
         above 300 digits MODULAR_ARITHMETIC should be enabled
         (on 32 bit processors).
*/
         

//#define NRESIDUE /* use "modular_mult.cc" instead of mpz_mod */
/* Sollte in der aktuellen Implementierung asymptotisch schneller sein als
   mod mit Trialdivision. Da aber das Restklassensystem ein anderes ist,
   gibt es bei einigen Operationen Kompatibilitätsprobleme.
   Wenn man die Operation "redc" durch eine (ggf.) asymptotisch schlechtere,
   aber besser (maschinennähere) Implementierung ersetzt, dürfte dies
   für kleine Zahlen die schnellste Variante sein und (bei asymptotisch guter
   Implementierung) für größere Zahlen ähnlich schnell wie
   "MODULAR_ARITHMETIC" ablaufen.
*/
   

//#define MODULAR_ARITHMETIC /* use modular_arithmetic.cc instead of mpz_mod (if possible) */
/* Verwendung von reciprocal, d.h. "mpz_mod(a,b,n)" wird durch
   a=b-floor(b*(2^k/n)/2^k) ersetzt, wobei 2^k/n konstant bleibt,
   und 1/2^k durch Shiften realisiert wird.
   -> 2 Multiplikationen ersetzen 1 Division.
   Dies ist (bei Verwendung von Karatsuba oder noch schnelleren
   Multiplikationen) asymptotisch schneller als die in gmp-2.0.2 verwendete
   trialdivision. Scheint sich ab ca. 300 Dezimalstellen zu rentieren.
*/
  

#if defined(NRESIDUE) && defined (MODULAR_ARITHMETIC)
 #error "You must not define both: NRESIDUE and MODULAR_ARITHMETIC"
#endif

#if ! ( defined(NRESIDUE) || defined(MODULAR_ARITHMETIC) )
 // we use mpz_mod
 #define mpz_mulmod(res,a,b,n) { mpz_mul(res,a,b); mpz_mod(res,res,n); }
 #define modulo(res,T,n) mpz_mod(res,T,n)
#endif 

#ifdef NRESIDUE
 #include "modular_mult.cc"
 /* WICHTIG: 
     A) Alle Werte, mit denen gerechnet wird, vorher nach NRESIDUE konvertieren!
     B) Das Resultat einer Multiplikation muß durch ein "redc" wieder normiert
        werden, bevor es verwendet werden kann!
     C) redc niemals (ohne genaue Analyse) ohne vorherige Multiplikation verwenden!
     -> daher: für MULTIPLIKATION am besten immer das MAKRO mpz_mulmod benutzen!
 */ 
 #define mpz_mulmod(res,a,b,n) { mpz_mul(res,a,b); NResidue.redc(res,res); }
 #define modulo(res,T,n) NResidue.redc(res,T)
#endif

#ifdef MODULAR_ARITHMETIC
 #include "modular_arithmetic.cc"
 #define mpz_mulmod(res,a,b,n) { mpz_mul(res,a,b); NResidue.mod(res,res); }
 #define modulo(res,T,n) NResidue.mod(res,T)
#endif 


#if (CONTINUATION_METHOD > 0)
 #include "polynomial.H"
#endif

#if defined(DEBUG_ECM) && (!defined(SLOW_WEIERSTRASS) || defined(NRESIDUE))
 #error "DEBUG_ECM works only in SLOW_WEIERSTRASS-Mode without NRESIDUE!"
#endif


class TmpzPoint : private ForbidAssignment
{
 public:
  mpz_t x,z;
  inline TmpzPoint() { mpz_init(x); mpz_init(z); } // Konstruktor
  inline ~TmpzPoint() { mpz_clear(z); mpz_clear(x); } // Destruktor
};
typedef TmpzPoint* PmpzPoint;
typedef const TmpzPoint* PconstmpzPoint;


class elliptic_curves : private ForbidAssignment
{
 public:
  typedef long long int NATNUM;
 private:
  mpz_t a,b; // außer in go nur lesend verwendbar!
  mpz_t h,k,m; // allgemein verwendbar (zwischen Aufrufen veränderbar)!
  mpz_t x3,y3; // nur in add, mul2 verwendbar!
  mpz_t xh_mul, yh_mul; // nur in mul verwendbar!
  PmpzPoint A,B,C,T1,T2; // für den PRAC-Algorithmus in XZ_multiply
  int sigma; // über sigma wird die Kurve ausgewählt/definiert
  int phase; // für statistische Zwecke: in welcher Phase befinden wir uns?
#ifdef NRESIDUE
  CN_Residue NResidue;
#endif
#ifdef MODULAR_ARITHMETIC
  CN_Residue NResidue;
#endif
 public:
  inline elliptic_curves() /* Konstruktor */
   : A(new TmpzPoint), B(new TmpzPoint), C(new TmpzPoint),
     T1(new TmpzPoint), T2(new TmpzPoint), sigma(-1), phase(-1) 
#ifdef NRESIDUE
  , NResidue()
 /* Konstruktor aufrufen,
    NResidue wird später mit n initialisiert.
    n ist DIE globale Variable (die faktorisiert werden soll)
    zugegeben: es wäre besser, n trotzdem als Parameter allen Klassen
    zu übergeben, aber ich will's jetzt nicht mehr ändern, da
    dann auch die Rückgabe der Faktoren und die Division n/FAKTOR
    durchgeführt werden müssen... 
 */
#endif   
#ifdef MODULAR_ARITHMETIC
  , NResidue()
 /* Konstruktor aufrufen,
    NResidue wird später mit n initialisiert.
    n ist DIE globale Variable (die faktorisiert werden soll)
    zugegeben: es wäre besser, n trotzdem als Parameter allen Klassen
    zu übergeben, aber ich will's jetzt nicht mehr ändern, da
    dann auch die Rückgabe der Faktoren und die Division n/FAKTOR
    durchgeführt werden müssen... 
 */
#endif   
    {
      mpz_init(a); mpz_init(b);
      mpz_init(h); mpz_init(k); mpz_init(m);
      mpz_init(x3); mpz_init(y3);
      mpz_init(xh_mul); mpz_init(yh_mul);
#ifdef NRESIDUE
      NResidue.init(n);
#endif
#ifdef MODULAR_ARITHMETIC
      NResidue.init(n);
#endif
    }
  inline ~elliptic_curves() /* Destruktor */
    {
      mpz_clear(a); mpz_clear(b);
      mpz_clear(h); mpz_clear(k); mpz_clear(m);
      mpz_clear(x3); mpz_clear(y3); 
      mpz_clear(xh_mul); mpz_clear(yh_mul);
      delete A; delete B; delete C; delete T1; delete T2;
    }
 private:
  void check_curve(const mpz_t x, const mpz_t y) const;
  void factor_found(mpz_t k) const;

  bool sub(mpz_t xr, mpz_t yr,
           const mpz_t x1, const mpz_t y1,
           const mpz_t x2, const mpz_t y2); // for single point
  bool add(mpz_t xr, mpz_t yr,
           const mpz_t x1, const mpz_t y1,
           const mpz_t x2, const mpz_t y2); // for single point
  bool mul2(mpz_t xr, mpz_t yr, const mpz_t x1, const mpz_t y1);
  bool mul(mpz_t xr, mpz_t yr,
           const mpz_t x1, const mpz_t y1,
           NATNUM K);
  bool add(mpz_t xr, mpz_t yr,
           const mpz_t x1, const mpz_t y1,
           const mpz_t x2, const mpz_t y2,
           mpz_t k);
  bool init_arithmetic_progression(mpz_t* const x, mpz_t* const y,
           const mpz_t startx, const mpz_t starty, const NATNUM startpos,
           const unsigned int delta, const unsigned int grad);
  bool arithmetic_progression(mpz_t* const x, mpz_t* const y, const int anz);

  void XZ_mul2(mpz_t xr, mpz_t zr,
               const mpz_t x1, const mpz_t z1);
  inline void XZ_mul2(const PmpzPoint R, const PconstmpzPoint A)
    { XZ_mul2(R->x,R->z,A->x,A->z); }
  void XZ_mul2plus1(mpz_t xr, mpz_t zr,
                    const mpz_t Xp0, const mpz_t Zp0,
                    const mpz_t Xp1, const mpz_t Zp1,
                    const mpz_t x1, const mpz_t z1);
  inline void XZ_mul2plus1(const PmpzPoint R, const PconstmpzPoint A, const PconstmpzPoint B, const PconstmpzPoint C)
    { XZ_mul2plus1(R->x,R->z,A->x,A->z,B->x,B->z,C->x,C->z); }

  static unsigned int cost_of_evaluating_lucas_chain(const NATNUM K, const double alpha);
  void XZ_multiply(mpz_t xr, mpz_t zr, const mpz_t x1, const mpz_t z1, NATNUM K);

 public:
  void go(const int ecm_sigma, NATNUM phase1, const NATNUM phase2);
  inline void go(const int ecm_sigma, const int phase1, const int phase2)
   {
     go(ecm_sigma,static_cast<NATNUM>(phase1),static_cast<NATNUM>(phase2));
   }
  inline void go(const int ecm_sigma, const double phase1, const double phase2)
   {
     go(ecm_sigma,static_cast<NATNUM>(phase1),static_cast<NATNUM>(phase2));
   }

};

#endif /* ECM_HEADER_ */

---