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