1 //==============================================================================================
2 //
3 // This file is part of LiDIA --- a library for computational number theory
4 //
5 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved.
6 //
7 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/
8 //
9 //----------------------------------------------------------------------------------------------
10 //
11 // $Id$
12 //
13 // Author : Volker Mueller (VM), Markus Maurer (MM)
14 // Changes : See CVS log
15 //
16 //==============================================================================================
17
18 #ifdef HAVE_CONFIG_H
19 # include "config.h"
20 #endif
21 #include "LiDIA/eco_prime.h"
22 #include "LiDIA/wep_rat_function.h"
23
24
25
26 #ifdef LIDIA_NAMESPACE
27 namespace LiDIA {
28 #endif
29
30
31
32 // these functions search for the eigenvalue of Frobenius after
33 // Elkies polynomial is known. Several search algorithms are supported.
34 // returns true <=> something has been found
35
36 //-----------------------------------------------------------------
37 // alpha : eigenvalue to be computed
38 // fC : Elkies polynomial
39 // lpower : compute eigenvalue mod l^lpower
40 // prev_ev : eigenvalue mod l^(lpower-1)
41 //
42 // test_all : controls the search for alpha in
43 // Phi (X, Y) == alpha * (X, Y)
44 //
45 // 0 --> stop searching after first match
46 // 1 --> test all possible values for alpha
47 // or stop after second match
48 //
49 //
50
find_eigenvalue(lidia_size_t & alpha,const ff_pol & fC,lidia_size_t prev_ev,lidia_size_t lpower,bool test_all)51 bool eco_prime::find_eigenvalue (lidia_size_t & alpha,
52 const ff_pol & fC,
53 lidia_size_t prev_ev,
54 lidia_size_t lpower,
55 bool test_all)
56 {
57 lidia_size_t *klist; // list of possible eigenvalues
58 lidia_size_t lpow = 1;
59 bool rc = false;
60
61
62 //****** computation for l == 3 ******
63
64 if (l == 3 && lpower == 1)
65 // deg(fC) == (l-1)/2 == 1 --> computation in Fq
66 return eigenv_mod3 (alpha, fC);
67
68
69 //****** computation for l > 3 or lpower > 1 ******
70
71 if (sp_type == ONE_SUBGRP_INV || sp_type == ALL_SUBGRPS_INV) {
72 if (lpower == 1) {
73 // eigenvalue^2 = p^n = q mod l
74 klist = new lidia_size_t [2];
75 klist[0] = 1;
76
77 if (jacobi (static_cast<udigit>(eco_prime::q), static_cast<udigit>(this->l))) {
78 klist[1] = (lidia_size_t)
79 sqrt_mod(static_cast<udigit>(eco_prime::q),
80 static_cast<udigit>(this->l));
81 if (klist[1] > static_cast<int>((this->l-1)/2))
82 klist[1] = this->l - klist[1];
83
84 if (test_x_coordinate()) {
85 alpha = klist[1];
86 if (test_x_coordinate_uniquely())
87 sign_dewaghe(alpha, fC);
88 rc = true;
89 }
90 else {
91 char ev = ev_strategy & 0x0f;
92
93 if (ev == eco_prime::EV_RATIONAL_FUNCTION ||
94 ev == eco_prime::EV_RATIONAL_FUNCTION_TABLE)
95 rc = schoofpart_rat_function(alpha, fC, klist, test_all);
96 else
97 rc = schoofpart(alpha, fC, klist, test_all);
98
99 if (alpha < 0)
100 alpha += l;
101 }
102
103 delete[] klist;
104 return rc;
105 }
106 else {
107 prev_ev ++;
108 lidia_error_handler ("eco_prime::find_eigenvalue",
109 "p^n is not a square mod l");
110 return false;
111 }
112 }
113 else {
114 lidia_error_handler ("eco_prime::find_eigenvalue()",
115 "Sorry, eigenvalue modulo powers of l not"
116 " yet implemented");
117 return false;
118 }
119 }
120
121 //------------------------------------------------------------
122 // now we have Elkies type (11ddd)
123 // first we determine list of candidates for ev.
124
125
126 if (lpower == 1)
127 {
128 lidia_size_t * d_list;
129
130 if (sp_degree_known)
131 {
132 d_list = new lidia_size_t[2];
133 d_list[0] = 1;
134 d_list[1] = sp_degree;
135 }
136 else
137 compute_d_list (d_list);
138
139 // use d for computing possible candidates for ev
140
141 compute_ev_list (d_list, klist);
142 refine_ev_list(fC, klist);
143 delete[] d_list;
144 }
145 else
146 {
147 lidia_error_handler ("eco_prime::find_eigenvalue()",
148 "Sorry, eigenvalue modulo prime powers not"
149 " yet implemented.");
150 return false;
151 }
152
153 //---------------------------------------------------------
154 // now we search for the ev.
155
156 if (lpower == 1) {
157 char ev = ev_strategy & 0x0f;
158
159 #ifdef TIMING
160 timer t;
161 t.set_print_mode();
162 t.start_timer();
163 #endif
164
165 if (ev == eco_prime::EV_RATIONAL_FUNCTION ||
166 ev == eco_prime::EV_RATIONAL_FUNCTION_TABLE)
167 rc = schoofpart_rat_function(alpha, fC, klist, test_all);
168 else
169 if (ev == eco_prime::EV_DIVISION_POLYNOMIAL ||
170 (ev == eco_prime::EV_OPTIMAL &&
171 ((l % 4 == 1) || l <= lower_bound_for_FBG)))
172 rc = schoofpart(alpha, fC, klist, test_all);
173 else
174 if (ev == eco_prime::EV_BABYSTEP_GIANTSTEP)
175 rc = schoofpart_BG(alpha, fC, klist);
176 else
177 if (ev == eco_prime::EV_FUNNY_BABYSTEP_GIANTSTEP ||
178 (ev == eco_prime::EV_OPTIMAL && l % 4 == 3))
179 rc = schoofpart_FBG(alpha, fC, klist);
180 else
181 lidia_error_handler("eco_prime",
182 "wrong ev strategy chosen");
183
184 #ifdef TIMING
185 t.stop_timer();
186 if (info)
187 std::cout << "\nTotal time needed to find eigenvalue : " << t << std::flush;
188 #endif
189
190 if (test_x_coordinate_uniquely()) {
191 sign_dewaghe(alpha, fC);
192
193 if (info) {
194 std::cout << "\nDewaghe's method: Eigenvalue of Frobenius is ";
195 std::cout << alpha << std::flush;
196 }
197 }
198
199 delete[] klist;
200
201 if (rc) {
202 if (alpha < 0) {
203 switch (lpower) {
204 case 1 : lpow = l;
205 break;
206
207 case 2 : lpow = l * l;
208 break;
209
210 default :
211 lidia_error_handler("eco_prime", "find_eigenvalue::Can't handle prime");
212 }
213 alpha += lpow;
214 }
215 }
216 return rc;
217 }
218 return rc;
219 }
220
221
222
223 //
224 // this is the special version for finding the eigenvalue of Frobenius
225 // for l==3. In this case, all computations can be done in Fq, since
226 // degree of Elkies polynomial is 1.
227 //
228
229 //-------------------------------------------------------------------
230 // fC = (monic) Elkies polynomial for l == 3
231 //
232
eigenv_mod3(lidia_size_t & alpha,const ff_pol & fC)233 bool eco_prime::eigenv_mod3 (lidia_size_t & alpha, const ff_pol &fC)
234 {
235 ff_element rootfC, x3axb_pm1h;
236 bigint pm1h; // == (q-1)/2
237
238 shift_right (pm1h, pn, 1);
239 negate (rootfC, ff_element(fC.const_term()));
240
241 // x3axb_pm1h = (rootfC^3 + a*rootfC + b)^((q-1)/2)
242
243 square (x3axb_pm1h, rootfC);
244 add (x3axb_pm1h, eco_prime::A, x3axb_pm1h);
245 multiply (x3axb_pm1h, x3axb_pm1h, rootfC);
246 add (x3axb_pm1h, x3axb_pm1h, eco_prime::B);
247 power (x3axb_pm1h, x3axb_pm1h, pm1h);
248
249 // test whether Y^(q-1) == +-1
250
251 if (x3axb_pm1h.is_one())
252 alpha = 1;
253 else
254 alpha = 2;
255
256 return true;
257 }
258
259
260
261 #ifdef LIDIA_NAMESPACE
262 } // end of namespace LiDIA
263 #endif
264