polredabs(,16)

[Igor Schein <igor@txc.com>]

Hi,

here's my typical case:

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
? \g1
   debug = 1
? polredabs(x^5 - x^4 - 12040781642129393071473904079660253048973811141573673202071693733789883279680587178494462996841316092777725721420479505331283827775*x^3 - 116300336972049690721017379544011576959110565146852966482595449932712559384985831383994266783651912069750389914648201847477549301891914579908523180930736074973601542737568062514475655562681165257*x^2 + 28923689262054691329826006244861882371486999095000166029365674110538452285217184588858628779585349092052020333450432011025074302859688823005297537508940396134093079707594458414327414841760790952734653966377901305736384509781946321196510075808623517993691862754*x + 603824510472333552906408309566519552483702548276229044880954577047602509786254891391799969614095483303548612156918564165324598251084001744566522007323003494588591405487402336312858426924318657537215114711342084660305244042075747811000122705478017654708300091827976086505455932507386781142134969661181915101523617253014533937,16)
Time disc. factorisation: 240
Treating p^k = 3^8
Treating p^k = 7^6
Treating p^k = 271^2
Treating p^k = 1423^2
Treating p^k = 2707^2
Treating p^k = 355642239075589000610214014392342847624285693955090637690648165981902348024803142925390999505584901053583715988860062506117335188128489834547093461463952922390046933948239957380668839040005211719849468567850039487073433542620760399881755655969738572401308529284815827883545228055482072406280923156187830154818972962265325157291024849881256555945028388202739559270770532380850791416481756274085220462659108803165966991536361997787269686208749198339151439050815670124685307181277257940378761510259440446996919814293566575666958284384194468634459280340124185860319036132179717528683600233773181036685406425769997209769167857650032626779949^2
  ***   Warning: impossible inverse: Mod(62277548538789561520401660217885073427574453048708934544094318214969928190701341602751, 355642239075589000610214014392342847624285693955090637690648165981902348024803142925390999505584901053583715988860062506117335188128489834547093461463952922390046933948239957380668839040005211719849468567850039487073433542620760399881755655969738572401308529284815827883545228055482072406280923156187830154818972962265325157291024849881256555945028388202739559270770532380850791416481756274085220462659108803165966991536361997787269686208749198339151439050815670124685307181277257940378761510259440446996919814293566575666958284384194468634459280340124185860319036132179717528683600233773181036685406425769997209769167857650032626779949).
Treating p^k = 62277548538789561520401660217885073427574453048708934544094318214969928190701341602751^2
Treating p^k = 5710601130262493982874450316565825495165045130102777933367476011520353031709000897843018129737663422647788965256555811440586444074733529945639975518616318451965156181969984375944022502658751058133290214379999447672732954810258745045434613907135176929472475141795295473650186975005011971767434254591274144482951509383985181683434512355180512271475791867669579180730136796049701004125942482268419545635060361587599286598961331223459969844696435774835549958157589776773711166689075805418032893523603791328684081403330357539692341054153564694608827207699^2
  ***   Warning: impossible inverse: Mod(62277548538789561520401660217885073427574453048708934544094318214969928190701341602751, 5710601130262493982874450316565825495165045130102777933367476011520353031709000897843018129737663422647788965256555811440586444074733529945639975518616318451965156181969984375944022502658751058133290214379999447672732954810258745045434613907135176929472475141795295473650186975005011971767434254591274144482951509383985181683434512355180512271475791867669579180730136796049701004125942482268419545635060361587599286598961331223459969844696435774835549958157589776773711166689075805418032893523603791328684081403330357539692341054153564694608827207699).
