Aurel Page on Sat, 20 Jun 2020 16:01:12 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: rnfpolredbest for larger polynomials 

Hi Karim and Benjamin,
Could we call Round 2 when Round 4 with composite modulus seems to get stuck? Maybe it is a bit hard to decide when is a good time to do it. 

Cheers,
Aurel

On 19/06/2020 11:42, Karim Belabas wrote:

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