include/g2hec_Genus2_ops.h

   1 /*++
   2
   3 Copyright (c) 2008
   4
   5 Module Name:
   6     g2hec_Genus2_ops.h
   7
   8 Summary:
   9     Definitions for genus 2 (imaginary) hyperelliptic curve arithmetic.
  10     Curves are of the form y^2 + h(x)y = f(x), w/ deg(f)=5.
  11     The group operations in the Jacobian variety of the curve are implemented
  12 with both explicit formulas and the generic Cantor's algorithm.
  13
  14 Author:
  15     Ning Shang  2008-07-28  Created
  16
  17 Notes:
  18     TBD
  19
  20
  21 --*/
  22
  23 #ifndef GENUS2_OPS_H
  24 #define GENUS2_OPS_H
  25
  26 // The following headers need to be included for initial setup
  27 /* Start include headers */
  28 #include "g2hec_nstools.h"
  29 #include "g2hec_nsfieldtype.h"
  30 /* End include headers */
  31
  32 /* Some types */
  33 //enum bool_t { FALSE = 0, TRUE = 1};
  34 //typedef enum bool_t bool_t;
  35 typedef bool bool_t;
  36 #define FALSE 0
  37 #define TRUE 1
  38
  39 typedef long ndeg_t;
  40
  41 // Divisor degree
  42 enum divdeg_t { DEGREE_1 = 1, DEGREE_2 = 2};
  43 typedef enum divdeg_t divdeg_t;
  44
  45
  46 /* For C++ */
  47 //#ifdef __cplusplus
  48 //extern "C"{
  49 //#endif
  50
  51 NTL_CLIENT
  52
  53 NS_G2_OPEN_NS
  54
  55 /* genus 2 */
  56 const long genus = 2;
  57
  58   /* Determine the polynomial type according to field type */
  59 #define DETERMINE_POLY_TYPE
  60 /* Genus 2 hyperelliptic curve class */
  61 class g2hcurve {
  62   private:
  63   poly_t fpoly; // f(x), degree 5 for genus 2
  64
  65   poly_t hpoly; // h(x), degree <=2 for genus 2
  66
  67   bool_t is_nonsingular;
  68
  69   bool_t is_genus_2;
  70
  71   public:
  72   g2hcurve() { // Default constructor points f, h to polynomial 0
  73     is_genus_2 = is_nonsingular = FALSE;
  74   }
  75
  76   g2hcurve(const poly_tc& poly1, const poly_tc& poly2) { // C-tor
  77     fpoly = poly1;    hpoly = poly2;
  78   }
  79
  80   g2hcurve(const g2hcurve& hcurve) { // Copy constructor
  81     fpoly = hcurve.fpoly;
  82     hpoly = hcurve.hpoly;
  83     is_nonsingular = hcurve.is_nonsingular;
  84     is_genus_2 = hcurve.is_genus_2;
  85   }
  86
  87   g2hcurve& operator=(const g2hcurve& hcurve) // assignment
  88   {
  89     fpoly = hcurve.fpoly;
  90     hpoly = hcurve.hpoly;
  91     is_nonsingular = hcurve.is_nonsingular;
  92     is_genus_2 = hcurve.is_genus_2;
  93     return *this;
  94   }
  95
  96   ~g2hcurve() {} // D-tor
  97
  98   void set_f(const poly_tc& poly); // Set f(x) for curve
  99
 100   void set_h(const poly_tc& poly); // Set h(x) for curve
 101
 102   void update(); // Check and reset is_nonsingular and is_genus_2 flags
 103
 104   const poly_tc& get_f() const;
 105
 106   const poly_tc& get_h() const;
 107
 108   bool_t is_valid_curve() const; // Return TRUE if is_nonsingular && is_genus_2
 109
 110   g2hcurve& random(); // Generate a random valid curve
 111
 112
 113 };
 114
 115
 116 /* Divisor definition:
 117 a divisor in a Jacobian variety of a genus 2 curve is given by a pair
 118 of polynomials [u(x), v(x)], where deg(u) is at most 2 and deg(v) is at
 119 most 1.
 120 */
 121 class divisor {
 122  private:
 123   poly_t upoly;  // degree at most 2
 124
 125   poly_t vpoly; // degree at most 1
 126
 127   static g2hcurve s_hcurve; //  underlying curve
 128   // Defined as a static data member.  Only one curve exists at one time.
 129   // s_hcurve need to be initialized in implementation. ("divisor.c")
 130
 131   bool_t is_valid; // Flag if divisor is valid
 132
 133  public:
 134   divisor() // Default C-tor. Set u=1, v=0, s_hcurve=default
 135     {
 136     upoly = 1; vpoly = 0; is_valid = FALSE;
 137     }
 138
 139   divisor(const poly_tc& polyu, const poly_tc& polyv, const g2hcurve& curve)
 140 // C-tor
 141   {upoly = polyu; vpoly = polyv; is_valid = FALSE; s_hcurve = curve;}
 142
 143   divisor(const divisor& div) // Copy c-tor
 144     {upoly = div.upoly; vpoly = div.vpoly; is_valid = div.is_valid; }
 145
 146   divisor& operator=(const divisor& div) // Assignment
 147     {
 148       upoly = div.upoly; vpoly = div.vpoly; is_valid = div.is_valid;
 149       return *this;
 150     }
 151
 152   ~divisor() {};  // D-tor
 153
 154   void set_upoly(poly_tc& poly) {upoly = poly;} // Set upoly
 155
 156   void set_vpoly(poly_tc& poly) {vpoly = poly;} // Set vpoly
 157
 158   void set_curve(const g2hcurve& curve) // Set hcurve
 159     { divisor::s_hcurve = curve; }
 160
 161   void update(); // Check and update is_valid flag. Must be called by client
 162   // after any set_ routine is called
 163
 164   const poly_tc& get_upoly() const // Get upoly
 165     { return upoly; }
 166
 167   const poly_tc& get_vpoly() const // Get vpoly
 168     { return vpoly; }
 169
 170   const g2hcurve& get_curve() const // Return curve
 171     { return s_hcurve; }
 172
 173   bool_t is_valid_divisor() const; // Return TRUE if s_hcurve.is_valid_curve
 174   // and [u, v] is an element of the Jacobian of the curve. Client must
 175   // call it to check validity of divisor before doing arithmetic.
 176
 177   bool_t is_unit();
 178
 179   void set_unit();
 180
 181   divisor& random(); // If s_hcurve is valid, set divisor to a random valid
 182                      // divisor of degree 2
 183
 184   divisor& random(divdeg_t dgr); // If s_hcurve is valid set divisor to a
 185                          //random valid divisor of degree dgr. drg takes
 186                          // value DEGREE_1 or DEGREE_2
 187 };
 188
 189 /******************************************************\
 190   Divisor Arithmetic
 191 \******************************************************/
 192 /* Procedure version */
 193   bool_t add_cantor(divisor& x, const divisor& a, const divisor& b);
 194   // x = a + b via Cantor's algorithm
 195
 196   bool_t add(divisor& x, const divisor& a, const divisor& b);
 197   // x = a + b via explicit formulas; execptions are handled by calling
 198   // add_cantor()
 199
 200   bool_t sub(divisor& x, const divisor& a, const divisor& b);
 201   // x = a - b
 202
 203   bool_t dnegate(divisor& x, const divisor& a);
 204   // x = -a
 205
 206   bool_t scalar_mul(divisor& x, const divisor& a, const ZZ& n,
 207                     bool_t (*method)(divisor&, const divisor&, const ZZ&));
 208   // x = [n]*a. The following methods are exported:
 209 // (1) Square and multiply: SAM
 210 // (2) Non-adjacent form: NAF
 211 // (3) Montgomery's ladder: ML
 212 // When no method is specified, SAM is used as default.
 213
 214 bool_t scalar_mul(divisor& x, const divisor& a, long n,
 215                   bool_t (*method)(divisor&, const divisor&, const ZZ&));
 216
 217 /* Supported scalar multiplication methods */
 218 bool_t SAM(divisor& x, const divisor& a, const ZZ& n);
 219      // Square and multiply
 220
 221 bool_t NAF(divisor& x, const divisor& a, const ZZ& n);
 222 // Non-adjacent form
 223
 224 bool_t ML(divisor& x, const divisor& a, const ZZ& n);
 225 // Montgomery's ladder
 226
 227
 228
 229 /* Operator version */
 230   inline divisor operator+(const divisor& a, const divisor& b)
 231   {divisor x; add(x, a, b); return x;}
 232
 233   inline divisor operator-(const divisor& a, const divisor& b)
 234   {divisor x; sub(x, a, b); return x;}
 235
 236   inline divisor operator-(const divisor& a)
 237   {divisor x; dnegate(x, a); return x;}
 238
 239   inline divisor operator*(long n, const divisor& a)
 240   {divisor x; scalar_mul(x, a, n, NULL); return x;}
 241
 242   inline divisor operator*(const divisor& a, long n)
 243   {divisor x; scalar_mul(x, a, n, NULL); return x;}
 244
 245   inline divisor operator*(const ZZ& n, const divisor& a)
 246   {divisor x; scalar_mul(x, a, n, NULL); return x;}
 247
 248   inline divisor operator*(const divisor& a, const ZZ& n)
 249   {divisor x; scalar_mul(x, a, n, NULL); return x;}
 250
 251 /******************************************************\
 252   Comparisons
 253 \******************************************************/
 254 inline bool_t operator==(const g2hcurve& a, const g2hcurve& b)
 255 {
 256   return (a.get_f() == b.get_f() && a.get_h() == b.get_h());
 257 }
 258
 259 inline bool_t operator!=(const g2hcurve& a, const g2hcurve& b)
 260 {
 261   return (!(a==b));
 262 }
 263
 264 inline bool_t on_same_curve(const divisor& a, const divisor& b)
 265        // Return TRUE if a and b have the same underlying curve
 266        // Since the g2hcurve data member is implemented as static,
 267      // this is always true. This function is not needed.
 268
 269  //{return ( a.get_curve() == b.get_curve() );}
 270 {return TRUE;}
 271
 272   inline bool_t operator==(const divisor& a, const divisor& b)
 273   {
 274     return (on_same_curve(a, b) &&
 275            a.get_upoly() == b.get_upoly() &&
 276             a.get_vpoly() == b.get_vpoly());
 277    }
 278
 279   inline bool_t operator!=(const divisor& a, const divisor& b)
 280   {
 281     return ( !(a == b) );
 282   }
 283
 284 /******************************************************\
 285   I/O
 286 \******************************************************/
 287 /* Print polynomial */
 288 void print_poly(poly_tc& poly, std::ostream* s);
 289
 290 /* Print curve */
 291   std::ostream& operator<<(std::ostream& s, const g2hcurve& a);
 292
 293 /* Print divisor */
 294   std::ostream& operator<<(std::ostream& s, const divisor& a);
 295
 296
 297
 298 NS_G2_CLOSE_NS
 299
 300 //#ifdef __cplusplus
 301 //}
 302 //#endif
 303
 304 #endif /* GENUS2_OPS_H */