Line data Source code
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
24 108 : strtoclass(const char *s)
25 : {
26 108 : long c=0;
27 324 : while (*s && *s<='9') s++;
28 108 : if (!*s) return -1;
29 216 : while ('a'<=*s && *s<='z') c = 26*c + *(s++)-'a';
30 108 : 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
39 453750 : ellparsename(const char *s, long *f, long *c, long *i)
40 : {
41 : long j;
42 453750 : *f=-1; *c=-1; *i=-1;
43 453750 : if (*s<'0' || *s>'9') return 0;
44 453744 : *f=0;
45 2164256 : for (j=0;j<10 && '0'<=*s && *s<='9';j++)
46 1710512 : *f=10**f+*(s++)-'0';
47 453744 : if (j==10) {*f=-1; return 0;}
48 453744 : if (*s<'a' || *s>'z') return !*s;
49 453738 : *c=0;
50 930582 : for (j=0; j<7 && 'a'<=*s && *s<='z';j++)
51 476844 : *c=26**c+*(s++)-'a';
52 453738 : if (j==7) {*c=-1; return 0;}
53 453738 : if (*s<'0' || *s>'9') return !*s;
54 453726 : *i=0;
55 907452 : for (j=0; j<10 && '0'<=*s && *s<='9';j++)
56 453726 : *i=10**i+*(s++)-'0';
57 453726 : if (j==10) {*i=-1; return 0;}
58 453726 : return !*s;
59 : }
60 :
61 : /* Take an integer and convert it to base 26 */
62 : static GEN
63 12 : ellrecode(long x)
64 : {
65 : GEN str;
66 : char *s;
67 12 : long d = 0, n = x;
68 12 : do { d++; n /= 26; } while (n);
69 12 : str = cgetg(nchar2nlong(d+1)+1, t_STR);
70 12 : s = GSTR(str); s[d] = 0;
71 12 : n = x;
72 12 : do { s[--d] = n%26 + 'a'; n /= 26; } while (n);
73 12 : return str;
74 : }
75 :
76 : GEN
77 449490 : ellconvertname(GEN n)
78 : {
79 449490 : switch(typ(n))
80 : {
81 449478 : case t_STR:
82 : {
83 : long f,i,c;
84 449478 : if (!ellparsename(GSTR(n),&f,&c,&i)) pari_err_TYPE("ellconvertname", n);
85 449478 : if (f<0 || c<0 || i<0)
86 0 : pari_err_TYPE("ellconvertname [incomplete name]", n);
87 449478 : return mkvec3s(f,c,i);
88 : }
89 12 : case t_VEC:
90 12 : if (lg(n)==4)
91 : {
92 12 : pari_sp av = avma;
93 12 : GEN f=gel(n,1), c=gel(n,2), s=gel(n,3);
94 12 : if (typ(f)!=t_INT || typ(c)!=t_INT || typ(s)!=t_INT)
95 0 : pari_err_TYPE("ellconvertname",n);
96 12 : return gc_GEN(av, shallowconcat1(mkvec3(f, ellrecode(itos(c)), s)));
97 : }
98 : /*fall through*/
99 : }
100 0 : pari_err_TYPE("ellconvertname",n);
101 : return NULL; /*LCOV_EXCL_LINE*/
102 : }
103 :
104 : THREAD GEN ellcondfile_cache;
105 : THREAD long ellcondfile_cache_cond;
106 :
107 : void
108 1488 : pari_init_ellcondfile(void)
109 : {
110 1488 : ellcondfile_cache = NULL;
111 1488 : ellcondfile_cache_cond = -1;
112 1488 : }
113 :
114 : static GEN
115 1109 : ellcondfile(long n)
116 : {
117 1109 : if (ellcondfile_cache_cond >= 0 && n == ellcondfile_cache_cond)
118 624 : return gcopy(ellcondfile_cache);
119 : else
120 : {
121 485 : pari_sp av = avma;
122 : pariFILE *F;
123 : GEN V;
124 485 : char *s = stack_sprintf("%s/elldata/ell%ld", pari_datadir, n);
125 485 : F = pari_fopengz(s);
126 485 : if (!F) pari_err_FILE("elldata file",s);
127 485 : set_avma(av);
128 485 : V = gp_read_stream(F->file);
129 485 : if (!V || typ(V)!=t_VEC ) pari_err_FILE("elldata file [read]",s);
130 485 : ellcondfile_cache_cond = -1; /* disable cache until update */
131 485 : if (ellcondfile_cache) gunclone(ellcondfile_cache);
132 485 : ellcondfile_cache = gclone(V);
133 485 : ellcondfile_cache_cond = n; /* re-enable cache */
134 485 : pari_fclose(F); return V;
135 : }
136 : }
137 :
138 : /* return the vector of all curves of conductor f */
139 8106 : static int cmpi1(GEN x, GEN v) { return cmpii(x, gel(v,1)); }
140 : static GEN
141 936 : ellcondlist(long f)
142 : {
143 936 : pari_sp av = avma;
144 936 : GEN V = ellcondfile(f/1000);
145 936 : long i = tablesearch(V, utoipos(f), &cmpi1);
146 936 : if (i)
147 : {
148 936 : GEN v = gel(V,i);
149 936 : return vecslice(v,2, lg(v)-1);
150 : }
151 0 : retgc_const(av, cgetg(1, t_VEC));
152 : }
153 :
154 : static GEN
155 888 : ellsearchbyname(GEN V, char *name)
156 : {
157 : GEN x;
158 : long j;
159 4344 : for (j=1; j<lg(V); j++)
160 : {
161 4344 : GEN v = gel(V,j);
162 4344 : if (!strcmp(GSTR(gel(v,1)), name)) return v;
163 : }
164 0 : x = strtoGENstr(name);
165 0 : pari_err_DOMAIN("ellsearchbyname", "name", "=", x,x);
166 : return NULL;/*LCOV_EXCL_LINE*/
167 : }
168 :
169 : static GEN
170 18 : ellsearchbyclass(GEN V, long c)
171 : {
172 : long i,j,n;
173 : GEN res;
174 72 : for (n=0,j=1; j<lg(V); j++)
175 54 : if (strtoclass(GSTR(gmael(V,j,1)))==c) n++;
176 18 : res = cgetg(n+1,t_VEC);
177 72 : for (i=1,j=1; j<lg(V); j++)
178 54 : if (strtoclass(GSTR(gmael(V,j,1)))==c) res[i++] = V[j];
179 18 : return res;
180 : }
181 :
182 : GEN
183 72 : ellsearch(GEN A)
184 : {
185 72 : pari_sp av = avma;
186 : long f, c, i;
187 : GEN V;
188 72 : if (typ(A)==t_INT) { f = itos(A); c = i = -1; }
189 66 : else if (typ(A)==t_VEC)
190 : {
191 30 : long l = lg(A)-1;
192 30 : if (l<1 || l>3)
193 6 : pari_err_TYPE("ellsearch",A);
194 24 : f = gtos(gel(A,1));
195 24 : c = l>=2 ? gtos(gel(A,2)): -1;
196 24 : i = l>=3 ? gtos(gel(A,3)): -1;
197 24 : if (l>=3) A = ellconvertname(A);
198 : }
199 36 : else if (typ(A)==t_STR) {
200 30 : if (!ellparsename(GSTR(A),&f,&c,&i))
201 6 : pari_err_TYPE("ellsearch",A);
202 : } else {
203 6 : pari_err_TYPE("ellsearch",A);
204 : return NULL;/*LCOV_EXCL_LINE*/
205 : }
206 54 : if (f <= 0) pari_err_DOMAIN("ellsearch", "conductor", "<=", gen_0,stoi(f));
207 48 : V = ellcondlist(f);
208 48 : if (c >= 0)
209 30 : V = (i < 0)? ellsearchbyclass(V,c): ellsearchbyname(V, GSTR(A));
210 48 : return gc_GEN(av, V);
211 : }
212 :
213 : GEN
214 876 : ellsearchcurve(GEN name)
215 : {
216 876 : pari_sp ltop=avma;
217 : long f, c, i;
218 876 : if (!ellparsename(GSTR(name),&f,&c,&i)) pari_err_TYPE("ellsearch",name);
219 876 : if (f<0 || c<0 || i<0) pari_err_TYPE("ellsearch [incomplete name]", name);
220 876 : return gc_GEN(ltop, ellsearchbyname(ellcondlist(f), GSTR(name)));
221 : }
222 :
223 : GEN
224 18 : ellidentify(GEN E)
225 : {
226 18 : pari_sp ltop=avma;
227 : long j;
228 : GEN V, M, G, N;
229 18 : checkell_Q(E);
230 12 : G = ellglobalred(E); N = gel(G,1);
231 12 : V = ellcondlist(itos(N));
232 12 : M = ellchangecurve(vecslice(E,1,5),gel(G,2));
233 12 : for (j=1; j<lg(V); j++)
234 12 : if (ZV_equal(gmael(V,j,2), M))
235 12 : return gc_GEN(ltop, mkvec2(gel(V,j),gel(G,2)));
236 0 : pari_err_BUG("ellidentify [missing curve]");
237 : return NULL;/*LCOV_EXCL_LINE*/
238 : }
239 :
240 : GEN
241 6 : elldatagenerators(GEN E)
242 : {
243 6 : pari_sp ltop=avma;
244 6 : GEN V=ellidentify(E);
245 6 : GEN gens=gmael(V,1,3);
246 6 : GEN W=ellchangepointinv(gens,gel(V,2));
247 6 : return gc_upto(ltop,W);
248 : }
249 :
250 : void
251 47 : forell(void *E, long call(void*, GEN), long a, long b, long flag)
252 : {
253 47 : long ca=a/1000, cb=b/1000;
254 : long i, j, k;
255 :
256 47 : if (ca < 0) ca = 0;
257 220 : for(i=ca; i<=cb; i++)
258 : {
259 173 : pari_sp ltop=avma;
260 173 : GEN V = ellcondfile(i);
261 90874 : for (j=1; j<lg(V); j++)
262 : {
263 90742 : GEN ells = gel(V,j);
264 90742 : long cond= itos(gel(ells,1));
265 :
266 90742 : if (i==ca && cond<a) continue;
267 90742 : if (i==cb && cond>b) break;
268 935339 : for(k=2; k<lg(ells); k++)
269 : {
270 844638 : GEN e = gel(ells,k);
271 844638 : if (flag) {
272 3366 : GEN n = gel(e,1); /* Cremona label */
273 : long f, c, x;
274 3366 : if (!ellparsename(GSTR(n),&f,&c,&x))
275 0 : pari_err_TYPE("ellconvertname", n);
276 3366 : if (x != 1) continue;
277 : }
278 842295 : if (call(E, e)) return;
279 : }
280 : }
281 173 : set_avma(ltop);
282 : }
283 : }
284 :
285 : void
286 47 : forell0(long a, long b, GEN code, long flag)
287 47 : { EXPRVOID_WRAP(code, forell(EXPR_ARGVOID, a, b, flag)) }
|
