离散数学数论-PPT.pptx

《离散数学数论-PPT.pptx》由会员分享，可在线阅读，更多相关《离散数学数论-PPT.pptx（127页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、离散数学数论2TheIntegersandDivisionOfcourse,youalreadyknowwhattheintegersare,andwhatdivisionisHowever:Therearesomespecificnotations,terminology,andtheoremsassociatedwiththeseconceptswhichyoumaynotknow、Theseformthebasicsofnumber theory、Vitalinmanyimportantalgorithmstoday(hashfunctions,cryptography,digitals

2、ignatures;ingeneral,on-linesecurity)、3ThedividesoperatorNewnotation:3|12TospecifywhenanintegerevenlydividesanotherintegerReadas“3divides12”Thenot-dividesoperator:5|12TospecifywhenanintegerdoesnotevenlydivideanotherintegerReadas“5doesnotdivide12”4Divides,Factor,MultipleLet a,bZ with a0、Defn、:a|b“adiv

3、idesb”:(c Z:b=ac)“Thereisanintegercsuchthatctimesa equalsb、”Example:312 True,but 37 False、Iffadividesb,thenwesayaisafactororadivisorofb,andbisamultipleofa、Ex、:“b is even”:2|b、Is 0 even?Is 4?5ResultsonthedividesoperatorIf a|b and a|c,then a|(b+c)Example:if 5|25 and 5|30,then 5|(25+30)If a|b,then a|bc

4、 for all integers cExample:if 5|25,then 5|25*c for all ints cIf a|b and b|c,then a|cExample:if 5|25 and 25|100,then 5|100(“mon facts”but good to repeat for background)6DividesRelationTheorem:a,b,c Z:1、a|02、(a|b a|c)a|(b+c)3、a|ba|bc4、(a|b b|c)a|cCorollary:If a,b,c are integers,such that a|b and a|c,t

5、hen a|mb+nc whenever m and n are integers、7Proofof(2)Show a,b,c Z:(a|b a|c)a|(b+c)、Leta,b,cbeanyintegerssuchthata|banda|c,andshowthata|(b+c)、Bydefn、of|,weknow s:b=as,and t:c=at、Lets,t,besuchintegers、Thenb+c=as+at=a(s+t)、So,u:b+c=au,namelyu=s+t、Thusa|(b+c)、QEDDividesRelationCorollary:Ifa,b,careintege

6、rs,suchthata|banda|c,thena|mb+ncwhenevermandnareintegers、Proof:Fromprevioustheorempart3(i、e、,a|ba|be)itfollowsthata|mbanda|nc;again,fromprevioustheorempart2(i、e、,(a|b a|c)a|(b+c)itfollowsthata|mb+nc9TheDivision“Algorithm”Theorem:DivisionAlgorithm-Letabeanintegeranddapositiveinteger、Thenthereareuniqu

7、eintegersqandr,with0rd,suchthata=dq+r、Itsreallyatheorem,notanalgorithmOnlycalledan“algorithm”forhistoricalreasons、q is called the quotient r is called the remainder d is called the divisor a is called the dividend 10Whatarethequotientandremainderwhen101isdividedby11?q is called the quotient r is cal

8、led the remainder d is called the divisor a is called the dividend 101=11 9+2Wewrite:q=9=101div11r=2=101mod11adqr11If a=7 and d=3,then q=2 and r=1,since 7=(2)(3)+1、If a=7 and d=3,then q=3 and r=2,since 7=(3)(3)+2、So:given positive a and(positive)d,in order to get r we repeatedly subtract d from a,as

9、 many times as needed so that what remains,r,is less than d、Given negative a and(positive)d,in order to get r we repeatedly add d to a,as many times as needed so that what remains,r,is positive(or zero)and less than d、12大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流Theorem:Di

10、vision“Algorithm”-Letabeanintegeranddapositiveinteger、Thenthereareuniqueintegersqandr,with0rd,suchthata=dq+r、Proof:Wellusethewell-orderingpropertydirectlythatstatesthateverysetofnonnegativeintegershasaleastelement、a)ExistenceWewanttoshowtheexistenceofqandr,withthepropertythata=dq+r,0rd Note:thisseti

11、snonemptysinceqcanbeanegativeintegerwithlargeabsolutevalue、Considerthesetofnon-negativenumbersoftheforma-dq,whereqisaninteger、Hmm、Canthissetbeempty?Bythewell-orderingproperty,Shasaleastelement,r=a-dq0、(Existence,cont、)risnon-negative;also,rd、otherwiseifrd,therewouldbeasmallernonnegativeelementinS,na

