CoCalc -- Flxq

Testing latest pari + WASM + node.js... and it works?! Wow.
pari / 2021-07-01 / pari-2.14.0.alpha / src / basemath / Flxq_log.c
²⁸⁴⁸⁵ views
License: GPL3
ubuntu2004
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
Flx_cindex(GEN P, ulong p)
26
{
27
  long d = degpol(P), i;
28
  ulong s = 0, p2 = (p-1)>>1;
29
  for (i = 0; i <= d; ++i)
30
  {
31
    ulong x = P[d-i+2];
32
    if (x<=p2) x = 2*x; else x = 1+2*(p-1-x);
33
    s = p*s+x;
34
  }
35
  return s;
36
}
37

38
/* Compute the polynomial immediately after t for the [[ order */
39

40
static void
41
Flx_cnext(GEN t, ulong p)
42
{
43
  long i;
44
  long p2 = p>>1;
45
  for(i=2;;i++)
46
    if (t[i]==p2)
47
      t[i]=0;
48
    else
49
    {
50
      t[i] = t[i]<p2 ? p-1-t[i]: p-t[i];
51
      break;
52
    }
53
}
54

55
static int
56
has_deg1_auto(GEN T, ulong p)
57
{
58
  long i, n = degpol(T);
59
  GEN a = polx_Flx(get_Flx_var(T));
60
  for (i=1; i<n; i++)
61
  {
62
    a = Flxq_powu(a, p, T, p);
63
    if (degpol(a)==1) return 1;
64
  }
65
  return 0;
66
}
67

68
static void
69
smallirred_Flx_next(GEN a, long p)
70
{
71
  do
72
  {
73
    long i;
74
    for(i=2;;i++)
75
      if (++a[i]==p) a[i]=0;
76
      else break;
77
  } while (!Flx_is_irred(a, p) || has_deg1_auto(a,p) );
78
}
79

