1 // curve.h: declarations of elliptic curve classes
2 //////////////////////////////////////////////////////////////////////////
3 //
4 // Copyright 1990-2012 John Cremona
5 //
6 // This file is part of the eclib package.
7 //
8 // eclib is free software; you can redistribute it and/or modify it
9 // under the terms of the GNU General Public License as published by the
10 // Free Software Foundation; either version 2 of the License, or (at your
11 // option) any later version.
12 //
13 // eclib is distributed in the hope that it will be useful, but WITHOUT
14 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 // for more details.
17 //
18 // You should have received a copy of the GNU General Public License
19 // along with eclib; if not, write to the Free Software Foundation,
20 // Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
21 //
22 //////////////////////////////////////////////////////////////////////////
23
24 // originally adapted from Elliptic.h by Oisin McGuiness
25
26 // allow for multiple includes
27 #ifndef _ECLIB_ELLIPTIC_
28 #define _ECLIB_ELLIPTIC_
29
30 #include <eclib/marith.h>
31 #include <eclib/bigrat.h>
32 #include <map>
33
34 class Curve; class Curvedata; class CurveRed;
35 class Point;
36 class IsogenyClass;
37
38 //general test:
39 int valid_invariants(const bigint& c4, const bigint& c6); //true if valid
40 void c4c6_to_ai(const bigint& c4, const bigint& c6,
41 bigint& a1, bigint& a2, bigint& a3, bigint& a4,
42 bigint& a6,
43 bigint& b2, bigint& b4, bigint& b6, bigint& b8);
44 void c4c6_to_ai(const bigint& c4, const bigint& c6,
45 bigint& a1, bigint& a2, bigint& a3, bigint& a4,
46 bigint& a6);
47 void minimise_c4c6(const bigint& c4, const bigint& c6, const bigint& discr,
48 bigint& newc4, bigint& newc6, bigint& newdiscr, bigint& u);
49
50 //
51 // base class for bare elliptic curve
52 //
53
54 class Curve{
55 friend class Point;
56 friend class IsogenyClass;
57 public:
isnull()58 int isnull() const
59 {return ((a1==0)&&(a2==0)&&(a3==0)&&(a4==0)&&(a6==0));}
getai(bigint & aa1,bigint & aa2,bigint & aa3,bigint & aa4,bigint & aa6)60 void getai(bigint& aa1, bigint& aa2, bigint& aa3,
61 bigint& aa4, bigint& aa6) const
62 {aa1=a1; aa2=a2; aa3=a3; aa4=a4; aa6=a6; }
63
64 // input and output
output(ostream & os)65 void output(ostream& os) const
66 { os<<"["<<a1<<","<<a2<<","<<a3<<","<<a4<<","<<a6<<"]";}
67 //N.B. No spaces in output for ease of input to GP
68
69 void input(istream& is);
70 void tex_print(ostream &) const ;
71 // puts out TeX-ed equation of curve; never been used
72
73 // constructors
Curve(void)74 Curve(void) // :a1(0),a2(0),a3(0),a4(0),a6(0)
75 {a1=0;a2=0;a3=0;a4=0;a6=0;}
76 Curve(const bigint& c4, const bigint& c6); //init by invariants
77 //check valid for elliptic curve
78 //if not create null curve
Curve(const bigint & aa1,const bigint & aa2,const bigint & aa3,const bigint & aa4,const bigint & aa6)79 Curve(const bigint& aa1, const bigint& aa2, const bigint& aa3,
80 const bigint& aa4, const bigint& aa6)
81 :a1(aa1),a2(aa2),a3(aa3),a4(aa4),a6(aa6) {}
Curve(const Curve & c)82 Curve(const Curve& c)
83 : a1(c.a1), a2(c.a2), a3(c.a3), a4(c.a4), a6(c.a6)
84 {}
85 void operator=(const Curve& c)
86 { a1=c.a1; a2=c.a2; a3=c.a3; a4=c.a4; a6=c.a6; }
87 // no destructor is needed
88
89 // equality tests -- inherited, so you can compare Curvedata with Curve
90 int operator==(const Curve& f) const
91 {return ((a1==f.a1)&&(a2==f.a2)&&
92 (a3==f.a3)&&(a4==f.a4)&&(a6==f.a6));}
93 int operator!=(const Curve& f) const
94 {return ((a1!=f.a1)||(a2!=f.a2)||
95 (a3!=f.a3)||(a4!=f.a4)||(a6!=f.a6));}
96 protected:
97 bigint a1 ;
98 bigint a2 ;
99 bigint a3 ;
100 bigint a4 ;
101 bigint a6 ;
102 } ;
103
104
105 //
106 // derived class for curve with computed invariants
107 // NB minimalize() is a member function, flagged if ever called; by
108 // default not called, but see constructors for how to force.
109 //
110
111 class Curvedata : public Curve{
112 friend class CurveRed; // bug fix; ridiculous, is a derived class
113 friend class IsogenyClass;
114 public:
Curvedata()115 Curvedata() {discr_factored=0;}
116 Curvedata(const bigint& aa1, const bigint& aa2, const bigint& aa3,
117 const bigint& aa4, const bigint& aa6, int min_on_init = 0);
118 /*
119 Curvedata(const bigrational& qa1, const bigrational& qa2,
120 const bigrational& qa3, const bigrational& qa4,
121 const bigrational& qa6, bigint& scale);
122 */
123 Curvedata(const vector<bigrational>& qai, bigint& scale);
124 Curvedata(const Curve& c, int min_on_init = 0);
125 Curvedata(const bigint& cc4, const bigint& cc6, int min_on_init);
126 Curvedata(const Curvedata& c);
127 Curvedata(const Curvedata& c, int min_on_init);
128 // nb compiler cannot generate copy because constructor from
129 // curve overrides.
130 // But default assign, destruct suffice
131 void operator=(const Curvedata& c);
132 void minimalize(); // Changes self in situ
factor_discr()133 void factor_discr()
134 {if(!discr_factored){ the_bad_primes=pdivs(discr); discr_factored=1; }}
135 Curvedata minimalize(bigint& u, bigint& r, bigint& s, bigint& t) const;
136 // Self unchanged and returns transformation
137 void transform(const bigint& r, const bigint& s, const bigint& t); // NB u = 1;
138 // the more general case is not implemented here
139 void output(ostream& os) const;
140 void input(istream& is);
141 long get_ntorsion(); // implemented in points.cc
142
getbi(bigint & bb2,bigint & bb4,bigint & bb6,bigint & bb8)143 void getbi(bigint& bb2, bigint& bb4, bigint& bb6, bigint& bb8) const
144 {bb2=b2; bb4=b4; bb6=b6; bb8=b8; }
getci(bigint & cc4,bigint & cc6)145 void getci(bigint& cc4, bigint& cc6) const
146 {cc4=c4; cc6=c6; }
getb2(const Curvedata & c)147 friend inline bigint getb2(const Curvedata& c) {return c.b2; }
getb4(const Curvedata & c)148 friend inline bigint getb4(const Curvedata& c) {return c.b4; }
getb6(const Curvedata & c)149 friend inline bigint getb6(const Curvedata& c) {return c.b6; }
getb8(const Curvedata & c)150 friend inline bigint getb8(const Curvedata& c) {return c.b8; }
getc4(const Curvedata & c)151 friend inline bigint getc4(const Curvedata& c) {return c.c4; }
getc6(const Curvedata & c)152 friend inline bigint getc6(const Curvedata& c) {return c.c6; }
getdiscr(const Curvedata & c)153 friend inline bigint getdiscr(const Curvedata& c) {return c.discr; }
getconncomp(const Curvedata & c)154 friend inline int getconncomp(const Curvedata& c) {return c.conncomp; }
getbad_primes(Curvedata & c)155 friend inline vector<bigint> getbad_primes(Curvedata& c)
156 {
157 if(!c.discr_factored) c.factor_discr();
158 return c.the_bad_primes;
159 }
160 protected:
161 bigint b2 ;
162 bigint b4 ;
163 bigint b6 ;
164 bigint b8 ;
165 bigint c4 ;
166 bigint c6 ;
167 bigint discr ;
168 int minimal_flag; // 0 if .minimalize() has not been called
169 int discr_factored; // 0 if discr has not yet been factored
170 vector<bigint> the_bad_primes; //prime divisors of discriminant
171 int conncomp ; // number of components (1 or 2)
172 long ntorsion; // 0 if .gettorsion() not called
173 } ;
174
175 // function to find "optimal x shift" of a given curve
176 Curvedata opt_x_shift(const Curvedata& C, bigint& k);
177
178 /*
179 //
180 // further derived class for curve, invariants and periods:
181 //
182
183 class CurvedataExtra : public Curvedata{
184 public:
185 CurvedataExtra(const Curvedata&) ;
186 virtual void output(ostream& os) const;
187 void input(istream& is)
188 {cout<<"*** You cannot input a CurvedataExtra -- must be just Curve\n";
189 exit(1); }
190 void getroots(bigfloat& r1, bigfloat& r2, bigfloat& r3) const
191 {r1=roots[0]; r2=roots[1]; r3=roots[2]; }
192 // NB caller should then look at conncomp to see how many are set
193 friend inline bigfloat getperiod(const CurvedataExtra c) {return c.period; }
194 protected:
195 bigfloat roots[3] ; // real two-division points; NB if there's only one,
196 // it is stored in roots[2]
197 bigfloat period ; // smallest real period * conncomp
198
199 } ;
200 */
201
202 //
203 // CurveRed class call Tates algorithm as constructor,
204 // stores the info as member variables
205
206 // class Kodaira_code just holds an int which "codes" the type as follows:
207 // (this coding originally from R.G.E.Pinch)
208 //
209 // Im -> 10*m
210 // I*m -> 10*m+1
211 // I, II, III, IV -> 1, 2, 3, 4
212 // I*, II*. III*, IV* -> 5, 6, 7, 8
213 //
214 class Kodaira_code {
215 public:
216 int code;
217 //
code(k)218 Kodaira_code(int k = 0) : code(k) {;}
Kodaira_code(const Kodaira_code & c)219 Kodaira_code(const Kodaira_code& c) : code(c.code) {;}
220 void operator=(int k) {code=k;}
221 void operator=(const Kodaira_code& c) {code=c.code;}
222 friend ostream& operator<<(ostream& os, const Kodaira_code& c);
223 };
224
225 // utility function for converting Kodaira codes to the Pari coding
226
227 // Kodaira Symbol My coding Pari Coding
228
229 // I0 0 1
230 // I*0 1 -1
231 // Im (m>0) 10*m m+4
232 // I*m (m>0) 10*m+1 -(m+4)
233 // II, III, IV 2, 3, 4 m
234 // II*. III*, IV* 7, 6, 5 -m
235
236 int PariKodairaCode(Kodaira_code Kod);
237
238 class Reduction_type {
239 public:
240 int ord_p_discr;
241 int ord_p_N;
242 int ord_p_j_denom;
243 Kodaira_code Kcode; // NB the constructor makes this from an int
244 int c_p;
245 int local_root_number;
246 //
247 Reduction_type(int opd=0, int opN=0, int opj=0, int kc=1, int cp=1, int rno=0)
ord_p_discr(opd)248 : ord_p_discr(opd), ord_p_N(opN), ord_p_j_denom(opj), Kcode(kc), c_p(cp), local_root_number(rno)
249 {}
250 };
251
252 inline ostream& operator<<(ostream& os, const Reduction_type& R);
253
254
255 class CurveRed : public Curvedata {
256 friend class IsogenyClass;
257 protected:
258 map<bigint,Reduction_type> reduct_array; // maps p -> its reduction type
259 bigint N; //the conductor
260 public:
CurveRed()261 CurveRed() : Curvedata() {N=0;}
262 CurveRed(const Curvedata& E); // construct by Tate's algorithm
263 // arg E need not be minimal, but the reduced form will be
264 ~CurveRed();
265 CurveRed(const CurveRed& E);
266 void operator=(const CurveRed& E);
267 // The full display function is not const, since if called they will
268 // compute and set the local root numbers if necessary
269 void display(ostream& os); // full output
270 void output(ostream& os) const; // just the curvedata and conductor
271
272 private:
273 // functions for setting local root numbers:
274 int neron(long p, int kod); // p = 2 or 3
275 void setLocalRootNumber(const bigint& p);
276 void setLocalRootNumber2();
277 void setLocalRootNumber3();
278 void setLocalRootNumber_not_2_or_3(const bigint& p);
279
280 public:
281 // member access functions:
getbad_primes(const CurveRed & c)282 friend inline vector<bigint> getbad_primes(const CurveRed& c)
283 {return c.the_bad_primes; }
getconductor(const CurveRed & c)284 friend inline bigint getconductor(const CurveRed& c) {return c.N; }
285 friend int getord_p_discr(const CurveRed& c, const bigint& p);
286 friend int getord_p_N(const CurveRed& c, const bigint& p);
287 friend int getord_p_j_denom(const CurveRed& c, const bigint& p);
288 friend int getc_p(const CurveRed& c, const bigint& p);
289 friend int prodcp(const CurveRed& c);
290 friend int LocalRootNumber(CurveRed& c, const bigint& p);
291 friend int GlobalRootNumber(CurveRed& c);
292 friend Kodaira_code getKodaira_code(const CurveRed& c, const bigint& p);
293 // the returned value casts as a character array; to use coded as int,
294 // say declared Kodaira_code Kc, just use public member Kc.code
295 friend bigint Trace_Frob(CurveRed& c, const bigint& p);
296 };
297
298
299 inline ostream& operator<<(ostream& os, const Curve& c)
300 {
301 c.output(os);
302 return os;
303 }
304
305 inline ostream& operator<<(ostream& os, const Curvedata& c)
306 {
307 c.output(os);
308 return os;
309 }
310
311 inline ostream& operator<<(ostream& os, const CurveRed& c)
312 {
313 c.output(os);
314 return os;
315 }
316
317 inline istream& operator>>(istream& is, Curve& c)
318 {
319 c.input(is);
320 return is ;
321 }
322
323 inline istream& operator>>(istream& is, Curvedata& c)
324 {
325 c.input(is);
326 return is ;
327 }
328 //Reads the curve (ai) and computes the rest.
329
GlobalRootNumber(const Curvedata & E)330 inline int GlobalRootNumber(const Curvedata& E)
331 {
332 CurveRed C(E);
333 return GlobalRootNumber(C);
334 }
335
336 // end of file: curve.h
337
338 #endif
339