The Great Trinomial Hunt

《The Great Trinomial Hunt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、TheGreatTrinomialHuntRichardP.BrentandPaulZimmermannIntroductionwhererandsaregivenpositiveintegers,r>s>0,Atrinomialisapolynomialinonevariablewiththreeandtheinitialvaluesz0;z1;:::;zr1arealsogiven.73Therecurrencethendenesalltheremainingtermsnonzeroterms,forexampleP=6x+3x5.Ifthe

2、coecientsofapolynomialP(inthiscase6;3;5)arezr;zr+1;:::inthesequence.insomeringoreldF,wesaythatPisapolynomialItiseasytobuildhardwaretoimplementtheoverF,andwriteP2F[x].Theoperationsofadditionrecurrence(1).AllweneedisashiftregistercapableofandmultiplicationofpolynomialsinF[x]are

3、denedstoringrbits,andacircuitcapableofcomputingtheintheusualway,withtheoperationsoncoecientsadditionmod2(equivalently,theexclusiveor")oftwoperformedinF.bitsseparatedbyrspositionsintheshiftregisterClassicallythemostcommoncasesareF=Z;Q;Randfeedingtheoutputbackintotheshiftregis

4、ter.ThisorC,respectivelytheintegers,rationals,realsorisillustratedinFigure1forr=7,s=3.complexnumbers.However,polynomialsoverniteeldsarealsoimportantinapplications.Werestrictourattentiontopolynomialsoverthesimplestnite!!!!!!eld:theeldGF(2)oftwoelements,usuallywrittenas0and1.

5、Theeldoperationsofadditionand!!!multiplicationaredenedasforintegersmodulo2,so!+!0+1=1,1+1=0,01=0,11=1,etc.Animportantconsequenceofthedenitionsisthat,!forpolynomialsP;Q2GF(2)[x],wehaveOutput222(P+Q)=P+QFigure1:Hardwareimplementationofbecausethecrossterm"2PQvanishes.Highscho

6、olzn=zn3+zn7mod2.algebrawouldhavebeenmucheasierifwehadusedpolynomialsoverGF(2)insteadofoverR!Therecurrence(1)lookssimilartothewell-knownTrinomialsoverGF(2)areimportantincryptogra-Fibonaccirecurrencephyandrandomnumbergeneration.Toillustratewhythismightbetrue,considerasequence(z

7、0;z1;z2;:::)Fn=Fn1+Fn2;satisfyingtherecurrenceindeedtheFibonaccinumbersmod2satisfyourre-(1)zn=zns+znrmod2;currencewithr=2,s=1.Thisgivesasequence(0;1;1;0;1;1;:::)withperiod3:notveryinteresting.RichardBrentisaprofessorattheMathematicalSciencesHowever,ifwetakerlargerwecangetmuc

8、hlongerInstituteoftheAustralianNationalUniversi