12、melya-d(q0+1)0、Butthena-d(q0+1),whichissmallerthana-dq0,isanelementofS,contradictingthata-dq0wasthesmallestelementofS、So,itcannotbethecasethatrd,provingtheexistenceof0rdandq、q is called the quotient r is called the remainder d is called the divisor a is called the dividend b)UniquenessSupposeWithout

13、lossofgeneralitywemayassumethatq Q、Subtractingbothequationswehave:d(q-Q)=(R r)(*)So,ddivides(R-r);so,either|d|(R r)|or(R r)=0、SincedR-rd(because)i、e、,|R-r|0、ThisensuresthatitwouldtakeexponentialtimeinthelengthofanIDforanopponentto“fake”adifferentdocumenthavingthesameID、ASimpleHashUsingmodLet the dom

14、ain and codomain be the sets of all natural numbers below certain bounds:A=aN|a alim,B=bN|b blimThen an acceptable(although not great!)hash function from A to B(when alimblim)is h(a)=a mod blim、It has the following desirable hash function properties:It covers or is onto its codomain B(its range is B

15、)、When alim blim,then each bB has a preimage of about the same size,Specifically,|h1(b)|=alim/blim or alim/blim、ASimpleHashUsingmodHowever,it has the following limitations:It is not very random、Why not?It is definitely not cryptographically secure、Given a b,it is easy to generate as that map to it、H

16、ow?We know that for any nN,h(b+n blim)=b、For example,if all as encountered happen to have the same residue mod blim,they will all map to the same b!(see also“spiral view”)But ok,if input data is uniformly distributed、CollisionBecause a hash function is not one-to-one(there are more possible keys tha

17、n memory locations)more than one record may be assigned to the same location we call this situation a collision、What to do when a collision happens?One possible way of solving a collision is to assign the first free location following the occupied memory location assigned by the hashing function、The

18、re are other ways for example chaining(At each spot in the hash table,keep a linked list of keys sharing this hash value,and do a sequential search to find the one we need、)DigitalSignatureApplicationMany digital signature systems use a cryptographically secure(but public)hash function h which maps

19、arbitrarily long documents down to fixed-length(e、g、,1,024-bit)“fingerprint”strings、Document signing procedure:Signature verification procedure:Given a document a and signature c,quickly find as hash b=h(a)、pute b=f 1(c)、(Possible if fs inverse f 1 is made public(but not f)、)pare b to b;if they are

20、equal then the signature is valid、Note that if h were not cryptographically secure,then an opponent could easily forge a different document a that hashes to the same value b,and thereby attach someones digital signature to a different document than they actually signed,and fool the verifier!Given a

21、document a to sign,quickly pute its hash b=h(a)、pute a certain function c=f(b)that is known only to the signer This step is generally slow,so we dont want to apply it to the whole document、Deliver the original document together with the digital signature c、What if h was not cryptographically secure?

22、31Pseudorandomnumbers32Pseudorandomnumbersputers cannot generate truly random numbers thats why we call them pseudo-random numbers!LinearCongruentialMethod:Algorithm for generating pseudorandom numbers、Choose 4 integersSeed x0:starting valueModulus m:maximum possible valueMultiplier a:such that 2 a

23、m Increment c:between 0 and mIn order to generate a sequence of pseudorandom numbers,xn|0 xn echo Hello World|rot13Uryyb Jbeyq echo Uryyb Jbeyq|rot13Hello WorldPrimesandGreatestmonDivisor41PrimenumbersApositiveintegerpisprimeiftheonlypositivefactorsofpare1andpIfthereareotherfactors,itispositeNotetha

24、t1isnotprime!ItsnotpositeeitheritsinitsownclassAnintegernispositeifandonlyifthereexistsanintegerasuchthata|nand1anFundamentaltheoremofarithmeticFundamentalTheoremofArithmetic:Everypositiveintegergreaterthan1canbeuniquelywrittenasaprimeorastheproductoftwoormoreprimeswheretheprimefactorsarewritteninor

25、derofnon-decreasingsizeExamples100=2*2*5*5182=2*7*1329820=2*2*3*5*7*71In a fundamental sense,primes are the building blocks of the natural numbers、Fundamentaltheoremofarithmetic:StrongInductionfrombeforeShow that if n is an integer greater than 1,then n can be written as the product of primes、1-Hypo

26、thesis P(n)-n can be written as the product of primes、2 Base case P(2)2 can be written a 2(the product of itself)3 Inductive Hypothesis -P(j)is true for 2 j k,j integer、4 Inductive step?a)k+1 is prime in this case its the product of itself;b)k+1 is a posite number and it can be written as the produc

