Re: rnfpolredbest for larger polynomials

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

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]
`