src/.svn/text-base/divisor.C.svn-base

   1 /* Implementation of genus 2 divisor arithmetic over V. Shoup's
   2    NTL library
   3 */
   4
   5 #if HAVE_CONFIG_H
   6 #include <config.h>
   7 #endif
   8
   9 #include <assert.h>
  10 #include <g2hec_Genus2_ops.h>
  11
  12 NS_G2_START_IMPL
  13
  14 /*****************************************************\
  15  Initialize static member s_hcurve of class divisor
  16 \*****************************************************/
  17 g2hcurve my_curve;
  18 g2hcurve divisor::s_hcurve = my_curve;
  19
  20 void divisor::update() {
  21   bool_t OK = TRUE;
  22
  23   // Check curve's validity
  24   OK = OK && s_hcurve.is_valid_curve();
  25
  26   /* Check if [u, v] belongs to Jacobian of genus 2 curve
  27    It is so if
  28    (1) u is monic
  29    (2) deg(v) < deg(u) <= genus = 2
  30    (3) u | v^2 + v*h - f
  31   */
  32
  33   OK = OK && IsOne( LeadCoeff(upoly) ); // (1)
  34
  35   OK = OK && ( deg(upoly) <= genus ) && ( deg(vpoly) < deg(upoly) ); // (2)
  36
  37   OK = OK && IsZero(( vpoly*(vpoly + s_hcurve.get_h())
  38                       - s_hcurve.get_f() ) % upoly ); // (3)
  39
  40   // Set is_valid flag
  41   is_valid = OK;
  42
  43 }
  44
  45
  46 bool_t divisor::is_valid_divisor() const {
  47   return is_valid;
  48 }
  49
  50 bool_t divisor::is_unit(){
  51   assert(is_valid); // Invalid divisor is checked runtime error
  52
  53   return ( IsOne(upoly) && IsZero(vpoly) );
  54 }
  55
  56 void divisor::set_unit() {
  57   assert(s_hcurve.is_valid_curve()); // Invalid curve is checked runtime error
  58
  59   clear(vpoly); // vpoly = 0
  60   set(upoly); // upoly = 1
  61   update();
  62 }
  63
  64 divisor& divisor::random(divdeg_t dgr){ // Underlying curve is not touched
  65   assert(s_hcurve.is_valid_curve());
  66
  67   // A random valid divisor is generated by the following algorithm:
  68   // generate a degree 1 divisor [x - a1, b1] by choosing a1 by random
  69   // then trying to solve quadratic equation
  70   // x^2 + h(a1)*x - f(a1) for b1.
  71   // Note that finding a root of an equation by calling routine
  72   // FindRoot(root, poly) may go into an infinite loop if poly does
  73   // not split completely.  We avoid this by calling irreducibility
  74   // test routine DetIrredTest(poly).  After a degree 1 divisor is
  75   // found, this divisor is doubled by calling add_cantor() to return
  76   // a degree 2 polynomial.
  77
  78   field_t a1, b1, f_of_a1, h_of_a1;
  79
  80   poly_t poly;  // polynomial x^2 + h(a1)*x - f(a1)
  81
  82   SetCoeff(poly, 2); // set degree 2 leading term to 1
  83
  84   do {
  85     do{
  86       NTL_NNS random(a1);
  87
  88       eval(f_of_a1, s_hcurve.get_f(), a1);
  89
  90       eval(h_of_a1, s_hcurve.get_h(), a1);
  91
  92       SetCoeff(poly, 1, h_of_a1);
  93       SetCoeff(poly, 0, - f_of_a1);
  94
  95     } while ( DetIrredTest(poly) );
  96
  97   FindRoot(b1, poly);
  98
  99     // Set upoly = x - a1
 100     SetX(upoly);
 101     SetCoeff(upoly, 0, -a1);
 102
 103     // Set vpoly = b1
 104     vpoly = b1;
 105
 106     update();
 107   } while (*this == -*this); // Avoid getting unit after doubling
 108
 109   // return a degree one divisor if dgr = 1
 110   if (dgr == DEGREE_1)
 111     return *this;
 112
 113   // Double the degree 1 divisor to get a degree 2 divisor, otherwise
 114   add_cantor(*this, *this, *this);
 115
 116   if (is_valid_divisor())
 117     return *this;
 118
 119   cerr << "Random divisor failed to generate" << endl;
 120   abort();
 121 }
 122
 123
 124 divisor& divisor::random() {
 125   return random(DEGREE_2);
 126 }
 127
 128
 129 std::ostream& operator<<(std::ostream& s, const divisor& a)
 130 {
 131   s << "###" << endl;
 132
 133 s << "Divisor [u(x), v(x)] for Jacobian group of curve y^2 + h(x)*y = f(x)."
 134   << endl;
 135
 136 // print curve info
 137  s << a.get_curve();
 138
 139  // print u, v
 140  s << "[u(x), v(x)]:" << endl;
 141
 142  s << "       u(x) = ";
 143
 144  print_poly(a.get_upoly(), &s);
 145
 146  s << "       v(x) = ";
 147  print_poly(a.get_vpoly(), &s);
 148
 149 // Is divisor valid?
 150  if (a.is_valid_divisor())
 151    s << "       Divisor is valid" << endl;
 152  else
 153    s << "       Divisor is invalid" << endl;
 154
 155  s << "###" << endl;
 156
 157  return s;
 158 }
 159
 160 NS_G2_END_IMPL