80
/* Avoid automorphisms of degree 1 */
81
static GEN
82
smallirred_Flx(long p, ulong n, long sv)
83
{
84
  GEN a = zero_zv(n+2);
85
  a[1] = sv; a[3] = 1; a[n+2] = 1;
86
  smallirred_Flx_next(a, p);
87
  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
cindex_Flx(long c, long d, ulong p, long v)
101
{
102
  GEN P = cgetg(d+3, t_VECSMALL);
103
  long i;
104
  P[1] = v;
105
  for (i = 0; i <= d; ++i)
106
  {
107
    ulong x = c%p;
108
    P[i+2] = (x&1) ? p-1-(x>>1) : x>>1;
109
    c/=p;
110
  }
111
  return Flx_renormalize(P, d+3);
112
}
113

114
static GEN
115
factorel(GEN h, ulong p)
116
{
117
  GEN F = Flx_factor(h, p);
118
  GEN F1 = gel(F, 1), F2 = gel(F, 2);
119
  long i, l1 = lg(F1)-1;
120
  GEN p2 = cgetg(l1+1, t_VECSMALL);
121
  GEN e2 = cgetg(l1+1, t_VECSMALL);
122
  for (i = 1; i <= l1; ++i)
123
  {
124
    p2[i] = Flx_cindex(gel(F1, i), p);
125
    e2[i] = F2[i];
126
  }
127
  return mkmat2(p2, e2);
128
}
129

130
static long
131
Flx_addifsmooth3(pari_sp *av, struct Flxq_log_rel *r, GEN h, long u, long v, long w, ulong p)
132
{
133
  long off = r->off;
134
  r->nbtest++;
135
  if (Flx_is_smooth(h, r->r, p))
136
  {
137
    GEN z = factorel(h, p);
138
    if (v<0)
139
      z = mkmat2(vecsmall_append(gel(z,1),off+u),vecsmall_append(gel(z,2),-1));
140
    else
141
      z = famatsmall_reduce(mkmat2(
142
            vecsmall_concat(gel(z,1),mkvecsmall3(off+u,off+v,off+w)),
143
            vecsmall_concat(gel(z,2),mkvecsmall3(-1,-1,-1))));
144
    gel(r->rel,++r->nbrel) = gerepilecopy(*av,z);
145
    if (DEBUGLEVEL && (r->nbrel&511UL)==0)
146
      err_printf("%ld%% ",r->nbrel*100/r->nbexp);
147
    *av = avma;
148
  } else set_avma(*av);
149
  return r->nbrel==r->nb || r->nbrel==r->nbmax;
150
}
151

152
static void
153
Flx_renormalize_inplace(GEN x, long lx)
154
{
155
  long i;
156
  for (i = lx-1; i>1; i--)
157
    if (x[i]) break;
158
  setlg(x, i+1);
159
}
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
Flxq_log_cubic(struct Flxq_log_rel *r, GEN C, GEN R, ulong p)
170
{
171
  long l = lg(C);
172
  GEN a = zero_zv(l); /*We allocate one extra word to catch overflow*/
173
  GEN b = zero_zv(l);
174
  pari_sp av = avma;
175
  long i,j,k;
176
  for(i=0; ; i++, Flx_cnext(a, p))
177
  {
178
    Flx_renormalize_inplace(a, l+1);
179
    r->nb++;
180
    if (Flx_addifsmooth3(&av, r, Flx_add(a, C, p), i, -1, -1, p)) return;
181
    for(j=2; j<=l; j++) b[j] = 0;
182
    for(j=0; j<=i; j++, Flx_cnext(b, p))
183
    {
184
      GEN h,c;
185
      GEN pab,pabc,pabc2;
186
      Flx_renormalize_inplace(b, l+1);
187
      c = Flx_neg(Flx_add(a,b,p),p);
188
      k = Flx_cindex(c, p);
189
      if (k > j) continue;
190
      pab  = Flx_mul(a, b, p);
191
      pabc = Flx_mul(pab,c,p);
192
      pabc2= Flx_sub(pab,Flx_sqr(c,p),p);
193
      h = Flx_add(R,Flx_add(Flx_mul(C,pabc2,p),pabc,p), p);
194
      h = Flx_normalize(h, p);
195
      if (Flx_addifsmooth3(&av, r, h, i, j, k, p)) return;
196
    }
197
  }
198
}
199

200
static GEN
201
Flxq_log_find_rel(GEN b, long r, GEN T, ulong p, GEN *g, long *e)
202
{
203
  pari_sp av = avma;
204
  while (1)
205
  {
206
    GEN M;
207
    *g = Flxq_mul(*g, b, T, p); (*e)++;
208
    M = Flx_halfgcd(*g,T,p);
209
    if (Flx_is_smooth(gcoeff(M,1,1), r, p))
210
    {
211
      GEN z = Flx_add(Flx_mul(gcoeff(M,1,1),*g,p), Flx_mul(gcoeff(M,1,2),T,p),p);
212
      if (Flx_is_smooth(z, r, p))
213
      {
214
        GEN F = factorel(z, p);
215
        GEN G = factorel(gcoeff(M,1,1), p);
216
        GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
217
                         vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
218
        gerepileall(av,2,g,&rel); return rel;
219
      }
220
    }
221
    if (gc_needed(av,2))
222
    {
223
      if (DEBUGMEM>1) pari_warn(warnmem,"Flxq_log_find_rel");
224
      *g = gerepilecopy(av, *g);
225
    }
226
  }
227
}
228

229
/* Generalised Odlyzko formulae ( EUROCRYPT '84, LNCS 209, pp. 224-314, 1985. ) */
230
/* Return the number of monic, k smooth, degree n polynomials for k=1..r */
231
static GEN
232
smoothness_vec(ulong p, long r, long n)
233
{
234
  long i,j,k;
235
  GEN R = cgetg(r+1, t_VEC), pp = utoipos(p);
236
  GEN V = cgetg(n+1, t_VEC);
237
  for (j = 1; j <= n; ++j)
238
    gel(V, j) =  binomialuu(p+j-1,j);
239
  gel(R, 1) = gel(V, n);
240
  for (k = 2; k <= r; ++k)
241
  {
242
    GEN W = cgetg(n+1, t_VEC);
243
    GEN Ik = ffnbirred(pp, k);
244
    for (j = 1; j <= n; ++j)
245
    {
246
      long l = j/k;
247
      GEN s = gen_0;
248
      pari_sp av2 = avma;
249
      if (l*k == j)
250
      {
251
        s = binomial(addiu(Ik,l-1), l);
252
        l--;
253
      }
254
      for (i = 0; i <= l; ++i)
255
        s = addii(s, mulii(gel(V, j-k*i), binomial(addis(Ik,i-1), i)));
256
      gel(W, j) = gerepileuptoint(av2, s);
257
    }
258
    V = W;
259
    gel(R, k) = gel(V, n);
260
  }
261
  return R;
262
}
263

264
/* Solve N^2*pr/6 + N*prC = N+fb
265
   N^2*pr/6 + N*(prC-1) -fb = 0
266
 */
267

268
static GEN
269
smooth_cost(GEN fb, GEN pr, GEN prC)
270
{
271
  GEN a = gdivgs(pr,6);
272
  GEN b = gsubgs(prC,1);
273
  GEN c = gneg(fb);
274
  GEN vD = gsqrt(gsub(gsqr(b),gmul2n(gmul(a,c),2)),BIGDEFAULTPREC);
275
  return ceil_safe(gdiv(gsub(vD,b),gmul2n(a,1)));
276
}
277

278
/* Return best choice of r.
279
   We loop over d until there is sufficiently many triples (a,b,c) (a+b+c=0)
280
   of degree <=d with respect to the probability of smoothness of (a*b-c^2)*C
281
 */
282

283
static GEN
284
smooth_best(long p, long n, long *pt_r, long *pt_nb)
285
{
286
  pari_sp av = avma, av2;
287
  GEN bestc = NULL, pp = utoipos(p);
288
  long bestr = 0, bestFB = 0;
289
  long r,d, dC = (n+2)/3;
290
  for (r = 1; r < dC; ++r)
291
  {
292
    GEN fb = ffsumnbirred(pp, r);
293
    GEN smoothC = smoothness_vec(p,r,dC);
294
    GEN prC = gdiv(gel(smoothC,r), powuu(p,dC));
295
    ulong rels = 0;
296
    av2 = avma;
297
    for(d=0; d<dC && rels < ULONG_MAX; d++)
298
    {
299
      GEN c;
300
      long dt = dC+2*d;
301
      GEN smooth = smoothness_vec(p,r,dt);
302
      GEN pr = gdiv(gel(smooth,r), powuu(p,dt));
303
      GEN FB = addii(fb,powuu(p,d));
304
      GEN N = smooth_cost(subiu(FB,rels),pr,prC);
305
      GEN Nmax = powuu(p,d+1);
306
      if (gcmp(N,Nmax) >= 0)
307
      {
308
        rels = itou_or_0(addui(rels, gceil(gmul(gdivgs(sqri(Nmax),6),pr))));
309
        if (!rels) rels = ULONG_MAX;
310
        set_avma(av2);
311
        continue;
312
      }
313
      c = gdivgs(addii(powuu(p,2*d),sqri(N)),6);
314
      FB = addii(FB,N);
315
      if ((!bestc || gcmp(gmul2n(c,r), gmul2n(bestc,bestr)) < 0))
316
      {
317
        if (DEBUGLEVEL)
318
          err_printf("r=%ld d=%ld fb=%Ps early rels=%lu P=%.5Pe -> C=%.5Pe \n",
319
                      r, dt, FB, rels, pr, c);
320
        bestc = c;
321
        bestr = r;
322
        bestFB = itos_or_0(FB);
323
      }
324
      break;
325
    }
326
  }
327
  *pt_r=bestr;
328
  *pt_nb=bestFB;
329
  return bestc ? gerepileupto(av, gceil(bestc)): NULL;
330
}
331

332
static GEN
333
check_kernel(long r, GEN M, long nbi, long nbrow, GEN T, ulong p, GEN m)
334
{
335
  pari_sp av = avma;
336
  long N = 3*upowuu(p, r);
337
  GEN K = FpMs_leftkernel_elt(M, nbrow, m);
338
  long i, f=0, tbs;
339
  long lm = lgefint(m), u=1;
340
  GEN tab, g;
341
  GEN q = powuu(p,degpol(T));
342
  GEN idx = diviiexact(subiu(q,1),m);
343
  pari_timer ti;
344
  if (DEBUGLEVEL) timer_start(&ti);
345
  while (signe(gel(K,u))==0)
346
    u++;
347
  K = FpC_Fp_mul(K, Fp_inv(gel(K, u), m), m);
348
  g = Flxq_pow(cindex_Flx(u, r, p, T[1]), idx, T, p);
349
  tbs = maxss(1, expu(nbi/expi(m)));
350
  tab = Flxq_pow_init(g, q, tbs, T, p);
351
  setlg(K, N);
352
  for (i=1; i<N; i++)
353
  {
354
    GEN k = gel(K,i);
355
    pari_sp av = avma;
356
    long t = signe(k) && Flx_equal(Flxq_pow_table(tab, k, T, p),
357
                                   Flxq_pow(cindex_Flx(i,r,p,T[1]), idx, T, p));
358
    set_avma(av);
359
    if (!t)
360
      gel(K,i) = cgetineg(lm);
361
    else
362
      f++;
363
  }
364
  if (DEBUGLEVEL) timer_printf(&ti,"found %ld/%ld logs", f, nbi);
365
  if (f < maxss(3,maxss(p/2,nbi/p))) return NULL; /* Not enough logs found */
366
  return gerepilecopy(av, K);
367
}
368

369
static GEN
370
Flxq_log_rec(GEN W, GEN a, long r, GEN T, ulong p, GEN m)
371
{
372
  long AV = 0, u = 1;
373
  GEN g = a, b;
374
  pari_timer ti;
375
  while (!equali1(gel(W,u)))
376
   u++;
377
  b = cindex_Flx(u, r, p, T[1]);
378
  while(1)
379
  {
380
    long i, l;
381
    GEN V, F, E, Ao;
382
    timer_start(&ti);
383
    V = Flxq_log_find_rel(b, r, T, p, &g, &AV);
384
    if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r);
385
    F = gel(V,1); E = gel(V,2);
386
    l = lg(F);
387
    Ao = gen_0;
388
    for(i=1; i<l; i++)
389
    {
390
      GEN R = gel(W,F[i]);
391
      if (signe(R)<=0)
392
        break;
393
      Ao = Fp_add(Ao, mulis(R, E[i]), m);
394
    }
395
    if (i==l) return subis(Ao,AV);
396
  }
397
}
398

