/
step4-findMW.txt
123 lines (113 loc) · 3.47 KB
/
step4-findMW.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// This magma script takes as input an integer k and then does 3-descents
// (via ThreeDescentByIsogeny) on E_k, E_4k, and E_k^3 to search for points.
// Generators are written to the file gens.txt
// Values of k for which generators are not found are written to gens.txt
if (not assigned k) then
printf "This script requires a command line argument.\n";
printf "The usage is magma k:=7057 findMW.txt\n";
else
k := StringToInteger(k,10);
end if;
output := "";
superbadk := false;
// None of the elliptic curves or their twists have a rational point of order 3
// since there are no k's in badk that are squares.
printf "Working on k = %o.\n",k;
Elist := [ EllipticCurve([0,0,0,0,k]), EllipticCurve([0,0,0,0,4*k]),
EllipticCurve([0,0,0,0,k^3]) ];
covs := <>;
mps := <>;
ranklist := [];
t := Cputime();
done := false;
for i in [1..#Elist] do
E := Elist[i];
t2 := Cputime();
printf "Doing descent on curve %o.\n",i;
r1, r2 := ThreeDescentByIsogeny(E);
Append(~covs,r1);
Append(~mps,r2);
rk := Valuation(2*#r1+1,3);
Append(~ranklist,rk);
printf "Rank upper bound for E_k was %o. Time was %o.\n",rk,Cputime(t2);
if (rk eq 0) then
done := true;
break;
end if;
end for;
// Reorder lists based on rank.
// This increases the chances we do MW-sieve on a low rank curve.
if (done eq false) then
p := Sym(3)!1;
Sort(~ranklist,~p);
Elist := [ Elist[Image(p,i)] : i in [1..3]];
covs := < covs[Image(p,i)] : i in [1..3]>;
mps := < mps[Image(p,i)] : i in [1..3]>;
end if;
curdesc := Cputime(t);
printf "Descent time %o sec.\n",curdesc;
t := Cputime();
bound := 10000;
mult := 2;
while (done eq false) do
for i in [1..#Elist] do
if (done eq false) then
printf "Point searching on curve %o to bound %o.\n",i,bound;
Epts := [];
for j in [1..#covs[i]] do
ps := PointSearch(covs[i][j],bound : OnlyOne := true);
for p in ps do
comp := Components(mps[i][j]);
Append(~Epts,comp[2](Eltseq(comp[1](p))));
end for;
end for;
rb := ReducedBasis(Epts);
printf "%o points found on curve %o. Rank they generate is %o.\n",#Epts,i,#rb;
if #rb eq ranklist[i] then
done := true;
printf "We found %o independent points on curve %o.\n",#rb,i;
rb2 := Saturation(rb,100);
HP := HeightPairingMatrix(rb2);
A, B := LLLGram(HP);
newgens := [ &+[ B[i][j]*rb2[j] : j in [1..#rb2]] : i in [1..#rb2]];
printf "Generators are %o.\n",newgens;
const := aInvariants(Elist[i])[5];
ind := 0;
if (const eq k) then
ind := 1;
end if;
if (const eq 4*k) then
ind := 2;
end if;
if (const eq k^3) then
ind := 3;
end if;
end if;
end if;
end for;
if (done eq false) then
bound := bound*mult;
if (bound gt 500000) then
done := true;
superbadk := true;
end if;
end if;
end while;
cursearch := Cputime(t);
printf "Point search time %o sec.\n",cursearch;
if (not assigned ind) then
ind := 0;
end if;
if (not assigned newgens) then
newgens := 0;
end if;
if (superbadk eq true) then
printf "The value k = %o is bad. We didn't find enough points.\n",k;
PrintFile("superbadk.txt",Sprintf("%o,",k));
else
if (rk gt 0) then
output := Sprintf("%o,",<k,ind,[ Eltseq(newgens[i]) : i in [1..#newgens]],curdesc,cursearch>);
PrintFile("gens.txt",output);
end if;
end if;
quit;