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 : #include "pari.h"
16 : #include "paripriv.h"
17 :
18 : static const long C6_2[] = {-2038812128, -1962605152, -1609924832, -1360331488,
19 : -1191092320, -1036506592, -941262560, -909783441, -809624672, -654034528,
20 : -460155232, -354945888, -298125728, -277214752, -268382565, -253681713,
21 : -238372640, -234929537, -230390533, -203339808, -192141577, -180402805,
22 : -172848797, -169152193, -164606048, -157502880, -154892817, -151457813,
23 : -138225637, -125036000, -122799257, -114119045, -108565677, -102536928,
24 : -100578105, -97369120, -83484917, -70474733, -69964192, -66459285, -58439008,
25 : -54899360, -53609777, -44012393, -42169248, -41088465, -39328480, -28394585,
26 : -24918112, -19268128, -18628705, -17594720, -14723765, -11868768, -9678933,
27 : -8629885, -7659557, -7202953, -6658208, -5844960, -5557977, -3592593, -3252448,
28 : -3059065, -2754080, -2309472, -2137401, -1267488, -919657, -811053, -698561,
29 : -394273, -319328, -279305, -238049, -220320, -189297, -144352, -94365, -88352,
30 : -53317, -38313, -23968, -12096, -9440, -6137, -3689, -3133, -2592, -1088, -864,
31 : -485, -352, -224, -189, 71, 224, 235, 243, 352, 539, 847, 864, 1088, 2295,
32 : 2592, 4455, 5491, 9440, 12096, 13823, 23968, 40355, 45395, 56511, 82603, 88352,
33 : 107207, 128979, 144352, 170335, 220320, 287199, 319328, 416475, 427275,
34 : 1267488, 1869723, 2057527, 2309472, 2470095, 2754080, 3187107, 3252448,
35 : 4008231, 4342483, 4669487, 4987899, 5371975, 5844960, 6658208, 10487691,
36 : 11713427, 11868768, 12309759, 12960955, 14366403, 16599735, 17594720, 18210383,
37 : 19053387, 19268128, 20816675, 22685563, 24918112, 27839943, 31278555, 33721523,
38 : 34989327, 37619495, 38933811, 39328480, 41806907, 42169248, 43218279, 49457287,
39 : 52707375, 52761375, 54899360, 58439008, 61658315, 65479843, 67448447, 69964192,
40 : 89346807, 97369120, 99286183, 102536928, 104453199, 107206075, 112713363,
41 : 115536367, 121251735, 125036000, 146401127, 153168895, 157502880, 164606048,
42 : 170913915, 182325087, 190150775, 194062851, 203339808, 223692247, 232652655,
43 : 238372640, 256093595, 260871111, 275847579, 277214752, 296788987, 298125728,
44 : 318661163, 392275872, 535445792, 567723168, 636117920, 830651680, 918400032,
45 : 1061281440, 1218263328, 1331079200, 1513036448, 1780447392, 1851892768};
46 :
47 : static const long C4_2[] = {1607872, 1567552, 1373632, 1227712, 1123648, 1024192,
48 : 960448, 938913, 868672, 753472, 596032, 501312, 446272, 425152, 416073, 400737,
49 : 384448, 380737, 375817, 345792, 332977, 319273, 310297, 305857, 300352, 291648,
50 : 288417, 284137, 267337, 250048, 247057, 235273, 227577, 219072, 216273, 211648,
51 : 191017, 170617, 169792, 164073, 150592, 144448, 142177, 124657, 121152, 119073,
52 : 115648, 93073, 85312, 71872, 70273, 67648, 60073, 52032, 45417, 42073, 38857,
53 : 37297, 35392, 32448, 31377, 23457, 21952, 21073, 19648, 17472, 16593, 11712,
54 : 9457, 8697, 7873, 5377, 4672, 4273, 3841, 3648, 3297, 2752, 2073, 1984, 1417,
55 : 1137, 832, 528, 448, 337, 241, 217, 192, 112, 96, 73, 64, -32, -39, -47, -32,
56 : -23, 57, 64, 73, 97, 96, 112, 177, 192, 273, 313, 448, 528, 577, 832, 1177,
57 : 1273, 1473, 1897, 1984, 2257, 2553, 2752, 3073, 3648, 4353, 4672, 5577, 5673,
58 : 11712, 15177, 16177, 17472, 18273, 19648, 21657, 21952, 25233, 26617, 27937,
59 : 29193, 30673, 32448, 35392, 47913, 51577, 52032, 53313, 55177, 59097, 65073,
60 : 67648, 69217, 71337, 71872, 75673, 80137, 85312, 91857, 99273, 104377, 106977,
61 : 112273, 114873, 115648, 120457, 121152, 123153, 134737, 140577, 140673, 144448,
62 : 150592, 156073, 162457, 165697, 169792, 199857, 211648, 214417, 219072, 221793,
63 : 225673, 233337, 237217, 244977, 250048, 277777, 286273, 291648, 300352, 307977,
64 : 321537, 330673, 335193, 345792, 368497, 378273, 384448, 403273, 408273, 423753,
65 : 425152, 444937, 446272, 466537, 535872, 659392, 685632, 739648, 883648, 944832,
66 : 1040448, 1140672, 1210048, 1317952, 1468992, 1508032};
67 :
68 : static const long C6_2a[] = {2674143008UL, 1985472243UL, 1095028593UL, 3504837745UL, 4290570801UL, 3953653345UL, 4109103319UL, 2741053627UL};
69 : static const long C6_2b[] = {0, 2, -3, -56, -65, -731, 1106, 1777};
70 : static const long C4_2b[] = {1926592, 4817977, 5803233, 39049953, 43151713, 214593153, 282744177, 387735433};
71 :
72 : const long C6_3[] = {8, -181, -216, -253, -568, -1917, -2008, -11341, -20341, -54648, -105517, -130213, -243928, -280792, -1723861, -4906117, -7628536, -47293021, -64288216, -147598093, -243578341, -309548728, -481100248, -888576373, -1072562392};
73 : const long C4_3[] = {-32, -23, 0, 25, 64, 153, 160, 505, 745, 1440, 2233, 2569, 3904, 4288, 14377, 28873, 38752, 130777, 160480, 279289,
74 : 390025, 457600, 613984, 924265, 1047808};
75 :
76 : const long C6_3a[] = {2563903117UL, 457618317UL, 2023533717UL, 952150165UL, 2735598328UL, 2595802584UL, 769886424UL, 3701930360UL, 4283905637UL, 906440629UL, 621617725UL, 4076173245UL, 836619493UL, 3386456997UL};
77 : const long C6_3b[] = {0, -1, -1, -3, -3, -4, -7, -8, -11, -132, -171, -193, -888, -4366};
78 : const long C4_3b[] = {1873273, 2826745, 3417769, 5763625, 6248800, 7312864, 9833152, 11315104, 13847305, 68572777, 81448345, 88531609, 244143625, 705907849};
79 :
80 : static long
81 899234 : search(long i, const long T[], long n)
82 : {
83 899234 : long mmin = 0, mmax = n-1;
84 : for(;;)
85 4230037 : {
86 5129271 : long m = (mmin + mmax)>>1;
87 5129271 : if (T[m]==i) return m;
88 5122236 : if (T[m]<i) mmin = m+1;
89 5122236 : if (T[m]>i) mmax = m-1;
90 5122236 : if (mmin>mmax) return -1;
91 : }
92 : }
93 :
94 : static long
95 455350 : ellmanintable_i(GEN E)
96 : {
97 455350 : GEN G = ellglobalred(E), N = gel(G,1);
98 455350 : GEN u = gmael(G,2,1), C4 = ell_get_c4(E), C6 = ell_get_c6(E);
99 455350 : if (typ(u) != t_INT || !is_pm1(u))
100 : {
101 0 : C4 = gmul(C4, gpowgs(u, -4));
102 0 : C6 = gmul(C6, gpowgs(u, -6));
103 : }
104 455350 : if (cmpiu(N, 500000) > 0)
105 : {
106 0 : GEN M = gel(ellisomat(E,0,1),2);
107 0 : if (lg(M)==2) return 1; /* Manin conjecture */
108 0 : return ugcdiu(ZV_lcm(gel(M,1)),6); /* Watkins conjecture */
109 : }
110 455350 : if (signe(C6)==0)
111 : {
112 798 : if (equaliu(absi(C4),48)) return 2;
113 : }
114 454552 : else if (expi(C6)<31)
115 : {
116 365848 : long i, c6 = itos(C6), c4 = itos_or_0(C4);
117 365848 : if (c6==-152 && c4 == 16) return 5;
118 365834 : if ((c6==-161 && c4 == 1) || (c6==-81 && c4 == 33)) return 4;
119 365799 : i = search(c6, C6_2, sizeof(C6_2)/sizeof(*C6_2));
120 365799 : if (i>=0 && equalis(C4,C4_2[i])) return 2;
121 364966 : i = search(c4, C4_3, sizeof(C4_3)/sizeof(*C4_3));
122 364966 : if (i>=0 && equalis(C6,C6_3[i])) return 3;
123 88704 : } else if (expi(C4)<31)
124 : {
125 84245 : long i, c4 = itos(C4);
126 84245 : i = search(c4, C4_2b, sizeof(C4_2b)/sizeof(*C4_2b));
127 84245 : if (i>=0)
128 : {
129 21 : GEN C6i = C6_2b[i] >=0 ? uu32toi(C6_2b[i],C6_2a[i]) : uu32toineg(-C6_2b[i],C6_2a[i]);
130 21 : if (equalii(C6, C6i)) return 2;
131 : }
132 84224 : i = search(c4, C4_3b, sizeof(C4_3b)/sizeof(*C4_3b));
133 84224 : if (i>=0)
134 : {
135 98 : GEN C6i = C6_3b[i] > 0 ? uu32toi(C6_3b[i],C6_3a[i]) : uu32toineg(-C6_3b[i],C6_3a[i]);
136 98 : if (equalii(C6, C6i)) return 3;
137 : }
138 : } else
139 : {
140 4459 : if ((equalii(C4,uu32toi(1,204887049UL)) && equalii(C6,uu32toineg(70280,4219266533UL)))
141 4452 : || (equalii(C4,uu32toi(2433, 2015761857UL)) && equalii(C6,addii(int2n(64),uu32toi(3572205093,952187231UL)))))
142 14 : return 3;
143 : }
144 454055 : return 1;
145 : }
146 :
147 : long
148 455350 : ellmanintable(GEN E)
149 455350 : { pari_sp av = avma; return gc_long(av, ellmanintable_i(E)); }
|
