Re: Targeting low degree factors of division polynomials

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Richard in Reading [2013-06-14 13:46]:
> In a previous email Karim mentions that in principle it's possible for
> the polynomial factorization process to find low degree factors at an
> earlier stage but in practice they'll find all the factors
> simultaneously.

By "in practice", I meant, "generically, most of the time, on average"
(i.e. this was not meant to convey a precise mathematical statement,
rather my general expectation :-)

> Looking at the log for the following commands using \g5
> 
> e=ellinit("784h1");f=factor(elldivpol(e,128)/elldivpol(e,64));

Minor preliminary points : 

1) I just committed a fix for the problem I reported in modular factorization
(using Berlekamp and a few minutes instead of a straightforward
Cantor-Zassenhaus, much faster in this range)

2) the following function will save some time.
\\ elldivpol(e, 2*m) / elldivpol(e, m)
F(e,m)=
{
  my(A = elldivpol(e,m+2));
  my(B = elldivpol(e,m-1));
  my(C = elldivpol(e,m-2));
  my(D = elldivpol(e,m+1)); (A*B^2 - C*D^2)/elldivpol(e,2);
}

  (18:13) gp > f = elldivpol(e,128)/elldivpol(e,64);
  time = 3min, 54,311 ms.
  (18:17) gp > g = F(e,64);
  time = 5,584 ms.
  (18:17) gp > g == f
  %5 = 1

> the two factors of degree 64 are found under the line
> "### K = 1, 96 combinations"
> and the factor of degree 128 is found under the line
> "### K = 2, 4371 combinations"
> the remaining factors of degree 256,512,1024,2048 and 2048 are found at the end after the LLL step.
> 
> So this is an example of low-degree factors being found more easily.

Yes. Luckily, out of the 96  3-adic factors, two factors of degree 64 turn
up to actually be rational, and two more combine to form a rational 128-th
degree factor.

A summary of printed timings (in milliseconds):

Time setup: 32178                      \\ = factoring mod various primes
Time Hensel lift (mod 3^13757): 299812
                                       \\ <-- at this point we find 3 factors
Time LLL: 3211
Time Check Factor: 103323
Total Time: 441833

So out of 441s, we could have saved about 106s (LLL + check factor), in this
particularly lucky case.

> Without me having to trawl through the source code to work out how the
> factoring works, could someone please infer from the log file what must be
> happening to drop these small factors out early so I can attempt to exploit
> this when factoring much larger degree division polynomials? 

Maybe more theory about division polynomials will help to predict / exploit
such cases. Why would 128 points of exact order 128 on this precise curve
happen to be defined over a degree 128 extension ? (so far, I have no
bright idea...)


Going back to the generic problem of factoring "abstract" polynomials,
without a hint about their origin, one could save the final "check
factor" if we modify the code to allow "bounded-degree factorization"
analogously to factor(N, B) for integers N (which looks for prime
factors <= B). We could look for polynomial factors of "bounded by B"
for polynomial inputs, say

- factors of degree bounded by B ? (most logical, hard to implement)

- or rational factors which are products of at most B modular (p-adic) factors ?
  (not very natural, dependent on p, trivial to implement)

- or ???

I'm at a loss to suggest a sensible interface... Both suggestions above
would save at most 106s out of 441s in this example, though.


Maybe the simplest is to forget about factor() entirely and
use 
  factormod() + polhensellift() + naive recombination 
yourself, using heuristic bounds, and trying to recognize factors by checking
divisibility modulo some big prime only ?

  g = F(e,64);
  p = 3;
  bigp = nextprime(10^30);
  N = 500;
  gp = factorcantor(g, p)[,1];
  GP = centerlift(polhensellift(g, lift(gp), p, N) * Mod(1,p^N));
  lc = pollead(g) * Mod(1,bigp); gbigp *= lc; GPbigp *= lc;
  for (i=1,#GP, print1(i," "); if (gbigp % GPbigp[i] == 0, print("BINGO")));

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 BINGO
25 26 27 28 29 30 BINGO
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 

Total time: 20s to find the 2 factors of degree 64 (and you can
generalize with combination of 2 or 3 factors without complicating the code
too much). Of course, I'm proving nothing:

- I could have missed some factors (I use a coefficient bound of 3^500 instead
  of 3^13757)

- the factors I found mod bigp might not be true rational factors.

But I in fact have those two factors in less than 20 seconds instead of 400 :-)
(And I could check them rigorously at some extra cost, by attempting a
true division over Q...)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`