399
static int
400
Flxq_log_use_index_cubic(GEN m, GEN T0, ulong p)
401
{
402
  pari_sp av = avma;
403
  long n = get_Flx_degree(T0), r, nb;
404
  GEN cost = smooth_best(p, n, &r, &nb);
405
  GEN cost_rho = sqrti(shifti(m,2));
406
  int use = (cost && gcmp(cost,cost_rho)<0);
407
  set_avma(av);
408
  return use;
409
}
410

411
static GEN
412
Flxq_log_index_cubic(GEN a0, GEN b0, GEN m, GEN T0, ulong p)
413
{
414
  long n = get_Flx_degree(T0), r, nb;
415
  pari_sp av = avma;
416
  struct Flxq_log_rel rel;
417
  long nbi;
418
  GEN W, M, S, T, a, b, Ao, Bo, e, C, R;
419
  pari_timer ti;
420
  GEN cost = smooth_best(p, n, &r, &nb);
421
  GEN cost_rho = sqrti(shifti(m,2));
422
  if (!cost || gcmp(cost,cost_rho)>=0) return gc_NULL(av);
423
  nbi = itos(ffsumnbirred(stoi(p), r));
424
  if (DEBUGLEVEL)
425
  {
426
    err_printf("Size FB=%ld, looking for %ld relations, %Ps tests needed\n", nbi, nb,cost);
427
    timer_start(&ti);
428
  }
429
  T = smallirred_Flx(p,n,get_Flx_var(T0));
430
  for(;;)
431
  {
432
    S = Flx_ffisom(T0,T,p);
433
    a = Flx_Flxq_eval(a0, S, T, p);
434
    b = Flx_Flxq_eval(b0, S, T, p);
435
    C = Flx_shift(pol1_Flx(get_Flx_var(T)), (n+2)/3);
436
    R = Flxq_powu(C,3,T,p);
437
    if (DEBUGLEVEL)
438
      timer_printf(&ti," model change: %Ps",Flx_to_ZX(T));
439
    rel.nbmax=2*nb;
440
    M = cgetg(rel.nbmax+1, t_VEC);
441
    rel.rel = M;
442
    rel.nbrel = 0; rel.r = r; rel.off = 3*upowuu(p,r);
443
    rel.nb = nbi; rel.nbexp = nb; rel.nbtest=0;
444
    Flxq_log_cubic(&rel, C, R, p);
445
    setlg(M,1+rel.nbrel);
446
    if (DEBUGLEVEL)
447
    {
448
      err_printf("\n");
449
      timer_printf(&ti," %ld relations, %ld generators (%ld tests)",rel.nbrel,rel.nb,rel.nbtest);
450
    }
451
    W = check_kernel(r, M, nbi, rel.off + rel.nb - nbi, T, p, m);
452
    if (W) break;
453
    if (DEBUGLEVEL) timer_start(&ti);
454
    smallirred_Flx_next(T,p);
455
  }
456
  if (DEBUGLEVEL) timer_start(&ti);
457
  Ao = Flxq_log_rec(W, a, r, T, p, m);
458
  if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
459
  Bo = Flxq_log_rec(W, b, r, T, p, m);
460
  if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
461
  e = Fp_div(Ao, Bo, m);
462
  if (!Flx_equal(Flxq_pow(b0, e, T0, p), a0)) pari_err_BUG("Flxq_log");
463
  return gerepileupto(av, e);
464
}
465

