离散数学数论-PPT.pptx

离散数学数论2TheIntegersandDivisionOfcourse,youalreadyknowwhattheintegersare,andwhatdivisionisHowever:Therearesomespecificnotations,terminology,andtheoremsassociatedwiththeseconceptswhichyoumaynotknow、Theseformthebasicsofnumber theory、Vitalinmanyimportantalgorithmstoday(hashfunctions,cryptography,digitalsignatures;ingeneral,on-linesecurity)、3ThedividesoperatorNewnotation:3|12TospecifywhenanintegerevenlydividesanotherintegerReadas“3divides12”Thenot-dividesoperator:5|12TospecifywhenanintegerdoesnotevenlydivideanotherintegerReadas“5doesnotdivide12”4Divides,Factor,MultipleLet a,bZ with a0、Defn、:a|b“adividesb”:(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 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,then 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,careintegers,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、Thenthereareuniqueintegersqandr,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 called 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 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:Division“Algorithm”-Letabeanintegeranddapositiveinteger、Thenthereareuniqueintegersqandr,with0rd,suchthata=dq+r、Proof:Wellusethewell-orderingpropertydirectlythatstatesthateverysetofnonnegativeintegershasaleastelement、a)ExistenceWewanttoshowtheexistenceofqandr,withthepropertythata=dq+r,0rd Note:thissetisnonemptysinceqcanbeanegativeintegerwithlargeabsolutevalue、Considerthesetofnon-negativenumbersoftheforma-dq,whereqisaninteger、Hmm、Canthissetbeempty?Bythewell-orderingproperty,Shasaleastelement,r=a-dq0、(Existence,cont、)risnon-negative;also,rd、otherwiseifrd,therewouldbeasmallernonnegativeelementinS,namelya-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)UniquenessSupposeWithoutlossofgeneralitywemayassumethatq 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 domain 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)、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、How?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 than 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、There 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 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 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 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?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 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,itispositeNotethat1isnotprime!ItsnotpositeeitheritsinitsownclassAnintegernispositeifandonlyifthereexistsanintegerasuchthata|nand1anFundamentaltheoremofarithmeticFundamentalTheoremofArithmetic:Everypositiveintegergreaterthan1canbeuniquelywrittenasaprimeorastheproductoftwoormoreprimeswheretheprimefactorsarewritteninorderofnon-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-Hypothesis 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 product 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,it 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、SolutionThe 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 divide 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:22222315117311757440929485404203484:22310110322910314119348492404203484:2272314516292553111928439237492742742:21389104531282129938319284392329378472:22231321370533840299284392329378472323:3333071120085936708707Some“random”numbersfactored(using“factor”)Hmm、Apparentpatternofaseveralsmallprimefactorsendingwithoneortwoverylargeprimes、Real?StillmanymysteriesinprimenumberpatternsOpenquestionsaboutexactdistributionofprimescloselyrelatedtothemainopenprobleminmath:theRiemannhypothesisconcerningdistr、ofzerosoftheRiemannzeta-function、49Theorem:Thereareinfinitelymanyprimes、Seeourearlierproofbycontradiction、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,thus 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、5354So,theresstillsomeeasycashtobemade!559,808,358 digits thats close!5612Mdigitprimefound!PrizeawardedOct、14!57TIMEsBestInventionsof2008、58Also,whatspecialpatternsarethere(ifany)inthedigitsofprimenumbers?TheprimenumbertheoremTheratioofthenumberofprimesnotexceedingxandx/ln(x)approaches1asxgrowswithoutboundRephrased:thenumberofprimenumberslessthanxisapproximatelyx/ln(x)(in1792byGaussat15、)Rephrased:thechanceofannumberxbeingaprimenumberis(roughly)1/ln(x)(density:therearennumbersuptonwithroughlyn/ln(n)beingprime、So,frequencyofprimesamongnnumbersisaround1/ln(n)、)So,lessfrequentforhigherxButstill,therearemanyprimes!(keyforcrypto!)Consider200digitprimenumbersln(10200)460Thechanceofa200digitnumberbeingprimeis1/460Ifweonlychooseoddnumbers,thechanceis2/460=1/230So,actually x/(ln x 1)is better estimate of number of primes、GreatestmondivisorThegreatestmondivisoroftwointegersaandb isthelargestintegerdsuchthatd|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 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/164=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)divisions、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 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:=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 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)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 for multiplication!plexity?(additions and shifts)ModularExponentiation Problem:Givenlargeintegersb(base),n(exponent),andm(modulus),efficientlyputebnmodm、Notethatbnitselfmaycontainaverylargenumberofdigits、Yet,thisisatypeofcalculationthatismonlyrequiredinmoderncryptographicalgorithms!Hmm、ModularExponentiation: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,becauseofthevariousidentitylawsofmodulararithmetic、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: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:3644isHUGEbutfinalanswerbetween0and644、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