Re: rnfpolredbest for larger polynomials

[Benjamin Matschke <matschke@bu.edu>]

Hi Karim,

Thanks a lot!

> A solution would be to alternate between a number of ROUND4 loops and
> ECM-type factorizations which would strive to find "smallish" large factors
> for some bounded amount of time. And to give up when neither seems to work.

This sounds like a very good idea, presumably even for (rnf)polredbest
in general.

Best,
Benjamin

Le ven. 19 juin 2020 à 05:42, Karim Belabas
<Karim.Belabas@math.u-bordeaux.fr> a écrit :
>
> Hi Benjamin,
>
> * Benjamin Matschke [2020-06-19 04:16]:
> > rnfpolredbest seems to get slow for larger inputs, here is an example:
> >
> > f = y^4 + 3779*y^2 + 3575881
> > K = bnfinit(f)
> > g = x^3 + (-6/1891*y^3 - 11328/1891*y + 12)*x -
> > 185828205268604880664711758295687064824766032511727208226289638708278008/1891*y^3
> > - 4193788865327654200848261540592786277199048095680627005208368097895442*y^2
> > - 364061076121017004851315903951025443139463935963694411909316544669762680474/1891*y
> > - 7620275092346327331118337613708081210333545556068555805693518189928940204
> > g_reduced = rnfpolredbest(K,g) \\slow
>
> The underlying problem here is the following:
>
> T = x^12+48*x^10+1215555874761101125537810268967953841736223282879955682590773324177989820*x^9+648*x^8+30632008043979748363552818777992436811752826728574883201287487769285343464*x^7+738788042333112882145134143188977023476014770677496688188276711316507811615622174044748578132585575234165143001945921727313365615401868011818760*x^6+78768020684519352934850105429123408944507268730621128231882111406733740336*x^5+1773091301599470917148321943653544856342435449625992051651864107159618747877493217707396587518205380561996343204670212145552077476964483228362864*x^4-17960762901225368783003903267629032616403886697137147437481267086367399523735695578775243399153498173759016297775695600522276362451802481059998146168647195820252033812450674869704592074645075610991440288296824898576*x^3+1063854780959682550288993166192126913805461269775595230991118464295771248726495930624437952510923228337197805922802127287331246486178689937017632*x^2-21552915481470442539604683921154839139684664036564576924977520503640879428482834694530292078984197808510819557330834720626731634942162977272060789818924250466650320659284108570801116304558587635775234035081576870560*x+218323108597757356816370007679560788705316602458706378183831948603297113957467284158904352695741338140569781899238358367585333582313267102871478350375396563645877765785163790756406438812814709907184184409701434438316037663054434778512225162646251708831271021769288337532699380656595600;
>
> nfbasis([T, 500000]); \\ infinite loop
>
> addprimes([12198999209,28527455371,2154391156987]);
> nfbasis([T, 500000]); \\ instantaneous
>
> > Also in this example, L = rnfinit(K,g) runs into a large integer
> > factorization.
>
> This is normal and expected, see ??rnfinit, in particular the "Huge
> discriminants, helping rnfdisc" section
>
> > Would it in general be possible to have a version of rnfpolredbest
> > that returns some simplified polynomial within a given time frame?
>
> This is what the current implementation aims to achieve, but the above bug
> prevents it.
>
> > Perhaps it could make sense for large input polynomials g (as the one
> > above) to first reduce it greedily (with respect to some naive height
> > of g), say by adding elements of K to the primitive element of L/K,
> > and iterate in a gradient flow or simulated annealing way.
>
> I don't know how to do this. The algorithm must compute some approximation to
> the ring of integers and it does this by using a supposedly polynomial time
> algorithm (a variant of ROUND4 avoiding integer factorization, which would
> be necessary to compute the true ring of integers). The problem is that the
> algorithm is polynomial time only when fed actual primes and we run it on
> large composites expecting either a correct result or a quick "side exit"
> (a non invertible non-zero element in Z/NZ, which produces a factor of N).
> In this example, we get no result and no side exit.
>
> A solution would be to alternate between a number of ROUND4 loops and
> ECM-type factorizations which would strive to find "smallish" large factors
> for some bounded amount of time. And to give up when neither seems to work.
>
> Cheers,
>
>     K.B.
> --
> Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
> Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
> 351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
> F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
> `