密码学LECTURE3

《密码学LECTURE3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、NumberTheoryBasicsILecture3NumbersIntegersRealArithmeticOperationsAdditionandsubtractionMultiplicationanddivisionExponentiationandlogarithmTheGeometryofNumbersInfinity0MappingLineontoCircleStereographicProjectionone-to-onemappingxP(x)MappingLinetoCircleWraparoundModulararithmeticModular

2、Arithmetica=bmodmiff(a-b)=km+bforsomemZmtheequivalenceclassundermodm[a]mCanonicalform:Zm={0,1,2,…,m-1},weusethepositiveremainderasthestandardrepresentationModularArithmetic-1=m-1modmZ7={0,1,2,3,4,5,6}(Zm,+,,0,1)definesaring+,areclosedassociativeandcommutativeOperationdistributesover+

3、0istheidentityfor+and1forAdditiveinverseandmultiplicativeinverseMultiplicativeInversesandCongruenceEquationsWhendoesanumberhasamultiplicativeinverse?Whendoesacongruenceequationax=bmodmhasasolutionhasauniquesolution5x=8mod12==>x=43x=8mod12==>nosolution3x=9mod12==>xin{3,7,11}GreatestComm

4、onDivisor(GCD)gcd(12,15)=3gcd(12,25)=1,relativeprimeTheorem:ax=bmodmhasauniquesolutionforeverynumberbinZmiffgcd(a,m)=1ProofConsiderthemap:Pa(x)=ax.Supposexyandax=aymodmthena(x-y)=0modm.Soifgcd(a,m)=1,thenx=ymodm.Therefore,itisabijection.Therefore,everyax=bmodmhasauniquesolutionInpartic

5、ularax=1modmhasasolution,whichimpliesthatahasaninverseMultiplicationGroupZ*m={a:gcd(a,m)=1}Eulerphifunctionf(m)=

6、Z*m

7、Ifmisaprimethenf(m)=m-1,andf(md)=md-md-1Euclid’sAlgorithm(Firstnon-trivialalgorithmknown)GCD(r0,r1)=GCD(r1,r0-r1)=GCD(r1,r0modr1)Eachiteration,thetotalnumberofbitsinthet

8、wonumbersisreducedbyatleast1==>numberofrecursionisO(

9、input

10、)Division,naively,takesO(

11、input

12、2)operations.FFTmethodforDivision:O(

13、input

14、log(

15、input

16、))AsamplerunGCD(75,28)75=228+1928=119+919=29+19=91GCD(75,28)=1,relativeprimeBreakdownsGCD(r0,r1)GCD(r0,r1)=GCD(rm-1,rm)=rmr0=q1r1+r2r1=q2r

17、2+r3…rm-2=qm-1rm-1+rmrm-1=qmrmGCD(r0,r1)=GCD(rm-1,rm)=rmComputingMultiplicativeInverser1-1modr0existsiffGCD(r0,r1)=1==>rm=1Wouldliketofinetsuchthatr1t=1modr0Recursivelyfindr1tk=rkmodr0t0=0,t1=1,andtk=tk-2-qk-1tk-1modr0AsamplerunGCD(75,28)75=228+1928=119+919=29+19=91GCD(75,2