466
INLINE GEN Flx_frob(GEN u, ulong p) { return Flx_inflate(u, p); }
467

468
static GEN
469
rel_Coppersmith(long r, GEN u, GEN v, long h, GEN R, long d, ulong p)
470
{
471
  GEN a, b, F, G, M;
472
  if (degpol(Flx_gcd(u,v,p))) return NULL;
473
  a = Flx_add(Flx_shift(u, h), v, p);
474
  if (lgpol(a)==0 || !Flx_is_smooth(a, r, p)) return NULL;
475
  b = Flx_add(Flx_mul(R, Flx_frob(u, p), p), Flx_shift(Flx_frob(v, p),d), p);
476
  if (!Flx_is_smooth(b, r, p)) return NULL;
477
  F = factorel(a, p); G = factorel(b, p);
478
  M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2*p)),
479
             vecsmall_concat(zv_z_mul(gel(F, 2),p), vecsmall_append(zv_neg(gel(G, 2)),d)));
480
  return famatsmall_reduce(M);
481
}
482

483
GEN
484
Flxq_log_Coppersmith_worker(GEN u, long i, GEN V, GEN R)
485
{
486
  long r = V[1], h = V[2], d = V[3], p = V[4], dT = V[5];
487
  pari_sp ltop = avma;
488
  GEN v = zero_zv(dT+2);
489
  GEN L = cgetg(2*i+1, t_VEC);
490
  pari_sp av = avma;
491
  long j;
492
  long nbtest=0, rel = 1;
493
  ulong lu = Flx_lead(u), lv;
494
  for (j=1; j<=i; j++)
495
  {
496
    GEN z;
497
    Flx_cnext(v, p);
498
    Flx_renormalize_inplace(v, dT+2);
499
    lv = Flx_lead(v);
500
    set_avma(av);
501
    if (lu != 1 && lv != 1) continue;
502
    if (degpol(Flx_gcd(u, v, p))!=0) continue;
503
    if (lu==1)
504
    {
505
      z = rel_Coppersmith(r, u, v, h, R, d, p);
506
      nbtest++;
507
      if (z) { gel(L, rel++) = z; av = avma; }
508
    }
509
    if (i==j) continue;
510
    if (lv==1)
511
    {
512
      z = rel_Coppersmith(r, v, u, h, R, d, p);
513
      nbtest++;
514
      if (z) { gel(L, rel++) = z; av = avma; }
515
    }
516
  }
517
  setlg(L,rel);
518
  return gerepilecopy(ltop, mkvec2(stoi(nbtest), L));
519
}
520

