第4章-数论初步和有限域-2014.ppt

*Wecanextendtheanalogybetweenpolynomialarithmeticoverafieldandintegerarithmeticbydefiningthegreatestcommondivisorasshown.*Considernowthecaseofpolynomialarithmeticwithcoordinatesmod2andpolynomialsmodanirreduciblepolynomialm(x).ThatisModularPolynomialArithmeticusesthesetSofallpolynomialsofdegreen-1orlessoverthefieldZp.Withtheappropriatedefinitionofarithmeticoperations,eachsuchsetSisafinitefield.Thedefinitionconsistsofthefollowingelements:Arithmeticfollowstheordinaryrulesofpolynomialarithmeticusingthebasicrulesofalgebra,withthefollowingtworefinements.2.Arithmeticonthecoefficientsisperformedmodulop.3.Ifmultiplicationresultsinapolynomialofdegreegreaterthann-1,thenthepolynomialisreducedmodulosomeirreduciblepolynomialm(x)ofdegreen.Thatis,wedividebym(x)andkeeptheremainder.Thisformsafinitefield.AndjustastheEuclideanalgorithmcanbeadaptedtofindthegreatestcommondivisoroftwopolynomials,theextendedEuclideanalgorithmcanbeadaptedtofindthemultiplicativeinverseofapolynomial.*ExampleshowsadditionmultiplicationinGF(23)modulo(x3+x+1),fromStallingsTable4.6.*Showhereafewsimpleexamplesofaddition,multiplicationmoduloreductioninGF(23).Notethelongformmoduloreductionfindsp(x)=q(x).m(x)+r(x)withr(x)beingthedesiredremainder.*Showhereafewsimpleexamplesofaddition,multiplicationmoduloreductioninGF(23).Notethelongformmoduloreductionfindsp(x)=q(x).m(x)+r(x)withr(x)beingthedesiredremainder.X的幂乘运算可以重复应用xtime来实现。对任意常数的乘法可以通过对中间结果相加来实现。*利用上面的结论，如果两数相乘，可以重复多次x乘，结果相加。**换句话说，多项式的加法就是4字节向量的逐比特异或。**模P，******如果将a，b都表示为素数的乘积，则gcd(a,b)极易确定。例如： 300=22×31×52 18=21×32 gcd(18,300)=21×31×50=6*如果将a，b都表示为素数的乘积，则gcd(a,b)极易确定。例如： 300=22×31×52 18=21×32 gcd(18,300)=21×31×50=6********************