Re: bnfisintnorm() is eager for memory

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

* Max Alekseyev [2024-02-23 02:21]:
> In the following example, bnfisintnorm() runs out of memory even with a
> 32GB stack. Is there a way to overcome this?
> 
> ? b = bnfinit('x^2-2305843005992468481,1)
> ? bnfisintnorm(b,2305843008139952128)

Not really with the current specification for the function. One could
easily obtain the solutions as "algebraic numbers in factored form", but have
a look at the simplest such solution 'y', attached to this mail:

? nfeltnorm(b, y)
%1 = 2305843008139952128

y is given by a factorization matrix, corresponding to an expression
\prod_i {y_i}^{e_i}, where the y_i are small algebraic integers and the
e_i are (positive or negative) integers.

Check the exponents y[,2]: its a vector with length 151 and sup-norm
5345503542932135311077290.

It's (relatively) easy to get all solutions in this form, with exponents
e_i of that magnitude. It's a completely explicit and well defined
expression, but no hope of expanding that as the expected t_POLMOD.

A related difficulty: b.fu has a hard time finishing as well, about 2
minutes. The result has coefficients about exp(b.reg) ~ 10^6103581
and requires about 5 MB of storage (more than 5 times the size of the
original full bnf, which contains the same data in factored form and is
computed in 0.1 s). 

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/

b = bnfinit('x^2-2305843005992468481,1)

y=[[89478486, 1]~, -1; 1073741824, 1; [1, 2]~, -1; 2147483647, 1; [-298261617, 1]~, -1; 6227199465703601, 1; 2, -5345503542932135311077290; 5, 195325679348395623979581; 7, -916652602232130680163063; 11, -2074472776674611340705506; 19, -4802741365413093437625561; 31, -193387559932788863817; 37, -1539817292920700794612842; 43, -422296570364442926507439; 47, 4397425459723093090438160; 59, 3504608496518269834118; 67, -99047330267875580075602; 73, 639893142246514431733354; 83, 45615682764789454209; 89, 3496257634672873536157; 97, -86245378015097205116990; 101, -35303185290713329265; 127, 64389396361227979280; 131, -168517042636058753056; 137, -20456729318051768527; 139, -52274778095919388419; 151, -39924491058462593978; 157, -2898942559755157307013370; 163, 233244713203444476143; 173, -156381276773372056346; 179, 147197569399994695006; 191, -101844855223869235415; 193, 188825167296670300790; 199, 116395998223901085937; 223, -61961400499525211071; 227, -916322716407691214276729; 229, 2197177279202901367638031; 281, 76863436430072419797; 307, 2197026289587486424920630; 331, -25088327920778249731; 401, -184387177353338541628; 419, -97567784705716584623; 431, 49629784694278110383; 439, -160765299086952298199; 443, 27936941494515839351; 449, 5548728488951088467; 461, 14293600660018493190; 463, -83005176458890047934; 467, 210722541082032626349; 479, -132993786465810800678; 487, -42337954338894531856; 547, -145800870823953933233; 557, -118308361749603377199; 563, -2619528697060642653625053; 593, -735728236490215227066769; 599, 47175544935296005424; 601, -735426719381423142885714; 643, 9084908910957721540; 659, 77957126048185582473; 661, 133859104651960206552; 673, 25051039443; 677, -916527516169664807093027; 739, 13091496229971863529; 769, 76863436430072419797; 773, 117988969934680417980; 827, 1266637427903557816880066; 829, 636515470764688589020473; 839, 156381276773372056346; 857, 3442987348206210157810; 863, 1266687604559399373379528; [-2818413899045891410568, 16749657944168]~, -1266519219972656235285035; [-3348821638970358282422, 13406166771439]~, -636515470764688589020473; [-3348821652376525053861, -13406166771439]~, -636681308042330767780001; [-2074538583858736034186, -31068744600143]~, 2619241339730926434908851; [-2074538552789991434043, 31068744600143]~, 2619204026489483832603414; [3941941990145625246460, 10050538308730]~, 735540281880969402256823; [3941941980095086937730, -10050538308730]~, 735567471191128274768570; [7089559957648612172340, 28491760590670]~, 916527516169664807093027; [7089559929156851581670, -28491760590670]~, 916647829502130064182264; [8483336762656675027910, 7307568865705]~, -2196979114042551128915206; [8483336755349106162205, -7307568865705]~, -2197089084271143371221013; [2020332586201903605102, -12295551451099]~, 61961400499525211071; [3566046554683370104340, 39866464656670]~, 35303185290713329265; [25187677096299735083574, -8904987353263]~, -77957126048185582473; [2586349938548754354598, -10520994396551]~, -127936325543520396501; [24359326552282594333922, -41507238358189]~, 233244713203444476143; [9043422608899050312036, -74852214024682]~, 42337954338894531856; [485890538573459393026, 47850112546563]~, -7542767741020775062; [7025264221850614743250, -16058215997125]~, 17699135784705004806; [-1409206957897774677368, -8374828972084]~, -1266687604559399373379528; [-5157860815563725530976, -4959990294288]~, -5548728488951088467; [-19269518779467873661090, -35518641303795]~, -122196416573370844664; [-13610337272440976915290, 46850482234105]~, -89967301079491696353; [-20680899936519116374774, -90391916852337]~, 83005176458890047934; [27815969095210688830934, -23745812811583]~, -13567729686957603193; [17943795017208815663664, 138688702985032]~, 184387177353338541628; [-8003968821543619743832, -98952796048516]~, 178708291653941655212; [-9211781941703776526662, 36570538487319]~, -227988194125821992307; [16317172977327782626382, -98704309976459]~, -156381276773372056346; [28562609717656898831378, 63994546893339]~, -76863436430072419797; [-9165090557948958955686, 5063047801607]~, -147197569399994695006; [-36724257042508151146252, -144482338158226]~, 101844855223869235415; [-18732187533746978518874, -46363679066887]~, -260126560849763933896; [-4393806007344582210414, -16907715877157]~, -42337954338894531856; [1650769581929806033934, -18729837935083]~, 61961400499525211071; [25560997407522840083796, 34965192499198]~, -235145793359358209182; [-14221061975659423737442, -52663690119571]~, -27936941494515839351; [10380418292011130596624, -65714595600488]~, -24981418793796815618; [-14156175148505497664774, 47447286252663]~, 51072889113447976704; [11584263346404844382814, 57256281833357]~, -47175544935296005424; [16764287671134121412122, -64659472784089]~, 50176655841556499462; [20979834773803058945900, 88526439580450]~, 75869976562687063175; [40946748260268363924150, -154696620424175]~, 274354478432830237981; [-19339555855100100017554, 11742594724773]~, 97567784705716584623; [-14223637099898573879340, 21022416080830]~, 97567784705716584623; [25375814980301109192630, 151932602034065]~, 63197514381235713576; [-33504828725305151933174, -6619352551537]~, -131399857979575240728; [14031340983860510235648, -99111346059776]~, -13091496229971863529; [15093338612921985378176, -48300995922112]~, 106019731805238596047; [-11712664651730592702998, 29389317552351]~, 83005176458890047934; [12488983397244369059882, 6347083977791]~, -133859104651960206552; [-19548865231825414875782, -86842802743241]~, -97298777118908541124; [-29194906838684968508284, 18928025449158]~, 42337954338894531856; [15929604695926823091518, -61011510957091]~, 145800870823953933233; [-36194651169504706429730, 65730942679885]~, 267997287397324777897; [45823679515677008847696, -191998238361352]~, 187954609245824809946; [-1727730180108118604928, 46680287011136]~, 71032385966285589607; [-15436980801077524021958, -47573142105129]~, -62794683656946300383; [-87660288172705925241104, -100073580345752]~, -75869976562687063175; [23343619381890254656788, -3640526404706]~, 7542767741020775062; [16541321415586880662830, -26120891595835]~, -28444951229851659845; [29860829556001858508680, 59326889963340]~, -77957126048185582473; [13411708725212755700646, -88689199381127]~, -210722541082032626349; [42403828784632813459650, -66707282568925]~, -15870134717279788572; [-49284269531826357311758, -38944633115029]~, -120313332465257089237; [-16265732270180346877192, 40009159666804]~, 118308361749603377199; [-59368518277062942017150, -77154961147325]~, 62794683656946300383; [-3666162678468844922826, 179583282323537]~, -76863436430072419797; [7501065022282909136270, 30606216012885]~, -117988969934680417980; [-16352782606499824448192, 66773928206304]~, 15870134717279788572; [30762193224976057862276, -149202754037562]~, -113562499546259371109; [15579038985225198233206, -176196435936847]~, 160765299086952298199; [-13372932880445635093360, 102494474735320]~, -118207930901581595031; [12705026130245523594644, -51502284162978]~, 165837277642178759528; [4838746501997452959838, 4454106493069]~, 13567729686957603193; [846577213893529402299227371648, 37873742093358887308224]~, -3462347390525104096115; [846577176019787308940340063424, -37873742093358887308224]~, -3433902439295252436270; [-764060995979611397861200, 1468541463259400]~, 19360042318893938305; [-764060997448152861120600, -1468541463259400]~, -9084908910957721540; [61737302, 1]~, 21472319522; [61737301, -1]~, -25051039443]