521
static GEN
522
Flxq_log_Coppersmith(long nbrel, long r, GEN T, ulong p)
523
{
524
  pari_sp av;
525
  long dT = degpol(T);
526
  long h = dT/p, d = dT-(h*p);
527
  GEN R = Flx_sub(Flx_shift(pol1_Flx(T[1]), dT), T, p);
528
  GEN u = zero_zv(dT+2);
529
  GEN done;
530
  long nbtest = 0, rel = 0;
531
  GEN M = cgetg(nbrel+1, t_VEC);
532
  long i = 1;
533
  GEN worker = snm_closure(is_entry("_Flxq_log_Coppersmith_worker"),
534
               mkvec2(mkvecsmall5(r,h,d,p,dT), R));
535
  struct pari_mt pt;
536
  long running, pending = 0, stop=0;
537
  if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",degpol(R));
538
  mt_queue_start(&pt, worker);
539
  av = avma;
540
  while ((running = !stop) || pending)
541
  {
542
    GEN L;
543
    long l, j;
544
    Flx_cnext(u, p);
545
    Flx_renormalize_inplace(u, dT+2);
546
    mt_queue_submit(&pt, 0, running ? mkvec2(u, stoi(i)): NULL);
547
    done = mt_queue_get(&pt, NULL, &pending);
548
    if (!done) continue;
549
    L = gel(done, 2); nbtest += itos(gel(done,1));
550
    l = lg(L);
551
    if (l > 1)
552
    {
553
      for (j=1; j<l; j++)
554
      {
555
        if (rel>nbrel) break;
556
        gel(M,++rel) = gel(L,j);
557
        if (DEBUGLEVEL && (rel&511UL)==0)
558
          err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
559
      }
560
      av = avma;
561
    }
562
    else set_avma(av);
563
    if (rel>nbrel) stop = 1;
564
    i++;
565
  }
566
  mt_queue_end(&pt);
567
  if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
568
  return M;
569
}
570

