A-study-of-Coppersmiths-block-Wiedemann-algorithm-

RAPPORTDERECHERCHEAstudyofCoppersmith’sblockWiedemannalgorithmusingmatrixpolynomialsG.VillardNo975IMAvril97ResumeNousanalysonsunalgorithmeprobabilisteparblocs,proposeparCoppersmith,pourlaresolutiondegrandssystemeslineairescreuxAw=0donnessuruncorpsniK=GF(q).Cetalgorithmeestunemodicationd’unalgorithmedeWiedemann.Coppersmithajustiesamethodeparplusieursargumentsheuristiques.Unequestionouverteetaitdedemontrerquel’algorithmepeuteectivementfournirunesolution,avecuneprobabilitestrictementplusgrandequezero,surlescorpsdepetitecardi-nalitetelsqueK=GF(2).Nousrepondonsalaquestionapeuprescompletement.L’algorithmeutilisedeuxmatricesXetYdedimensionsmNetNn.Suruncorpsniquelconque,nousexpliquonscommentlesparametresmetnpeuvent^etrereglesdemaniereaceque,pourunsystemequelconqueenentree,unesolutionsoitproduiteavecunebonneprobabilite.Inversement,pourcertainssystemesparticuliersditsnonpathologiques,nousmontronsquelescontraintessurmetnpeuvent^etrerel^acheesencontinuantd’assurerunebonneprobabilitedereussite.Accessoirement,nousamelioronsunebornedonneeparKaltofendanslescasdescorpsnisagrandsnombresd’elements.Enn,pourrestercompletsdansnotregeneralisationdesetudesdeWiedemannaucasmatriciel,nousesquissonsrapidementuneversiondeterministedel’algorithmeparblocs.ASTUDYOFCOPPERSMITH’SBLOCKWIEDEMANNALGORITHMUSINGMATRIXPOLYNOMIALSGILLESVILLARDAbstract.WeanalysearandomizedblockalgorithmproposedbyCopper-smithforsolvinglargesparsesystemsoflinearequations,Aw=0,overaniteeldK=GF(q).ItisamodicationofanalgorithmofWiedemann.Coppersmithhasgivenheuristicargumentstounderstandwhythealgorithmworks.Butitwasanopenquestiontoprovethatitmayproduceasolution,withpositiveprobability,forsmallniteeldse.g.forK=GF(2).Weanswerthisquestionnearlycompletely.ThealgorithmusestworandommatricesXandYofdimensionsmNandNn.Overanyniteeld,weshowhowtheparametersmandnofthealgorithmmaybetunedsothat,foranyinputsystem,asolutioniscomputedwithhighprobability.Conversely,forcertainparticularinputsystems,weshowthattheconditionsontheinputparame-tersmayberelaxedtoensurethesuccess.WealsoimprovetheprobabilityboundofKaltofeninthecaseoflargecardinalityelds.Lastly,forthesakeofcompletenessofthegeneralizationofWiedemann’sworktothematrixcase,wewillbrieysketchadeterministicblockalgorithm.1.IntroductionTherandomizedmethodproposedbyCoppersmith[9]solveslargesparsesystemsofhomogeneouslinearequationsAw=0,w6=0.ThroughoutthepaperAwillbeasingularNNmatrixovertheGaloiseldwithqelementsK=GF(q)andwavectorofNunknowns.Onefundamentalapplicationofthisproblemisintegerandpolynomialfactorization,wheresuchlinearsystemsarisewithNover200;000[23,25,19].Thishasmotivatedseveralauthorstodevelopfastnite-eldcounterparttonumericaliterativemethods.Theconjugategradientmethodhasbeenusedin[23],theLanczosmethodin[23,12]andtheblockLanczosmethodin[8,29].Butuptonow,onlytheprobabilisticanalysisofWiedemann[39]wasgivingaprovablyreliableandecientmethodtosolveAw=0oversmallelds.ThismethodisbasedonndingrelationsinKrylovsubspacesusingtheBerlekamp-Masseyalgorithm[28].Thesameanalysiscouldbeappliedtoboundtheprobabilityofsuccessofthe(bi-orthogonal)Lanczosandconjugategradientalgorithmswithlook-aheadofLambert[24].Anyway,thesevariousapproachesareverysimilar:theycanbeunderstoodinauniedtheory[24].Butsincetheyusegeneratingpolynomialsofscalarsequences,theselatteralgo-rithmsimposelimitationsifonewantstoperformseveraloperationsatatime.Tosolvethisproblem,Coppersmith[9]modiestheapproachofWiedemannandusesLMC-IMAG,B.P.53F38041Grenoblecedex9,[e-mail],April23,1997.1991MathematicsSubjectClassication.Primary15A06,15A33;Secondary15-04,13P99.Keywordsandphrases.Sparselinearsystems,niteelds,exactarithmetic,probabilisticalgorithms,matrixpolynomials,minimalpolynomials.56GillesVILLARDmatrixsequences.Thisshouldbeviewedasablockversionofthesamealgorithm.Blocksenableonetotakeadvantageofsimultaneousoperations:eitherusingthemachinewordoverGF(2)[9]oraparallelmachine[18].Coppersmith’salgorithmisverypowerful[9,19,26]butraisestheoreticalquestions.Wearegoingtoanswersomeoftheminthispaper.Werefertox2forbasicdenitionsandtox3.1foradetailedpresentationoftheblockalgorithm.Weonlyconsiderthemethodintuitivelyinthisintroduction.IntheWiedemannalgorithm[39],onechoosesatrandomarowvectorxandacolumnvectoryandonecomputesthelowestdegreepolynomialg()=g0+g1+gddinK[]thatlinearlygeneratesthesequencehi=xAiy,0i2N1.Wemeanthatg()satisesforall0i2Nd1:g0hi+g1hi+1+:::+gdhi+d=x(g0Aiy+g1Ai+1y+:::+gdAi+dy)=0:Withhighprobability,thispolynomialistheminimalpolynomialyA()ofywithrespecttoAandissuchthatyA(0)=0(onedoesnotneedtheminimalpolynomialofAbutonlyafactorofit):yA()=gll+gl+1l+1+:::+gdd;0ld;gl6=0;8i;0i2Nd1:glAl+iy+gl+1Al+i+1y+:::+gdAd+iy=0:Takingw=glAl1y+:::+gdAd1yaboverelationshowsthatwisasolution:Aw=0.Insteadofvectorsxandy,themodiedalgorithmofCoppersmith[9]usesarandommatrixXwithmrowsandarandommatrixYwithncolumns.ItrstcomputesthesequenceofmnmatricesHi=XAiY;i=0;:::;L1withL=N=m+N=n+O(1).Byanalogywiththesca