Line data Source code
1 : /* Copyright (C) 2013 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 : #define DEBUGLEVEL DEBUGLEVEL_fflog
19 :
20 : /* Let [ be the following order on Fp: 0 [ p-1 [ 1 [ p-2 [ 2 .. [ p\2
21 : and [[ the lexicographic extension of [ to Fp[T]. Compute the
22 : isomorphism (Fp[X], [[) -> (N,<) on P */
23 :
24 : static long
25 392270 : Flx_cindex(GEN P, ulong p)
26 : {
27 392270 : long d = degpol(P), i;
28 392270 : ulong s = 0, p2 = (p-1)>>1;
29 1783088 : for (i = 0; i <= d; ++i)
30 : {
31 1390818 : ulong x = P[d-i+2];
32 1390818 : if (x<=p2) x = 2*x; else x = 1+2*(p-1-x);
33 1390818 : s = p*s+x;
34 : }
35 392270 : return s;
36 : }
37 :
38 : /* Compute the polynomial immediately after t for the [[ order */
39 :
40 : static void
41 435067 : Flx_cnext(GEN t, ulong p)
42 : {
43 : long i;
44 435067 : long p2 = p>>1;
45 557094 : for(i=2;;i++)
46 557094 : if (t[i]==p2)
47 122027 : t[i]=0;
48 : else
49 : {
50 435067 : t[i] = t[i]<p2 ? p-1-t[i]: p-t[i];
51 435067 : break;
52 : }
53 435067 : }
54 :
55 : static int
56 28 : has_deg1_auto(GEN T, ulong p, ulong pi)
57 : {
58 28 : long i, n = degpol(T);
59 28 : GEN a = polx_Flx(get_Flx_var(T));
60 672 : for (i=1; i<n; i++)
61 : {
62 644 : a = Flxq_powu_pre(a, p, T, p, pi);
63 644 : if (degpol(a)==1) return 1;
64 : }
65 28 : return 0;
66 : }
67 :
68 : static void
69 1057 : smallirred_Flx_next(GEN a, long p, ulong pi)
70 : {
71 : do
72 : {
73 : long i;
74 1449 : for(i=2;;i++)
75 1449 : if (++a[i]==p) a[i]=0;
76 1057 : else break;
77 1057 : } while (!Flx_is_irred(a, p) || has_deg1_auto(a,p,pi) );
78 28 : }
79 :
80 : /* Avoid automorphisms of degree 1 */
81 : static GEN
82 28 : smallirred_Flx(long p, ulong n, long sv, ulong pi)
83 : {
84 28 : GEN a = zero_zv(n+2);
85 28 : a[1] = sv; a[3] = 1; a[n+2] = 1;
86 28 : smallirred_Flx_next(a, p, pi);
87 28 : return a;
88 : }
89 :
90 : struct Flxq_log_rel
91 : {
92 : long nbrel;
93 : GEN rel;
94 : long nb;
95 : long r, off, nbmax, nbexp;
96 : ulong nbtest;
97 : };
98 :
99 : static GEN
100 4643 : cindex_Flx(long c, long d, ulong p, long v)
101 : {
102 4643 : GEN P = cgetg(d+3, t_VECSMALL);
103 : long i;
104 4643 : P[1] = v;
105 31664 : for (i = 0; i <= d; ++i)
106 : {
107 27021 : ulong x = c%p;
108 27021 : P[i+2] = (x&1) ? p-1-(x>>1) : x>>1;
109 27021 : c/=p;
110 : }
111 4643 : return Flx_renormalize(P, d+3);
112 : }
113 :
114 : static GEN
115 11216 : factorel(GEN h, ulong p)
116 : {
117 11216 : GEN F = Flx_factor(h, p);
118 11216 : GEN F1 = gel(F, 1), F2 = gel(F, 2);
119 11216 : long i, l1 = lg(F1)-1;
120 11216 : GEN p2 = cgetg(l1+1, t_VECSMALL);
121 11216 : GEN e2 = cgetg(l1+1, t_VECSMALL);
122 53128 : for (i = 1; i <= l1; ++i)
123 : {
124 41912 : p2[i] = Flx_cindex(gel(F1, i), p);
125 41912 : e2[i] = F2[i];
126 : }
127 11216 : return mkmat2(p2, e2);
128 : }
129 :
130 : static long
131 74256 : Flx_addifsmooth3(pari_sp *av, struct Flxq_log_rel *r, GEN h, long u, long v, long w, ulong p)
132 : {
133 74256 : long off = r->off;
134 74256 : r->nbtest++;
135 74256 : if (Flx_is_smooth(h, r->r, p))
136 : {
137 5670 : GEN z = factorel(h, p);
138 5670 : if (v<0)
139 1225 : z = mkmat2(vecsmall_append(gel(z,1),off+u),vecsmall_append(gel(z,2),-1));
140 : else
141 13335 : z = famatsmall_reduce(mkmat2(
142 4445 : vecsmall_concat(gel(z,1),mkvecsmall3(off+u,off+v,off+w)),
143 4445 : vecsmall_concat(gel(z,2),mkvecsmall3(-1,-1,-1))));
144 5670 : gel(r->rel,++r->nbrel) = gerepilecopy(*av,z);
145 5670 : if (DEBUGLEVEL && (r->nbrel&511UL)==0)
146 0 : err_printf("%ld%% ",r->nbrel*100/r->nbexp);
147 5670 : *av = avma;
148 68586 : } else set_avma(*av);
149 74256 : return r->nbrel==r->nb || r->nbrel==r->nbmax;
150 : }
151 :
152 : static void
153 435141 : Flx_renormalize_inplace(GEN x, long lx)
154 : {
155 : long i;
156 4970206 : for (i = lx-1; i>1; i--)
157 4967563 : if (x[i]) break;
158 435141 : setlg(x, i+1);
159 435288 : }
160 :
161 : /*
162 : Let T*X^e=C^3-R
163 : a+b+c = 0
164 : (C+a)*(C+b)*(C+c) = C^3+ (a*b+a*c+b*c)*C+a*b*c
165 : = R + (a*b+a*c+b*c)*C+a*b*c
166 : = R + (a*b-c^2)*C+a*b*c
167 : */
168 : static void
169 14 : Flxq_log_cubic(struct Flxq_log_rel *r, GEN C, GEN R, ulong p, ulong pi)
170 : {
171 14 : long l = lg(C);
172 14 : GEN a = zero_zv(l); /*We allocate one extra word to catch overflow*/
173 14 : GEN b = zero_zv(l);
174 14 : pari_sp av = avma;
175 : long i,j,k;
176 2800 : for(i=0; ; i++, Flx_cnext(a, p))
177 : {
178 2800 : Flx_renormalize_inplace(a, l+1);
179 2800 : r->nb++;
180 2800 : if (Flx_addifsmooth3(&av, r, Flx_add(a, C, p), i, -1, -1, p)) return;
181 29400 : for(j=2; j<=l; j++) b[j] = 0;
182 353129 : for(j=0; j<=i; j++, Flx_cnext(b, p))
183 : {
184 : GEN h,c;
185 : GEN pab,pabc,pabc2;
186 350343 : Flx_renormalize_inplace(b, l+1);
187 350343 : c = Flx_neg(Flx_add(a,b,p),p);
188 350343 : k = Flx_cindex(c, p);
189 350343 : if (k > j) continue;
190 71456 : pab = Flx_mul_pre(a, b, p, pi);
191 71456 : pabc = Flx_mul_pre(pab,c,p,pi);
192 71456 : pabc2= Flx_sub(pab,Flx_sqr_pre(c,p,pi),p);
193 71456 : h = Flx_add(R,Flx_add(Flx_mul_pre(C,pabc2,p,pi),pabc,p), p);
194 71456 : h = Flx_normalize(h, p);
195 71456 : if (Flx_addifsmooth3(&av, r, h, i, j, k, p)) return;
196 : }
197 : }
198 : }
199 :
200 : static GEN
201 69 : Flxq_log_find_rel(GEN b, long r, GEN T, ulong p, ulong pi, GEN *g, long *e)
202 : {
203 69 : pari_sp av = avma;
204 : while (1)
205 3644 : {
206 : GEN M, z;
207 3713 : *g = Flxq_mul_pre(*g, b, T, p, pi); (*e)++;
208 3713 : M = Flx_halfgcd_all_pre(*g,T,p,pi,&z,NULL);
209 3713 : if (Flx_is_smooth_pre(gcoeff(M,1,1), r, p, pi)
210 454 : && Flx_is_smooth_pre(z, r, p, pi))
211 : {
212 69 : GEN F = factorel(z, p);
213 69 : GEN G = factorel(gcoeff(M,1,1), p);
214 69 : GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
215 69 : vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
216 69 : return gc_all(av,2,&rel,g);
217 : }
218 3644 : if (gc_needed(av,2))
219 : {
220 0 : if (DEBUGMEM>1) pari_warn(warnmem,"Flxq_log_find_rel");
221 0 : *g = gerepilecopy(av, *g);
222 : }
223 : }
224 : }
225 :
226 : /* Generalised Odlyzko formulae ( EUROCRYPT '84, LNCS 209, pp. 224-314, 1985. ) */
227 : /* Return the number of monic, k smooth, degree n polynomials for k=1..r */
228 : static GEN
229 2233 : smoothness_vec(ulong p, long r, long n)
230 : {
231 : long i,j,k;
232 2233 : GEN R = cgetg(r+1, t_VEC), pp = utoipos(p);
233 2233 : GEN V = cgetg(n+1, t_VEC);
234 20496 : for (j = 1; j <= n; ++j)
235 18263 : gel(V, j) = binomialuu(p+j-1,j);
236 2233 : gel(R, 1) = gel(V, n);
237 5341 : for (k = 2; k <= r; ++k)
238 : {
239 3108 : GEN W = cgetg(n+1, t_VEC);
240 3108 : GEN Ik = ffnbirred(pp, k);
241 36029 : for (j = 1; j <= n; ++j)
242 : {
243 32921 : long l = j/k;
244 32921 : GEN s = gen_0;
245 32921 : pari_sp av2 = avma;
246 32921 : if (l*k == j)
247 : {
248 10801 : s = binomial(addiu(Ik,l-1), l);
249 10801 : l--;
250 : }
251 119847 : for (i = 0; i <= l; ++i)
252 86926 : s = addii(s, mulii(gel(V, j-k*i), binomial(addis(Ik,i-1), i)));
253 32921 : gel(W, j) = gerepileuptoint(av2, s);
254 : }
255 3108 : V = W;
256 3108 : gel(R, k) = gel(V, n);
257 : }
258 2233 : return R;
259 : }
260 :
261 : /* Solve N^2*pr/6 + N*prC = N+fb
262 : N^2*pr/6 + N*(prC-1) -fb = 0
263 : */
264 :
265 : static GEN
266 1729 : smooth_cost(GEN fb, GEN pr, GEN prC)
267 : {
268 1729 : GEN a = gdivgu(pr,6);
269 1729 : GEN b = gsubgs(prC,1);
270 1729 : GEN c = gneg(fb);
271 1729 : GEN vD = gsqrt(gsub(gsqr(b),gmul2n(gmul(a,c),2)),BIGDEFAULTPREC);
272 1729 : return ceil_safe(gdiv(gsub(vD,b),gmul2n(a,1)));
273 : }
274 :
275 : /* Return best choice of r.
276 : We loop over d until there is sufficiently many triples (a,b,c) (a+b+c=0)
277 : of degree <=d with respect to the probability of smoothness of (a*b-c^2)*C
278 : */
279 :
280 : static GEN
281 315 : smooth_best(long p, long n, long *pt_r, long *pt_nb)
282 : {
283 315 : pari_sp av = avma, av2;
284 315 : GEN bestc = NULL, pp = utoipos(p);
285 315 : long bestr = 0, bestFB = 0;
286 315 : long r,d, dC = (n+2)/3;
287 819 : for (r = 1; r < dC; ++r)
288 : {
289 504 : GEN fb = ffsumnbirred(pp, r);
290 504 : GEN smoothC = smoothness_vec(p,r,dC);
291 504 : GEN prC = gdiv(gel(smoothC,r), powuu(p,dC));
292 504 : ulong rels = 0;
293 504 : av2 = avma;
294 2023 : for(d=0; d<dC && rels < ULONG_MAX; d++)
295 : {
296 : GEN c;
297 1729 : long dt = dC+2*d;
298 1729 : GEN smooth = smoothness_vec(p,r,dt);
299 1729 : GEN pr = gdiv(gel(smooth,r), powuu(p,dt));
300 1729 : GEN FB = addii(fb,powuu(p,d));
301 1729 : GEN N = smooth_cost(subiu(FB,rels),pr,prC);
302 1729 : GEN Nmax = powuu(p,d+1);
303 1729 : if (gcmp(N,Nmax) >= 0)
304 : {
305 1519 : rels = itou_or_0(addui(rels, gceil(gmul(gdivgu(sqri(Nmax),6),pr))));
306 1519 : if (!rels) rels = ULONG_MAX;
307 1519 : set_avma(av2);
308 1519 : continue;
309 : }
310 210 : c = gdivgu(addii(powuu(p,2*d),sqri(N)),6);
311 210 : FB = addii(FB,N);
312 210 : if ((!bestc || gcmp(gmul2n(c,r), gmul2n(bestc,bestr)) < 0))
313 : {
314 133 : if (DEBUGLEVEL)
315 0 : err_printf("r=%ld d=%ld fb=%Ps early rels=%lu P=%.5Pe -> C=%.5Pe \n",
316 : r, dt, FB, rels, pr, c);
317 133 : bestc = c;
318 133 : bestr = r;
319 133 : bestFB = itos_or_0(FB);
320 : }
321 210 : break;
322 : }
323 : }
324 315 : *pt_r=bestr;
325 315 : *pt_nb=bestFB;
326 315 : return bestc ? gerepileupto(av, gceil(bestc)): NULL;
327 : }
328 :
329 : static GEN
330 28 : check_kernel(long r, GEN M, long nbi, long nbrow, GEN T, ulong p, ulong pi, GEN m)
331 : {
332 28 : pari_sp av = avma;
333 28 : long N = 3*upowuu(p, r);
334 28 : GEN K = FpMs_leftkernel_elt(M, nbrow, m);
335 28 : long i, f=0, tbs;
336 28 : long lm = lgefint(m), u=1;
337 : GEN tab, g;
338 28 : GEN q = powuu(p,degpol(T));
339 28 : GEN idx = diviiexact(subiu(q,1),m);
340 : pari_timer ti;
341 28 : if (DEBUGLEVEL) timer_start(&ti);
342 224 : while (signe(gel(K,u))==0)
343 196 : u++;
344 28 : K = FpC_Fp_mul(K, Fp_inv(gel(K, u), m), m);
345 28 : g = Flxq_pow_pre(cindex_Flx(u, r, p, T[1]), idx, T, p, pi);
346 28 : tbs = maxss(1, expu(nbi/expi(m)));
347 28 : tab = Flxq_pow_init_pre(g, q, tbs, T, p, pi);
348 28 : setlg(K, N);
349 46662 : for (i=1; i<N; i++)
350 : {
351 46634 : GEN k = gel(K,i);
352 46634 : pari_sp av = avma;
353 51031 : long t = signe(k) && Flx_equal(Flxq_pow_table_pre(tab, k, T, p, pi),
354 4397 : Flxq_pow_pre(cindex_Flx(i,r,p,T[1]), idx, T, p, pi));
355 46634 : set_avma(av);
356 46634 : if (!t)
357 42237 : gel(K,i) = cgetineg(lm);
358 : else
359 4397 : f++;
360 : }
361 28 : if (DEBUGLEVEL) timer_printf(&ti,"found %ld/%ld logs", f, nbi);
362 28 : if (f < maxss(3,maxss(p/2,nbi/p))) return NULL; /* Not enough logs found */
363 28 : return gerepilecopy(av, K);
364 : }
365 :
366 : static GEN
367 28 : Flxq_log_rec(GEN W, GEN a, long r, GEN T, ulong p, ulong pi, GEN m)
368 : {
369 28 : long AV = 0, u = 1;
370 28 : GEN g = a, b;
371 : pari_timer ti;
372 280 : while (!equali1(gel(W,u)))
373 252 : u++;
374 28 : b = cindex_Flx(u, r, p, T[1]);
375 : while(1)
376 13 : {
377 : long i, l;
378 : GEN V, F, E, Ao;
379 41 : timer_start(&ti);
380 41 : V = Flxq_log_find_rel(b, r, T, p, pi, &g, &AV);
381 41 : if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r);
382 41 : F = gel(V,1); E = gel(V,2);
383 41 : l = lg(F);
384 41 : Ao = gen_0;
385 320 : for(i=1; i<l; i++)
386 : {
387 292 : GEN R = gel(W,F[i]);
388 292 : if (signe(R)<=0)
389 13 : break;
390 279 : Ao = Fp_add(Ao, mulis(R, E[i]), m);
391 : }
392 41 : if (i==l) return subis(Ao,AV);
393 : }
394 : }
395 :
396 : static int
397 301 : Flxq_log_use_index_cubic(GEN m, GEN T0, ulong p)
398 : {
399 301 : pari_sp av = avma;
400 301 : long n = get_Flx_degree(T0), r, nb;
401 301 : GEN cost = smooth_best(p, n, &r, &nb);
402 301 : GEN cost_rho = sqrti(shifti(m,2));
403 301 : int use = (cost && gcmp(cost,cost_rho)<0);
404 301 : set_avma(av);
405 301 : return use;
406 : }
407 :
408 : static GEN
409 14 : Flxq_log_index_cubic(GEN a0, GEN b0, GEN m, GEN T0, ulong p)
410 : {
411 14 : ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
412 14 : long n = get_Flx_degree(T0), r, nb;
413 14 : pari_sp av = avma;
414 : struct Flxq_log_rel rel;
415 : long nbi;
416 : GEN W, M, S, T, a, b, Ao, Bo, e, C, R;
417 : pari_timer ti;
418 14 : GEN cost = smooth_best(p, n, &r, &nb);
419 14 : GEN cost_rho = sqrti(shifti(m,2));
420 14 : if (!cost || gcmp(cost,cost_rho)>=0) return gc_NULL(av);
421 14 : nbi = itos(ffsumnbirred(stoi(p), r));
422 14 : if (DEBUGLEVEL)
423 : {
424 0 : err_printf("Size FB=%ld, looking for %ld relations, %Ps tests needed\n", nbi, nb,cost);
425 0 : timer_start(&ti);
426 : }
427 14 : T = smallirred_Flx(p,n,get_Flx_var(T0), pi);
428 : for(;;)
429 : {
430 14 : S = Flx_ffisom(T0,T,p);
431 14 : a = Flx_Flxq_eval_pre(a0, S, T, p, pi);
432 14 : b = Flx_Flxq_eval_pre(b0, S, T, p, pi);
433 14 : C = Flx_shift(pol1_Flx(get_Flx_var(T)), (n+2)/3);
434 14 : R = Flxq_powu_pre(C,3,T,p,pi);
435 14 : if (DEBUGLEVEL)
436 0 : timer_printf(&ti," model change: %Ps",Flx_to_ZX(T));
437 14 : rel.nbmax=2*nb;
438 14 : M = cgetg(rel.nbmax+1, t_VEC);
439 14 : rel.rel = M;
440 14 : rel.nbrel = 0; rel.r = r; rel.off = 3*upowuu(p,r);
441 14 : rel.nb = nbi; rel.nbexp = nb; rel.nbtest=0;
442 14 : Flxq_log_cubic(&rel, C, R, p, pi);
443 14 : setlg(M,1+rel.nbrel);
444 14 : if (DEBUGLEVEL)
445 : {
446 0 : err_printf("\n");
447 0 : timer_printf(&ti," %ld relations, %ld generators (%ld tests)",rel.nbrel,rel.nb,rel.nbtest);
448 : }
449 14 : W = check_kernel(r, M, nbi, rel.off + rel.nb - nbi, T, p, pi, m);
450 14 : if (W) break;
451 0 : if (DEBUGLEVEL) timer_start(&ti);
452 0 : smallirred_Flx_next(T,p, pi);
453 : }
454 14 : if (DEBUGLEVEL) timer_start(&ti);
455 14 : Ao = Flxq_log_rec(W, a, r, T, p, pi, m);
456 14 : if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
457 14 : Bo = Flxq_log_rec(W, b, r, T, p, pi, m);
458 14 : if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
459 14 : e = Fp_div(Ao, Bo, m);
460 14 : if (!Flx_equal(Flxq_pow_pre(b0, e, T0, p, pi), a0)) pari_err_BUG("Flxq_log");
461 14 : return gerepileupto(av, e);
462 : }
463 :
464 23534 : INLINE GEN Flx_frob(GEN u, ulong p) { return Flx_inflate(u, p); }
465 :
466 : static GEN
467 40915 : rel_Coppersmith(long r, GEN u, GEN v, long h, GEN R, long d, ulong p, ulong pi)
468 : {
469 : GEN a, b, F, G, M;
470 40915 : if (degpol(Flx_gcd_pre(u,v,p,pi))) return NULL;
471 40791 : a = Flx_add(Flx_shift(u, h), v, p);
472 40898 : if (lgpol(a)==0 || !Flx_is_smooth_pre(a, r, p, pi)) return NULL;
473 10001 : b = Flx_add(Flx_mul_pre(R, Flx_frob(u, p), p, pi),
474 : Flx_shift(Flx_frob(v, p),d), p);
475 10053 : if (!Flx_is_smooth_pre(b, r, p, pi)) return NULL;
476 2640 : F = factorel(a, p); G = factorel(b, p);
477 5280 : M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2*p)),
478 5280 : vecsmall_concat(zv_z_mul(gel(F, 2),p), vecsmall_append(zv_neg(gel(G, 2)),d)));
479 2640 : return famatsmall_reduce(M);
480 : }
481 :
482 : GEN
483 1454 : Flxq_log_Coppersmith_worker(GEN u, long i, GEN V, GEN R)
484 : {
485 1454 : long r = V[1], h = V[2], d = V[3], p = V[4], pi = V[5], dT = V[6];
486 1454 : pari_sp ltop = avma;
487 1454 : GEN v = zero_zv(dT+2);
488 1460 : GEN L = cgetg(2*i+1, t_VEC);
489 1458 : pari_sp av = avma;
490 : long j;
491 1458 : long nbtest=0, rel = 1;
492 1458 : ulong lu = Flx_lead(u), lv;
493 81878 : for (j=1; j<=i; j++)
494 : {
495 : GEN z;
496 80413 : Flx_cnext(v, p);
497 80449 : Flx_renormalize_inplace(v, dT+2);
498 80607 : lv = Flx_lead(v);
499 80583 : set_avma(av);
500 80569 : if (lu != 1 && lv != 1) continue;
501 50065 : if (degpol(Flx_gcd_pre(u, v, p, pi))!=0) continue;
502 33649 : if (lu==1)
503 : {
504 21209 : z = rel_Coppersmith(r, u, v, h, R, d, p, pi);
505 21274 : nbtest++;
506 21274 : if (z) { gel(L, rel++) = z; av = avma; }
507 : }
508 33714 : if (i==j) continue;
509 33521 : if (lv==1)
510 : {
511 19670 : z = rel_Coppersmith(r, v, u, h, R, d, p, pi);
512 19699 : nbtest++;
513 19699 : if (z) { gel(L, rel++) = z; av = avma; }
514 : }
515 : }
516 1465 : setlg(L,rel);
517 1465 : return gerepilecopy(ltop, mkvec2(stoi(nbtest), L));
518 : }
519 :
520 : static GEN
521 14 : Flxq_log_Coppersmith(long nbrel, long r, GEN T, ulong p, ulong pi)
522 : {
523 : pari_sp av;
524 14 : long dT = degpol(T);
525 14 : long h = dT/p, d = dT-(h*p);
526 14 : GEN R = Flx_sub(Flx_shift(pol1_Flx(T[1]), dT), T, p);
527 14 : GEN u = zero_zv(dT+2);
528 : GEN done;
529 14 : long nbtest = 0, rel = 0;
530 14 : GEN M = cgetg(nbrel+1, t_VEC);
531 14 : long i = 1;
532 14 : GEN worker = snm_closure(is_entry("_Flxq_log_Coppersmith_worker"),
533 : mkvec2(mkvecsmalln(6, r,h,d,p,pi,dT), R));
534 : struct pari_mt pt;
535 14 : long running, pending = 0, stop=0;
536 14 : if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",degpol(R));
537 14 : mt_queue_start(&pt, worker);
538 14 : av = avma;
539 1541 : while ((running = !stop) || pending)
540 : {
541 : GEN L;
542 : long l, j;
543 1527 : Flx_cnext(u, p);
544 1527 : Flx_renormalize_inplace(u, dT+2);
545 1527 : mt_queue_submit(&pt, 0, running ? mkvec2(u, stoi(i)): NULL);
546 1527 : done = mt_queue_get(&pt, NULL, &pending);
547 1527 : if (!done) continue;
548 1465 : L = gel(done, 2); nbtest += itos(gel(done,1));
549 1465 : l = lg(L);
550 1465 : if (l > 1)
551 : {
552 3437 : for (j=1; j<l; j++)
553 : {
554 2494 : if (rel>nbrel) break;
555 2429 : gel(M,++rel) = gel(L,j);
556 2429 : if (DEBUGLEVEL && (rel&511UL)==0)
557 0 : err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
558 : }
559 1008 : av = avma;
560 : }
561 457 : else set_avma(av);
562 1465 : if (rel>nbrel) stop = 1;
563 1465 : i++;
564 : }
565 14 : mt_queue_end(&pt);
566 14 : if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
567 14 : return M;
568 : }
569 :
570 : static GEN Flxq_log_Coppersmith_d(GEN W, GEN g, long r, GEN T, ulong p, ulong pi, GEN mo);
571 :
572 : static GEN
573 64 : Flxq_log_from_rel(GEN W, GEN rel, long r, GEN T, ulong p, ulong pi, GEN m)
574 : {
575 64 : pari_sp av = avma;
576 64 : GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
577 64 : long i, l = lg(F);
578 478 : for(i=1; i<l; i++)
579 : {
580 414 : GEN R = gel(W, F[i]);
581 414 : if (signe(R)==0) /* Already failed */
582 0 : return NULL;
583 414 : else if (signe(R)<0) /* Not yet tested */
584 : {
585 15 : setsigne(gel(W,F[i]),0);
586 15 : R = Flxq_log_Coppersmith_d(W, cindex_Flx(F[i],r,p,T[1]), r, T, p, pi, m);
587 15 : if (!R) return NULL;
588 : }
589 414 : o = Fp_add(o, mulis(R, E[i]), m);
590 : }
591 64 : return gerepileuptoint(av, o);
592 : }
593 :
594 : static GEN
595 64 : Flxq_log_Coppersmith_d(GEN W, GEN g, long r, GEN T, ulong p, ulong pi, GEN mo)
596 : {
597 64 : pari_sp av = avma, av2;
598 64 : long dg = degpol(g), k = r-1, m = maxss((dg-k)/2,0);
599 64 : long i, j, l = dg-m, N;
600 64 : GEN v = cgetg(k+m+1,t_MAT);
601 64 : long dT = degpol(T);
602 64 : long h = dT/p, d = dT-h*p;
603 64 : GEN R = Flx_rem_pre(Flx_shift(pol1_Flx(T[1]), dT), T, p, pi);
604 64 : GEN z = Flx_rem_pre(Flx_shift(pol1_Flx(T[1]), h), g, p, pi);
605 424 : for(i=1; i<=k+m; i++)
606 : {
607 360 : gel(v,i) = Flx_to_Flv(Flx_shift(z,-l),m);
608 360 : z = Flx_rem_pre(Flx_shift(z,1),g,p,pi);
609 : }
610 64 : v = Flm_ker(v,p);
611 369 : for(i=1; i<=k; i++)
612 305 : gel(v,i) = Flv_to_Flx(gel(v,i),T[1]);
613 64 : N = upowuu(p,k);
614 64 : av2 = avma;
615 1721 : for (i=1; i<N; i++)
616 : {
617 : GEN p0,q,qh,a,b;
618 1721 : ulong el = i;
619 1721 : set_avma(av2);
620 1721 : q = pol0_Flx(T[1]);
621 10058 : for (j=1; j<=k; j++)
622 : {
623 8337 : ulong r = el % p;
624 8337 : el /= p;
625 8337 : if (r) q = Flx_add(q, Flx_Fl_mul(gel(v,j), r, p), p);
626 : }
627 1721 : qh = Flx_shift(q, h);
628 1721 : p0 = Flx_rem_pre(qh, g, p, pi);
629 1721 : b = Flx_sub(Flx_mul_pre(R, Flx_frob(q, p), p, pi),
630 : Flx_shift(Flx_frob(p0, p), d), p);
631 1721 : if (lgpol(b)==0 || !Flx_is_smooth_pre(b, r, p, pi)) continue;
632 160 : a = Flx_div_pre(Flx_sub(qh, p0, p), g, p, pi);
633 160 : if (degpol(Flx_gcd_pre(a, q, p, pi)) && degpol(Flx_gcd_pre(a, p0, p, pi)))
634 48 : continue;
635 112 : if (!(lgpol(a)==0 || !Flx_is_smooth_pre(a, r, p, pi)))
636 : {
637 64 : GEN F = factorel(b, p);
638 64 : GEN G = factorel(a, p);
639 64 : GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2*p), gel(G, 1));
640 64 : GEN E = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
641 64 : zv_z_mul(gel(G, 2),-p));
642 64 : GEN R = famatsmall_reduce(mkmat2(FG, E));
643 64 : GEN l = Flxq_log_from_rel(W, R, r, T, p, pi, mo);
644 64 : if (!l) continue;
645 64 : l = Fp_divu(l,p,mo);
646 64 : if (dg <= r)
647 : {
648 15 : long idx = Flx_cindex(g, p);
649 15 : affii(l, gel(W, idx));
650 15 : if (DEBUGLEVEL>1) err_printf("Found %lu\n", idx);
651 : }
652 64 : return gerepileuptoint(av, l);
653 : }
654 : }
655 0 : set_avma(av);
656 0 : return NULL;
657 : }
658 :
659 : static GEN
660 28 : Flxq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, GEN T, ulong p, ulong pi, GEN m)
661 : {
662 28 : GEN b = polx_Flx(T[1]);
663 28 : long AV = 0;
664 28 : GEN g = a, bad = pol0_Flx(T[1]);
665 : pari_timer ti;
666 : while(1)
667 0 : {
668 : long i, l;
669 : GEN V, F, E, Ao;
670 28 : timer_start(&ti);
671 28 : V = Flxq_log_find_rel(b, r2, T, p, pi, &g, &AV);
672 28 : if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
673 28 : F = gel(V,1); E = gel(V,2);
674 28 : l = lg(F);
675 28 : Ao = gen_0;
676 203 : for(i=1; i<l; i++)
677 : {
678 175 : GEN Fi = cindex_Flx(F[i], r2, p, T[1]);
679 : GEN R;
680 175 : if (degpol(Fi) <= r)
681 : {
682 126 : if (signe(gel(W,F[i]))==0)
683 0 : break;
684 126 : else if (signe(gel(W,F[i]))<0)
685 : {
686 0 : setsigne(gel(W,F[i]),0);
687 0 : R = Flxq_log_Coppersmith_d(W,Fi,r,T,p,pi,m);
688 : } else
689 126 : R = gel(W,F[i]);
690 : }
691 : else
692 : {
693 49 : if (Flx_equal(Fi,bad)) break;
694 49 : R = Flxq_log_Coppersmith_d(W,Fi,r,T,p,pi,m);
695 49 : if (!R) bad = Fi;
696 : }
697 175 : if (!R) break;
698 175 : Ao = Fp_add(Ao, mulis(R, E[i]), m);
699 : }
700 28 : if (i==l) return subis(Ao,AV);
701 : }
702 : }
703 :
704 : static GEN
705 14 : Flxq_log_index_Coppersmith(GEN a0, GEN b0, GEN m, GEN T0, ulong p)
706 : {
707 14 : ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
708 14 : pari_sp av = avma;
709 14 : GEN M, S, a, b, Ao=NULL, Bo=NULL, W, e;
710 : pari_timer ti;
711 14 : double rf = p ==3 ? 1.2 : .9;
712 14 : long n = degpol(T0), r = (long) sqrt(n*rf);
713 : GEN T;
714 14 : long r2 = 3*r/2;
715 14 : long nbi = itos(ffsumnbirred(utoipos(p), r)), nbrel=nbi*5/4;
716 14 : if (DEBUGLEVEL)
717 : {
718 0 : err_printf("Coppersmith: Parameters r=%ld r2=%ld\n", r,r2);
719 0 : err_printf("Coppersmith: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
720 0 : timer_start(&ti);
721 : }
722 14 : T = smallirred_Flx(p,n,get_Flx_var(T0), pi);
723 14 : S = Flx_ffisom(T0,T,p);
724 14 : a = Flx_Flxq_eval_pre(a0, S, T, p, pi);
725 14 : b = Flx_Flxq_eval_pre(b0, S, T, p, pi);
726 14 : if (DEBUGLEVEL) timer_printf(&ti,"model change");
727 14 : M = Flxq_log_Coppersmith(nbrel, r, T, p, pi);
728 14 : if (DEBUGLEVEL) timer_printf(&ti,"relations");
729 14 : W = check_kernel(r, M, nbi, 3*upowuu(p,r), T, p, pi, m);
730 14 : timer_start(&ti);
731 14 : Ao = Flxq_log_Coppersmith_rec(W, r2, a, r, T, p, pi, m);
732 14 : if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
733 14 : Bo = Flxq_log_Coppersmith_rec(W, r2, b, r, T, p, pi, m);
734 14 : if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
735 14 : e = Fp_div(Ao, Bo, m);
736 14 : if (!Flx_equal(Flxq_pow_pre(b0,e,T0,p,pi), a0)) pari_err_BUG("Flxq_log");
737 14 : return gerepileupto(av, e);
738 : }
739 :
740 : GEN
741 28 : Flxq_log_index(GEN a, GEN b, GEN m, GEN T, ulong p)
742 : {
743 28 : long d = get_Flx_degree(T);
744 28 : if (p==3 || (p==5 && d>41))
745 14 : return Flxq_log_index_Coppersmith(a, b, m, T, p);
746 14 : else return Flxq_log_index_cubic(a, b, m, T, p);
747 : }
748 :
749 : int
750 164532 : Flxq_log_use_index(GEN m, GEN T, ulong p)
751 : {
752 164532 : long d = get_Flx_degree(T);
753 164532 : if (p==3 || (p==5 && d>41))
754 24297 : return 1;
755 140235 : else if (d<=4 || d==6)
756 139934 : return 0;
757 : else
758 301 : return Flxq_log_use_index_cubic(m, T, p);
759 : }
|