571
static GEN Flxq_log_Coppersmith_d(GEN W, GEN g, long r, GEN T, ulong p, GEN mo);
572

573
static GEN
574
Flxq_log_from_rel(GEN W, GEN rel, long r, GEN T, ulong p, GEN m)
575
{
576
  pari_sp av = avma;
577
  GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
578
  long i, l = lg(F);
579
  for(i=1; i<l; i++)
580
  {
581
    GEN R = gel(W, F[i]);
582
    if (signe(R)==0) /* Already failed */
583
      return NULL;
584
    else if (signe(R)<0) /* Not yet tested */
585
    {
586
      setsigne(gel(W,F[i]),0);
587
      R = Flxq_log_Coppersmith_d(W, cindex_Flx(F[i],r,p,T[1]), r, T, p, m);
588
      if (!R) return NULL;
589
    }
590
    o = Fp_add(o, mulis(R, E[i]), m);
591
  }
592
  return gerepileuptoint(av, o);
593
}
594

595
static GEN
596
Flxq_log_Coppersmith_d(GEN W, GEN g, long r, GEN T, ulong p, GEN mo)
597
{
598
  pari_sp av = avma, av2;
599
  long dg = degpol(g), k = r-1, m = maxss((dg-k)/2,0);
600
  long i, j, l = dg-m, N;
601
  GEN v = cgetg(k+m+1,t_MAT);
602
  long dT = degpol(T);
603
  long h = dT/p, d = dT-h*p;
604
  GEN R = Flx_rem(Flx_shift(pol1_Flx(T[1]), dT), T, p);
605
  GEN z = Flx_rem(Flx_shift(pol1_Flx(T[1]), h), g, p);
606
  for(i=1; i<=k+m; i++)
607
  {
608
    gel(v,i) = Flx_to_Flv(Flx_shift(z,-l),m);
609
    z = Flx_rem(Flx_shift(z,1),g,p);
610
  }
611
  v = Flm_ker(v,p);
612
  for(i=1; i<=k; i++)
613
    gel(v,i) = Flv_to_Flx(gel(v,i),T[1]);
614
  N = upowuu(p,k);
615
  av2 = avma;
616
  for (i=1; i<N; i++)
617
  {
618
    GEN p0,q,qh,a,b;
619
    ulong el = i;
620
    set_avma(av2);
621
    q = pol0_Flx(T[1]);
622
    for (j=1; j<=k; j++)
623
    {
624
      ulong r = el % p;
625
      el /= p;
626
      if (r) q = Flx_add(q, Flx_Fl_mul(gel(v,j), r, p), p);
627
    }
628
    qh = Flx_shift(q, h);
629
    p0 = Flx_rem(qh, g, p);
630
    b = Flx_sub(Flx_mul(R, Flx_frob(q, p), p), Flx_shift(Flx_frob(p0, p), d), p);
631
    if (lgpol(b)==0 || !Flx_is_smooth(b, r, p)) continue;
632
    a = Flx_div(Flx_sub(qh, p0, p), g, p);
633
    if (degpol(Flx_gcd(a, q, p)) &&  degpol(Flx_gcd(a, p0 ,p)))
634
      continue;
635
    if (!(lgpol(a)==0 || !Flx_is_smooth(a, r, p)))
636
    {
637
      GEN F = factorel(b, p);
638
      GEN G = factorel(a, p);
639
      GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2*p), gel(G, 1));
640
      GEN E  = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
641
          zv_z_mul(gel(G, 2),-p));
