Sharedwww / merel-stein / ss.gpOpen in CoCalc
Author: William A. Stein
1\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
2\\ ss.gp -- pari-gp v2 program                           \\
3\\                                                       \\
4\\ Date: June 9, 1999                                    \\
5\\                                                       \\
6\\ Author: William A. Stein ([email protected])      \\
7\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
8
9len(v)=matsize(v)[2];
10nrows(v)=matsize(v)[1];
11
12{composite_finitefield(p, f, g,
13    v)=
14\\print("comp p=",p,", f=", f,", g=",g);
15   if(poldegree(f)<=1,return(g));
16   if(poldegree(g)<=1,return(f));
17   v=polcompositum(f*Mod(1,p),g*Mod(1,p));
18\\   if(len(v)>1, print("v = ",v));
19   return(lift(v[1]));
20}
21
22\\ a root of g(x) in Fp[x]/(f(x)).
23{rootin_finitefield(p, f, g,
24    fac)=
25    fac=factorff(g, p, subst(f,x,t));
26\\    print("fac = ",fac);
27    if(poldegree(fac[1,1])!=1,
28       print("ERROR"));
29    -subst(fac[1,1],x,0);
30}
31
32\\ sum n_E/(j-j_E) \in Fpbar(j).
33{fdiv(p,i,sq,
34   ans, f, alp, bet, ratfun1, ratfun2, fac, m, r, n_E, j_E)=
35
36   fac = lift(factormod(sseigen[p,i][1], p));
37   ans = vector(nrows(fac),m,0);
38   for(r=1,nrows(fac),
39     if(fac[r,2]!=1,print("WARNING, fac = ",fac));
40     f = composite_finitefield(p, fac[r,1], ssbasis[p][1]);
41     alp = rootin_finitefield(p, f, fac[r,1]);
42     bet = rootin_finitefield(p, f, ssbasis[p][1]);
43     ratfun1 = 0;   \\ this will be sum n_E/(j-j_E).
44     ratfun2 = 0;
45     for(m=1,len(ssbasis[p][2]),
46       n_E = subst(sseigen[p,i][2][m],x,alp)*Mod(1,p);
47       j_E = subst(ssbasis[p][2][m],x,bet)*Mod(1,p);
48       ratfun1 += n_E/(x-j_E);
49       if(sq==1, ratfun2 += n_E/((x-j_E)^2));
50     );
51     if(sq==1,
52       ans[r] = [subst(f,x,t), lift(lift(ratfun1)),
53                             lift(lift(ratfun2))],
54       ans[r] = [subst(f,x,t), lift(lift(ratfun1))];
55     );
56   );
57   return(ans);
58}
59
60\\ Compute the Fp-rational zeros of the rational function
61\\ g(x) in Fp[t]/f(t).
62{zeros(p, f, g,
63   fac,c,v,i)=
64   ans=[];
65   g=numerator(g);
66   for(j=0,p-1,
67     if(Mod(subst(g,x,j),f)*Mod(1,p)==0,
68        ans=setunion(ans,[j]);
69     )
70   );
71   return(vecsort(eval(ans)));
72}
73
74\\ fdivzeros
75{fdivzeros(p,i,
76   v)=
77   v=fdiv(p,i);
78   for(i=1,len(v),
79     v[i]=[v[i][1],zeros(p,v[i][1],v[i][2])];
80   );
81   return(v);
82}
83
84\\ fdivzeros_table
85{fdivzeros_table(pstart, pstop,
86   p, i, v)=
87   forprime(p=pstart, pstop,
88     i=1;
89     while(type(sseigen[p,i])=="t_VEC",
90        print("rf[",p,",",i,"] = ",fdivzeros(p,i),";");
91        i++;
92     )
93   );
94}
95
96\\ fdiv2zeros
97{fdiv2zeros(p,i,
98   v)=
99   v=fdiv(p,i);
100   for(i=1,len(v),
101     v[i]=[v[i][1],zeros(p,v[i][1],v[i][2])];
102   );
103   return(v);
104}
105
106{fdiv2zeros_table(pstart, pstop,
107   p, i, v)=
108   forprime(p=pstart, pstop,
109     i=1;
110     while(type(sseigen[p,i])=="t_VEC",
111        print("rf[",p,",",i,"] = [",fdiv2zeros(p,i));
112        i++;
113     )
114   );
115}
116
117
118\\ apEj: returns a list of the set of _all_ pairs [j, a_p(E_j)] where
119\\ j lies in F_p and E_j is some elliptic curve of j-invariant
120\\ j. If several curves has the same j-invariant but different
121\\ a_p they will appear on the list.  Note, a_p := p+1 - #E(Fp).
122\\ The algorithm is as stupid as imaginable, but who cares
123\\ since p < 1000.
124{jap(p,
125  ans, a, b, E, cn)=
126\\  print1 ("ja, p=",p,": [");
127  ans=[];
128  cn=floor(p/40)+1;
129  for(a=0,p-1,
130\\    if(a%cn==0,print1("."));
131    for(b=0,p-1,
132      if(poldisc((x^3+a*x+b)*Mod(1,p))!=0,
133\\         print(poldisc((x^3+a*x+b)*Mod(1,p)));
134         E=ellinit([0,0,0,Mod(a,p),Mod(b,p)]);
135         ans = setunion(ans, [[lift(E.j), lift(ellap(E,p))]]);
136      );
137    );
138  );
139  return(vecsort(eval(ans),1));
140}
141
142\\ Returns all j's for which there exists SOME elliptic curve
143\\ over E/Fp of j-invariant j for which ap=1, i.e.,
144\\ |E(Fp)| = p+1-ap = p..
145\\ v = output of jap.
146{jwithapone(v,
147  i, ans)=
148  ans=[];
149  for(i=1,len(v),if(v[i][2]==1,ans=setunion(ans,[v[i][1]])));
150  return(vecsort(eval(ans)));
151}
152
153{jwithapone_table(pstart, pstop,
154  p)=
155  japs=vector(pstop);
156  forprime(p=pstart,pstop,
157    japs[p]=jap(p);
158    print("jap1[",p,"] = ",jwithapone(japs[p]),";")
159  );
160}
161
162
163
164{rflist(p,
165   v, i, j)=
166   i=1;
167   v=[];
168   while(type(rf[p,i])=="t_VEC",
169      for(j=1,len(rf[p,i]),
170         v=setunion(v,rf[p,i][j][2]));
171      i++;
172   );
173   return(eval(v));
174}
175
176{rf_0jap1(pstart,pstop,
177   p, v, w, z)=
178   forprime(p=pstart,pstop,
179     v=Set(rflist(p));
180     w=Set(jap1[p]);
181     z=eval(setintersect(v,w));
182     if(len(z)!=0,
183       print(p, ":  ",v,", ", w,", ", z)
184     );
185   );
186