Treating p^k = 62277548538789561520401660217885073427574453048708934544094318214969928190701341602751^2
Treating p^k = 91695984576297940629091069401042460650120597087319631764207283103899515544084709290863922393355280619668585159475593578878213307647994696419557596826269279805542663166576348258775815367233592614817390308317790064936650418380672544807231875119540099634407725209485016585330347793739939645066398102286451272751117239792049645810409362439518436982322765685948495055885162760592148619210759929508925358598803952888646046860197017898245782850365441390398853312591947949^2
  ***   Warning: impossible inverse: Mod(62277548538789561520401660217885073427574453048708934544094318214969928190701341602751, 91695984576297940629091069401042460650120597087319631764207283103899515544084709290863922393355280619668585159475593578878213307647994696419557596826269279805542663166576348258775815367233592614817390308317790064936650418380672544807231875119540099634407725209485016585330347793739939645066398102286451272751117239792049645810409362439518436982322765685948495055885162760592148619210759929508925358598803952888646046860197017898245782850365441390398853312591947949).
Treating p^k = 62277548538789561520401660217885073427574453048708934544094318214969928190701341602751^2
Treating p^k = 1472376269261547935712189695539879328360809097620894436978760078026276621446058365630718840298650018568789021488866567664808642593143353610974263185449536403914590340670273060128389858837876003705500814424556759675204694832775638453519384652993175257172676072689020732696406957201737571362701496443662427952926375988307434332700437795258349830052177045120085511801522828780375699^2
  ***   Warning: impossible inverse: Mod(62277548538789561520401660217885073427574453048708934544094318214969928190701341602751, 1472376269261547935712189695539879328360809097620894436978760078026276621446058365630718840298650018568789021488866567664808642593143353610974263185449536403914590340670273060128389858837876003705500814424556759675204694832775638453519384652993175257172676072689020732696406957201737571362701496443662427952926375988307434332700437795258349830052177045120085511801522828780375699).
Treating p^k = 62277548538789561520401660217885073427574453048708934544094318214969928190701341602751^2
Treating p^k = 23642168065502427460832177385115391357004888711017495437608479291958208410578829068974381528090217024884400190356117806360635728812506239926993755815139299785031355993473782894532129150801270234071221736459847468685201574675481268751607504101405327137501861498901290350554592826817455533115949^2
Time round4: 10
Time LLL basis: 80
chk_gen_init: new prec = 37 (initially 38)
smallvectors looking for norm <= 2.40815632 E130
final sort & check...
1 minimal vectors found.
x^5 - x^4 - 12040781642129393071473904079660253048973811141573673202071693733789883279680587178494462996841316092777725721420479505331283827775*x^3 - 116300336972049690721017379544011576959110565146852966482595449932712559384985831383994266783651912069750389914648201847477549301891914579908523180930736074973601542737568062514475655562681165257*x^2 + 28923689262054691329826006244861882371486999095000166029365674110538452285217184588858628779585349092052020333450432011025074302859688823005297537508940396134093079707594458414327414841760790952734653966377901305736384509781946321196510075808623517993691862754*x + 603824510472333552906408309566519552483702548276229044880954577047602509786254891391799969614095483303548612156918564165324598251084001744566522007323003494588591405487402336312858426924318657537215114711342084660305244042075747811000122705478017654708300091827976086505455932507386781142134969661181915101523617253014533937
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

The polynomial is not reduced, and the only way I know about it is if
I run at \g, otherwise it's completely silent.  I would like to have
an option to have
62277548538789561520401660217885073427574453048708934544094318214969928190701341602751
from the example above factored:

? factor(62277548538789561520401660217885073427574453048708934544094318214969928190701341602751)

[524351 15]

So basically, leave polredabs(,16) behave as it does now, and have,
say, polredabs(,24) factor JUST the composites that appear in
impossible inverse.

I hope I'm making myself clear.  Right now, it's a lot of manual work
for me, when from, say thousands of polynomials I get, say, 100
polynomials as above.  The way I handle it now is run polredabs(,16)
on all non-reduced polynomials at \g1, grep for impossible inverse
warnings, extract composites to factor, factor them, do addprimes on
the prime factors and then rerun polredabs(,16) - unnecessarily messy
prcedure.  For polynomials that I'm dealing with right now, the
composite to factor is always a high power of a prime, and often a
prime large than 2^31-1, so increasing primelimit is of no help. 

Thanks

Igor