642
      GEN R  = famatsmall_reduce(mkmat2(FG, E));
643
      GEN l  = Flxq_log_from_rel(W, R, r, T, p, mo);
644
      if (!l) continue;
645
      l = Fp_divu(l,p,mo);
646
      if (dg <= r)
647
      {
648
        long idx = Flx_cindex(g, p);
649
        affii(l, gel(W, idx));
650
        if (DEBUGLEVEL>1) err_printf("Found %lu\n", idx);
651
      }
652
      return gerepileuptoint(av, l);
653
    }
654
  }
655
  set_avma(av);
656
  return NULL;
657
}
658

659
static GEN
660
Flxq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, GEN T, ulong p, GEN m)
661
{
662
  GEN b = polx_Flx(T[1]);
663
  long AV = 0;
664
  GEN g = a, bad = pol0_Flx(T[1]);
665
  pari_timer ti;
666
  while(1)
667
  {
668
    long i, l;
669
    GEN V, F, E, Ao;
670
    timer_start(&ti);
671
    V = Flxq_log_find_rel(b, r2, T, p, &g, &AV);
672
    if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
673
    F = gel(V,1); E = gel(V,2);
674
    l = lg(F);
675
    Ao = gen_0;
676
    for(i=1; i<l; i++)
677
    {
678
      GEN Fi = cindex_Flx(F[i], r2, p, T[1]);
679
      GEN R;
680
      if (degpol(Fi) <= r)
681
      {
682
        if (signe(gel(W,F[i]))==0)
683
          break;
684
        else if (signe(gel(W,F[i]))<0)
685
        {
686
          setsigne(gel(W,F[i]),0);
687
          R = Flxq_log_Coppersmith_d(W,Fi,r,T,p,m);
688
        } else
689
          R = gel(W,F[i]);
690
      }
691
      else
692
      {
693
        if (Flx_equal(Fi,bad)) break;
694
        R = Flxq_log_Coppersmith_d(W,Fi,r,T,p,m);
695
        if (!R) bad = Fi;
696
      }
697
      if (!R) break;
698
      Ao = Fp_add(Ao, mulis(R, E[i]), m);
699
    }
700
    if (i==l) return subis(Ao,AV);
701
  }
702
}
703