27、t of two positive integers a and b,with 2 a b k+1、By the inductive hypothesis,a and b can be written as the product of primes,and so does k+1,QEDWhats missing?Uniqueness proof,soonpositefactorsTheorem:Ifn isapositeinteger,thennhasaprimedivisorlessthanorequaltothesquarerootofnProofSince n is posite,i

28、t has a factor a such that 1a n and b n,then ab n*n n、Contradiction、)Thus,n has a divisor not exceeding nThis divisor is either prime or a positeIf the latter,then it has a prime factor(by the FTA)In either case,n has a prime factor less than nQED45ShowinganumberisprimeE、g、,show that 113 is prime、So

29、lutionThe only prime factors less than 113=10、63 are 2,3,5,and 7None of these divide 113 evenlyThus,by the fundamental theorem of arithmetic,113 must be primeHow?46ShowinganumberispositeShow that 899 is posite、SolutionDivide 899 by successively larger primes,starting with 2We find that 29 and 31 div

30、ide 899 On a linux system or in cygwin,enter“factor 899”factor 899899:29 31factor 8999999999999999989999999999999999:7 7 13 6122449 2307692312304:222276912304038495:35731093769129485404038495:55897080807699294854040334945723:672472061178021762929485404033420344:22211093323422456427294854043485472:22

31、222315117311757440929485404203484:22310110322910314119348492404203484:2272314516292553111928439237492742742:21389104531282129938319284392329378472:22231321370533840299284392329378472323:3333071120085936708707Some“random”numbersfactored(using“factor”)Hmm、Apparentpatternofaseveralsmallprimefactorsendi

32、ngwithoneortwoverylargeprimes、Real?StillmanymysteriesinprimenumberpatternsOpenquestionsaboutexactdistributionofprimescloselyrelatedtothemainopenprobleminmath:theRiemannhypothesisconcerningdistr、ofzerosoftheRiemannzeta-function、49Theorem:Thereareinfinitelymanyprimes、Seeourearlierproofbycontradiction、

33、MersennenumbersMersennenumber:anynumberoftheform2n-1Mersenneprime:anyprimeoftheform2p-1,wherepisalsoaprimeExample:25-1=31isaMersenneprimeBut211-1=2047isnotaprime(23*89)IfMisaMersenneprime,thenM(M+1)/2isaperfectnumberA perfect number equals the sum of its divisorsExample:23-1=7 is a Mersenne prime,th

34、us 7*8/2=28 is a perfect number28=1+2+4+7+14Example:25-1=31 is a Merenne prime,thus 31*32/2=496 is a perfect number496=2*2*2*2*31 1+2+4+8+16+31+62+124+248=496ThelargestprimesfoundareMersenneprimes、Since,2p-1growsfast,andthereisaquiteefficienttestLucas-LehmertestfordeterminingifaMersenneprimeisprime、

35、5354So,theresstillsomeeasycashtobemade!559,808,358 digits thats close!5612Mdigitprimefound!PrizeawardedOct、14!57TIMEsBestInventionsof2008、58Also,whatspecialpatternsarethere(ifany)inthedigitsofprimenumbers?TheprimenumbertheoremTheratioofthenumberofprimesnotexceedingxandx/ln(x)approaches1asxgrowswitho

36、utboundRephrased:thenumberofprimenumberslessthanxisapproximatelyx/ln(x)(in1792byGaussat15、)Rephrased:thechanceofannumberxbeingaprimenumberis(roughly)1/ln(x)(density:therearennumbersuptonwithroughlyn/ln(n)beingprime、So,frequencyofprimesamongnnumbersisaround1/ln(n)、)So,lessfrequentforhigherxButstill,t

37、herearemanyprimes!(keyforcrypto!)Consider200digitprimenumbersln(10200)460Thechanceofa200digitnumberbeingprimeis1/460Ifweonlychooseoddnumbers,thechanceis2/460=1/230So,actually x/(ln x 1)is better estimate of number of primes、GreatestmondivisorThegreatestmondivisoroftwointegersaandb isthelargestintege

38、rdsuchthatd|aandd|bDenotedbygcd(a,b)Examplesgcd(24,36)=12gcd(17,22)=1gcd(100,17)=164RelativeprimesTwonumbersarerelatively primeiftheydonthaveanymonfactors(otherthan1)Rephrased:aandbarerelativelyprimeifgcd(a,b)=1gcd(25,16)=1,so25and16arerelativelyprime65PairwiserelativeprimeA set of integers a1,a2,an

