1 // -*- C++ -*- 2 //============================================================================================== 3 // 4 // This file is part of LiDIA --- a library for computational number theory 5 // 6 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved. 7 // 8 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/ 9 // 10 //---------------------------------------------------------------------------------------------- 11 // 12 // $Id$ 13 // 14 // Author : 15 // Changes : See CVS log 16 // 17 //============================================================================================== 18 19 20 // A trace_list is a list of trace_mod's. Note that only Atkin primes 21 // are stored in the list, Elkies primes are handled directly. Therefore 22 // (C3, M3) holds the collection of all Elkies primes. 23 // 24 // template class: used for eco_prime (bigmod) and eco_gf2n (gf2n) 25 26 27 #ifndef LIDIA_TRACE_LIST_H_GUARD_ 28 #define LIDIA_TRACE_LIST_H_GUARD_ 29 30 31 32 #ifndef LIDIA_UDIGIT_H_GUARD_ 33 # include "LiDIA/udigit.h" 34 #endif 35 #ifndef LIDIA_BIGINT_H_GUARD_ 36 # include "LiDIA/bigint.h" 37 #endif 38 #ifndef LIDIA_LIDIA_VECTOR_H_GUARD_ 39 # include "LiDIA/lidia_vector.h" 40 #endif 41 #ifndef LIDIA_TRACE_MOD_H_GUARD_ 42 # include "LiDIA/trace_mod.h" 43 #endif 44 #ifndef LIDIA_ELLIPTIC_CURVE_H_GUARD_ 45 # include "LiDIA/elliptic_curve.h" 46 #endif 47 #ifndef LIDIA_POINT_H_GUARD_ 48 # include "LiDIA/point.h" 49 #endif 50 #ifndef LIDIA_GF_ELEMENT_H_GUARD_ 51 # include "LiDIA/gf_element.h" 52 #endif 53 54 55 56 #ifdef LIDIA_NAMESPACE 57 namespace LiDIA { 58 # define IN_NAMESPACE_LIDIA 59 #endif 60 61 62 63 class trace_list 64 { 65 public: 66 67 friend std::ostream & operator << (std::ostream & o, const trace_list & t); 68 friend std::istream & operator >> (std::istream & i, trace_list & t); 69 70 private: 71 72 elliptic_curve< gf_element > E; 73 74 sort_vector< trace_mod > l; // l[i] are the possible values of the trace c 75 // modulo the i-th Atkin prime 76 bigint M1; // babystep modulus 77 bigint M2; // giantstep modulus 78 bigint M3; // c = c3 mod M3 79 bigint four_sqrt_q; // size of interval 80 bigint C3; // trace c mod M3 81 lidia_size_t last_index; // use l[0, ..., last_index] in BG phase 82 83 static int info; 84 static int MAX_NOF_TRACES; // maximal number of candidates for the trace 85 86 void tl_sort (lidia_size_t left, lidia_size_t right); 87 88 public: 89 90 trace_list (); 91 ~trace_list (); 92 93 const bigint& get_M1() const; 94 const bigint& get_M2() const; 95 const bigint& get_M3() const; 96 const bigint& get_C3() const; 97 bigint get_absolute_smallest_C3() const; 98 const sort_vector< trace_mod > & get_list() const; 99 100 public: 101 static void set_info_mode(int i=0); 102 static void set_max_nof_traces(int m); 103 104 void clear(); 105 void set_curve(const elliptic_curve< gf_element > & e); 106 107 108 private: 109 bigint number_of_combinations(); 110 111 bool split_baby_giant(sort_vector< bigint > & baby, 112 sort_vector< bigint > & giant); 113 114 void transform_lists(sort_vector< bigint > & baby, 115 sort_vector< bigint > & giant); 116 117 public: 118 bool append(const trace_mod &); // add a trace mod to the list, return 119 // true iff BG can start 120 121 bigint bg_search_for_order(); 122 bigint simple_search_for_order(); 123 bool baby_giant_lists_correct (const bigint & ec_order); 124 125 126 }; 127 128 // friend functions of class trace_list 129 130 std::ostream & operator << (std::ostream & o, const trace_list & t); 131 std::istream & operator >> (std::istream & i, trace_list & t); 132 133 134 135 #ifdef LIDIA_NAMESPACE 136 } // end of namespace LiDIA 137 # undef IN_NAMESPACE_LIDIA 138 #endif 139 140 141 142 #endif // LIDIA_TRACE_LIST_H_GUARD_ 143