704
static GEN
705
Flxq_log_index_Coppersmith(GEN a0, GEN b0, GEN m, GEN T0, ulong p)
706
{
707
  pari_sp av = avma;
708
  GEN  M, S, a, b, Ao=NULL, Bo=NULL, W, e;
709
  pari_timer ti;
710
  double rf = p ==3 ? 1.2 : .9;
711
  long n = degpol(T0), r = (long) sqrt(n*rf);
712
  GEN T;
713
  long r2 = 3*r/2;
714
  long nbi = itos(ffsumnbirred(utoipos(p), r)), nbrel=nbi*5/4;
715
  if (DEBUGLEVEL)
716
  {
717
    err_printf("Coppersmith: Parameters r=%ld r2=%ld\n", r,r2);
718
    err_printf("Coppersmith: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
719
    timer_start(&ti);
720
  }
721
  T = smallirred_Flx(p,n,get_Flx_var(T0));
722
  S = Flx_ffisom(T0,T,p);
723
  a = Flx_Flxq_eval(a0, S, T, p);
724
  b = Flx_Flxq_eval(b0, S, T, p);
725
  if (DEBUGLEVEL) timer_printf(&ti,"model change");
726
  M = Flxq_log_Coppersmith(nbrel, r, T, p);
727
  if (DEBUGLEVEL) timer_printf(&ti,"relations");
728
  W = check_kernel(r, M, nbi, 3*upowuu(p,r), T, p, m);
729
  timer_start(&ti);
730
  Ao = Flxq_log_Coppersmith_rec(W, r2, a, r, T, p, m);
731
  if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
732
  Bo = Flxq_log_Coppersmith_rec(W, r2, b, r, T, p, m);
733
  if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
734
  e = Fp_div(Ao, Bo, m);
735
  if (!Flx_equal(Flxq_pow(b0,e,T0,p),a0)) pari_err_BUG("Flxq_log");
736
  return gerepileupto(av, e);
737
}
738

739
GEN
740
Flxq_log_index(GEN a, GEN b, GEN m, GEN T, ulong p)
741
{
742
  long d = get_Flx_degree(T);
743
  if (p==3 || (p==5 && d>41))
744
    return Flxq_log_index_Coppersmith(a, b, m, T, p);
745
  else    return Flxq_log_index_cubic(a, b, m, T, p);
746
}
747

748
int
749
Flxq_log_use_index(GEN m, GEN T, ulong p)
750
{
751
  long d = get_Flx_degree(T);
752
  if (p==3 || (p==5 && d>41))
753
    return 1;
754
  else if (d<=4 || d==6)
755
    return 0;
756
  else
757
    return Flxq_log_use_index_cubic(m, T, p);
758
}
759

760
Product

Resources

Company