39、 are pairwise relatively prime if,for all pairs of numbers,they are relatively primeFormally:The integers a1,a2,an are pairwise relatively prime if gcd(ai,aj)=1 whenever 1 i b)Sorta,bsothatab,andthen(givenb1)(amodb)=b?hmmEuclidsAlgorithmExamplegcd(372,164)=gcd(164,372mod164)、372mod164=372 164 372/16

40、4=372 1642=372 328=44、gcd(164,44)=gcd(44,164mod44)、164mod44=164 44 164/44=164 443=164 132=32、gcd(44,32)=gcd(32,44mod32)=gcd(32,12)=gcd(12,32mod12)=gcd(12,8)=gcd(8,12mod8)=gcd(8,4)=gcd(4,8mod4)=gcd(4,0)=4、So,werepeatedlyswapthenumbers、Largestfirst、“mod”reducesthemquickly!plexity?GuessO(log b)division

41、s、Linear in#digits of b!pare to direct search for divisor、(Lamesthm、Section4、3)2000+yralg、makesE-mercepossible!73IntegersandAlgorithms74Base-bnumbersystemsOrdinarily,we write base-10 representations of numbers,using digits 0-9、Of course,any base b1 will work、For any positive integers n,b,there is a

42、unique sequence ak ak-1 a1a0 of digits ai1:Tofindthevalueoftherightmost(lowest-order)digit,simplyputenmodb、Now,replacenwiththequotient n/b、Repeatabovetwostepstofindsubsequentdigits,untilnisgone(=0)、79ConstructingBasebExpansionsprocedure base b expansion(n:positive integer)q:=nk:=0while(q 0)beginak:=

43、q mod bq:=q/b k:=k+1end the base b expansion of n is(ak-1 ak-2、a1 a0)b N=25inbinary?So,wehave25inbinaryis11001、81N=23670inhexadecimal?23670mod16=6;6N=23670/16=1479mod16=776N=1479/16=92mod16=12C76N=92/16=5mod16=55C76AdditionofIntegersinBinaryNotationprocedure add(a,b:positive integers)c:=0for j:=0 to

44、 n-1begind:=(aj+bj+c)/2 sj:=aj+bj+c-2dc:=dend sj:=cthe binary expansion of the sum is(sn sn-1、s0)2 the binary expansions of a and b are:an-1,an-2,a1,a0 andbn-1,bn-2,b1,b0As you have known since grade 1 or before Correctness proof?plexity?(#additions)O(n),wherenisnumberofbits!(logofthesizeofthenumber

45、)83MultiplyingIntegersprocedure multiply(a,b:positive integers)c:=0for j:=0 to n-1beginif bj then cj:=a shifted j placeselse cj:=0end p:=0for j:=0 to n 1p:=p+cj p is the value of ab the binary expansions of a and b are:an-1,an-2,a1,a0 andbn-1,bn-2,b1,b0O(n2)Note:There are more efficient algorithms f

46、or multiplication!plexity?(additions and shifts)ModularExponentiation Problem:Givenlargeintegersb(base),n(exponent),andm(modulus),efficientlyputebnmodm、Notethatbnitselfmaycontainaverylargenumberofdigits、Yet,thisisatypeofcalculationthatismonlyrequiredinmoderncryptographicalgorithms!Hmm、ModularExponen

47、tiation:UsingBinaryExpansionofexponentn Note that:We can pute b to various powers of 2 by repeated squaring、Then multiply them into the partial product,or not,depending on whether the corresponding ai bit is 1、The binary expansion of nCrucially,wecandothemodmoperationsaswegoalong,becauseofthevarious

48、identitylawsofmodulararithmetic、All the numbers stay small、Problem solved?Note:11=(1011)2So,By successively squaring:Therefore:Thealgorithmsuccessivelyputes:Example:87ModularExponentiation procedure modular exponentiation(b:integer,ak1 ak2 a0:binary representation of n,m:positive integer)x:=1 power:

49、=b mod m for i:=0 to k1beginif ai=1 thenx:=(x、power)mod m power:=(power、power)mod m endreturn x Example:3644mod645Note:644=(1010000100)2Stepsperformedbythealgorithm:So,3644mod645=36、Keypoint:youputesuccessivepowersbutnumbersstaysmallbecauseofrepeatedModoperation!Aside:3644isHUGEbutfinalanswerbetween

50、0and644、TwoAdditionalApplications:1-Performingarithmeticwithlargenumbers2-PublicKeySystemrequiresomeadditionalresultsinNumberTheoryAdditionalNumberTheoryResultsTheorem:a,b integers,a,b 0:s,t:gcd(a,b)=sa+tbLemma1:a,b,c0:gcd(a,b)=1 and a|bc,then a|cLemma2:If p is prime and p|a1a2an(integers ai),then i