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
9
len(v)=matsize(v)[2];
10
nrows(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