1 /* Copyright (C) 2005 The PARI group.
2
3 This file is part of the PARI/GP package.
4
5 PARI/GP is free software; you can redistribute it and/or modify it under the
6 terms of the GNU General Public License as published by the Free Software
7 Foundation; either version 2 of the License, or (at your option) any later
8 version. It is distributed in the hope that it will be useful, but WITHOUT
9 ANY WARRANTY WHATSOEVER.
10
11 Check the License for details. You should have received a copy of it, along
12 with the package; see the file 'COPYING'. If not, write to the Free Software
13 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
14
15 /********************************************************************/
16 /** **/
17 /** INTERFACE TO JOHN CREMONA ELLIPTIC CURVES DATABASE **/
18 /** **/
19 /********************************************************************/
20 #include "pari.h"
21 #include "paripriv.h"
22
23 static long
strtoclass(const char * s)24 strtoclass(const char *s)
25 {
26 long c=0;
27 while (*s && *s<='9') s++;
28 if (!*s) return -1;
29 while ('a'<=*s && *s<='z') c = 26*c + *(s++)-'a';
30 return c;
31 }
32
33 /*Take a curve name like "100a2" and set
34 * f to the conductor, (100)
35 * c to the isogeny class (in base 26), ("a" or 0)
36 * i to the curve index (2).
37 * return 0 if parse error. */
38 static int
ellparsename(const char * s,long * f,long * c,long * i)39 ellparsename(const char *s, long *f, long *c, long *i)
40 {
41 long j;
42 *f=-1; *c=-1; *i=-1;
43 if (*s<'0' || *s>'9') return 0;
44 *f=0;
45 for (j=0;j<10 && '0'<=*s && *s<='9';j++)
46 *f=10**f+*(s++)-'0';
47 if (j==10) {*f=-1; return 0;}
48 if (*s<'a' || *s>'z') return !*s;
49 *c=0;
50 for (j=0; j<7 && 'a'<=*s && *s<='z';j++)
51 *c=26**c+*(s++)-'a';
52 if (j==7) {*c=-1; return 0;}
53 if (*s<'0' || *s>'9') return !*s;
54 *i=0;
55 for (j=0; j<10 && '0'<=*s && *s<='9';j++)
56 *i=10**i+*(s++)-'0';
57 if (j==10) {*i=-1; return 0;}
58 return !*s;
59 }
60
61 /* Take an integer and convert it to base 26 */
62 static GEN
ellrecode(long x)63 ellrecode(long x)
64 {
65 GEN str;
66 char *s;
67 long d = 0, n = x;
68 do { d++; n /= 26; } while (n);
69 str = cgetg(nchar2nlong(d+1)+1, t_STR);
70 s = GSTR(str); s[d] = 0;
71 n = x;
72 do { s[--d] = n%26 + 'a'; n /= 26; } while (n);
73 return str;
74 }
75
76 GEN
ellconvertname(GEN n)77 ellconvertname(GEN n)
78 {
79 switch(typ(n))
80 {
81 case t_STR:
82 {
83 long f,i,c;
84 if (!ellparsename(GSTR(n),&f,&c,&i)) pari_err_TYPE("ellconvertname", n);
85 if (f<0 || c<0 || i<0)
86 pari_err_TYPE("ellconvertname [incomplete name]", n);
87 return mkvec3s(f,c,i);
88 }
89 case t_VEC:
90 if (lg(n)==4)
91 {
92 pari_sp av = avma;
93 GEN f=gel(n,1), c=gel(n,2), s=gel(n,3);
94 if (typ(f)!=t_INT || typ(c)!=t_INT || typ(s)!=t_INT)
95 pari_err_TYPE("ellconvertname",n);
96 return gerepilecopy(av, shallowconcat1(mkvec3(f, ellrecode(itos(c)), s)));
97 }
98 /*fall through*/
99 }
100 pari_err_TYPE("ellconvertname",n);
101 return NULL; /*LCOV_EXCL_LINE*/
102 }
103
104 static GEN
ellcondfile(long f)105 ellcondfile(long f)
106 {
107 pari_sp av = avma;
108 long n = f / 1000;
109 char *s = stack_malloc(strlen(pari_datadir) + 12 + 20 + 1);
110 pariFILE *F;
111 GEN V;
112 sprintf(s, "%s/elldata/ell%ld", pari_datadir, n);
113 F = pari_fopengz(s);
114 if (!F) pari_err_FILE("elldata file",s);
115 set_avma(av);
116 V = gp_read_stream(F->file);
117 if (!V || typ(V)!=t_VEC ) pari_err_FILE("elldata file [read]",s);
118 pari_fclose(F); return V;
119 }
120
121 /* return the vector of all curves of conductor f */
cmpi1(GEN x,GEN v)122 static int cmpi1(GEN x, GEN v) { return cmpii(x, gel(v,1)); }
123 static GEN
ellcondlist(long f)124 ellcondlist(long f)
125 {
126 pari_sp av = avma;
127 GEN V = ellcondfile(f);
128 long i = tablesearch(V, utoipos(f), &cmpi1);
129 if (i)
130 {
131 GEN v = gel(V,i);
132 return vecslice(v,2, lg(v)-1);
133 }
134 set_avma(av); return cgetg(1,t_VEC);
135 }
136
137 static GEN
ellsearchbyname(GEN V,char * name)138 ellsearchbyname(GEN V, char *name)
139 {
140 GEN x;
141 long j;
142 for (j=1; j<lg(V); j++)
143 {
144 GEN v = gel(V,j);
145 if (!strcmp(GSTR(gel(v,1)), name)) return v;
146 }
147 x = strtoGENstr(name);
148 pari_err_DOMAIN("ellsearchbyname", "name", "=", x,x);
149 return NULL;/*LCOV_EXCL_LINE*/
150 }
151
152 static GEN
ellsearchbyclass(GEN V,long c)153 ellsearchbyclass(GEN V, long c)
154 {
155 long i,j,n;
156 GEN res;
157 for (n=0,j=1; j<lg(V); j++)
158 if (strtoclass(GSTR(gmael(V,j,1)))==c) n++;
159 res = cgetg(n+1,t_VEC);
160 for (i=1,j=1; j<lg(V); j++)
161 if (strtoclass(GSTR(gmael(V,j,1)))==c) res[i++] = V[j];
162 return res;
163 }
164
165 GEN
ellsearch(GEN A)166 ellsearch(GEN A)
167 {
168 pari_sp av = avma;
169 long f, c, i;
170 GEN V;
171 if (typ(A)==t_INT) { f = itos(A); c = i = -1; }
172 else if (typ(A)==t_VEC)
173 {
174 long l = lg(A)-1;
175 if (l<1 || l>3)
176 pari_err_TYPE("ellsearch",A);
177 f = gtos(gel(A,1));
178 c = l>=2 ? gtos(gel(A,2)): -1;
179 i = l>=3 ? gtos(gel(A,3)): -1;
180 if (l>=3) A = ellconvertname(A);
181 }
182 else if (typ(A)==t_STR) {
183 if (!ellparsename(GSTR(A),&f,&c,&i))
184 pari_err_TYPE("ellsearch",A);
185 } else {
186 pari_err_TYPE("ellsearch",A);
187 return NULL;/*LCOV_EXCL_LINE*/
188 }
189 if (f <= 0) pari_err_DOMAIN("ellsearch", "conductor", "<=", gen_0,stoi(f));
190 V = ellcondlist(f);
191 if (c >= 0)
192 V = (i < 0)? ellsearchbyclass(V,c): ellsearchbyname(V, GSTR(A));
193 return gerepilecopy(av, V);
194 }
195
196 GEN
ellsearchcurve(GEN name)197 ellsearchcurve(GEN name)
198 {
199 pari_sp ltop=avma;
200 long f, c, i;
201 if (!ellparsename(GSTR(name),&f,&c,&i)) pari_err_TYPE("ellsearch",name);
202 if (f<0 || c<0 || i<0) pari_err_TYPE("ellsearch [incomplete name]", name);
203 return gerepilecopy(ltop, ellsearchbyname(ellcondlist(f), GSTR(name)));
204 }
205
206 GEN
ellidentify(GEN E)207 ellidentify(GEN E)
208 {
209 pari_sp ltop=avma;
210 long j;
211 GEN V, M, G, N;
212 checkell_Q(E);
213 G = ellglobalred(E); N = gel(G,1);
214 V = ellcondlist(itos(N));
215 M = ellchangecurve(vecslice(E,1,5),gel(G,2));
216 for (j=1; j<lg(V); j++)
217 if (ZV_equal(gmael(V,j,2), M))
218 return gerepilecopy(ltop, mkvec2(gel(V,j),gel(G,2)));
219 pari_err_BUG("ellidentify [missing curve]");
220 return NULL;/*LCOV_EXCL_LINE*/
221 }
222
223 GEN
elldatagenerators(GEN E)224 elldatagenerators(GEN E)
225 {
226 pari_sp ltop=avma;
227 GEN V=ellidentify(E);
228 GEN gens=gmael(V,1,3);
229 GEN W=ellchangepointinv(gens,gel(V,2));
230 return gerepileupto(ltop,W);
231 }
232
233 void
forell(void * E,long call (void *,GEN),long a,long b,long flag)234 forell(void *E, long call(void*, GEN), long a, long b, long flag)
235 {
236 long ca=a/1000, cb=b/1000;
237 long i, j, k;
238
239 if (ca < 0) ca = 0;
240 for(i=ca; i<=cb; i++)
241 {
242 pari_sp ltop=avma;
243 GEN V = ellcondfile(i*1000);
244 for (j=1; j<lg(V); j++)
245 {
246 GEN ells = gel(V,j);
247 long cond= itos(gel(ells,1));
248
249 if (i==ca && cond<a) continue;
250 if (i==cb && cond>b) break;
251 for(k=2; k<lg(ells); k++)
252 {
253 GEN e = gel(ells,k);
254 if (flag) {
255 GEN n = gel(e,1); /* Cremona label */
256 long f, c, x;
257 if (!ellparsename(GSTR(n),&f,&c,&x))
258 pari_err_TYPE("ellconvertname", n);
259 if (x != 1) continue;
260 }
261 if (call(E, e)) return;
262 }
263 }
264 set_avma(ltop);
265 }
266 }
267
268 void
forell0(long a,long b,GEN code,long flag)269 forell0(long a, long b, GEN code, long flag)
270 { EXPRVOID_WRAP(code, forell(EXPR_ARGVOID, a, b, flag)) }
271