离散数学-数论1课件

DiscreteMathCS2800Prof.BartSelmanselmancs.cornell.eduModuleNumberTheoryRosen,Sections3-4to3-7.1TheIntegersandDivisionOfcourse,youalreadyknowwhattheintegersare,andwhatdivisionisHowever:Therearesomespecificnotations,terminology,andtheoremsassociatedwiththeseconceptswhichyoumaynotknow.Theseformthebasicsofnumber theory.Vitalinmanyimportantalgorithmstoday(hashfunctions,cryptography,digitalsignatures;ingeneral,on-linesecurity).2ThedividesoperatorNewnotation:3|12TospecifywhenanintegerevenlydividesanotherintegerReadas“3divides12”Thenot-dividesoperator:5|12TospecifywhenanintegerdoesnotevenlydivideanotherintegerReadas“5doesnotdivide12”3Divides,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?4ResultsonthedividesoperatorIf 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(“common facts”but good to repeat for background)5DividesRelationTheorem: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.6Proofof(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).QED7DividesRelationCorollary: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+ncTheDivision“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 9Whatarethequotientandremainderwhen101isdividedby11?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=101mod11adqr10If 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.11Theorem: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.25ASimpleHashUsingmodLet 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).Compute b=f 1(c).(Possible if fs inverse f 1 is made public(but not f).)Compare 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 compute its hash b=h(a).Compute 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?Pseudorandomnumbers30PseudorandomnumbersComputers 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 World38PrimesandGreatestCommonDivisorPrimenumbersApositiveintegerpisprimeiftheonlypositivefactorsofpare1andpIfthereareotherfactors,itiscompositeNotethat1isnotprime!ItsnotcompositeeitheritsinitsownclassAnintegerniscompositeifandonlyifthereexistsanintegerasuchthata|nand1an40FundamentaltheoremofarithmeticFundamentalTheoremofArithmetic: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 composite 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,soonCompositefactorsTheorem:Ifn isacompositeinteger,thennhasaprimedivisorlessthanorequaltothesquarerootofnProofSince n is composite,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 compositeIf the latter,then it has a prime factor(by the FTA)In either case,n has a prime factor less than nQEDShowinganumberisprimeE.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?44ShowinganumberiscompositeShow that 899 is composite.SolutionDivide 899 by successively larger primes,starting with 2We find that 29 and 31 divide 899 45 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.Theorem:Thereareinfinitelymanyprimes.Seeourearlierproofbycontradiction.48MersennenumbersMersennenumber: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.52So,theresstillsomeeasycashtobemade!539,808,358 digits thats close!5412Mdigitprimefound!PrizeawardedOct.14!55TIMEsBestInventionsof2008.56Also,whatspecialpatternsarethere(ifany)inthedigitsofprimenumbers?57TheprimenumbertheoremTheratioofthenumberofprimesnotexceedingxandx/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.GreatestcommondivisorThegreatestcommondivisoroftwointegersaandb isthelargestintegerdsuchthatd|aandd|bDenotedbygcd(a,b)Examplesgcd(24,36)=12gcd(17,22)=1gcd(100,17)=1RelativeprimesTwonumbersarerelatively primeiftheydonthaveanycommonfactors(otherthan1)Rephrased:aandbarerelativelyprimeifgcd(a,b)=1gcd(25,16)=1,so25and16arerelativelyprime63PairwiserelativeprimeA 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?hmm70EuclidsAlgorithmExamplegcd(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!Complexity?GuessO(log b)divisions.Linear in#digits of b!Compare to direct search for divisor.(Lamesthm.Section4.3)2000+yralg.makesE-commercepossible!IntegersandAlgorithms72Base-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,simplycomputenmodb.Now,replacenwiththequotient n/b.Repeatabovetwostepstofindsubsequentdigits,untilnisgone(=0).ConstructingBasebExpansionsprocedure 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 78N=25inbinary?So,wehave25inbinaryis11001.N=23670inhexadecimal?23670mod16=6;6N=23670/16=1479mod16=776N=1479/16=92mod16=12C76N=92/16=5mod16=55C7680AdditionofIntegersinBinaryNotationprocedure 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?Complexity?(#additions)O(n),wherenisnumberofbits!(logofthesizeofthenumber)MultiplyingIntegersprocedure 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!Complexity?(additions and shifts)82ModularExponentiation Problem:Givenlargeintegersb(base),n(exponent),andm(modulus),efficientlycomputebnmodm.Notethatbnitselfmaycontainaverylargenumberofdigits.Yet,thisisatypeofcalculationthatiscommonlyrequiredinmoderncryptographicalgorithms!Hmm.ModularExponentiation:UsingBinaryExpansionofexponentn Note that:We can compute 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:Thealgorithmsuccessivelycomputes:Example:ModularExponentiation 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:=(xpower)mod m power:=(powerpower)mod m endreturn x 86Example:3644mod645Note:644=(1010000100)2Stepsperformedbythealgorithm:So,3644mod645=36.Keypoint:youcomputesuccessivepowersbutnumbersstaysmallbecauseofrepeatedModoperation!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:p|ai.Theorem2:If ac bc(mod m)and gcd(c,m)=1,then a b(mod m).ProofofTheorem1Theorem1:ab0 st:gcd(a,b)=sa+tbProof:By induction over the value of the larger argument a.Note:FromEuclidtheorem(“reducingthesizeofa”),weknowthatgcd(a,b)=gcd(b,c)withc=amodb,inwhichcasea=kb+cforsomeintegerk,soc=akb.Withb aandc b(seebasecasebelowforboundarycases),bytheinductivehypothesis(stronginduction),wecanassumethat uv:gcd(b,c)=ub+vc.Substitutingforc,thisisub+v(akb),whichwecanregrouptogetva+(uvk)b.So,nowlets=v,andlett=uvk,andweredonewithinductionstep.QEDThebasecaseissolvedbyconsidering:s=1,t=0,whichworksforgcd(a,0),orifa=boriginally(alsohandlesgcd(0,0).Basecase?Example:gcd(252,198)=18.Letsexpress18asalinearcombinationof252and198.UsingthedivisionsperformedbytheEuclidAlgorithm:252=1 198+54(from252mod198=54)198=3 54+36(from198mod54=36)54=1 36+18etc.36=2 18So,18=54-1 36(from3rdequation)36=1983 54(from2thequation)Therefore18=54-1(1983 54)=4 541 198But54=252-1 198;sosubstitutingthisexpressionfor54:18=4(252-1 198)-1 198=4 2525 198So,gcd(252,198)=18=4x2525x198.I.e.,thegcdisalinearcombinationoftheoriginalnumbers.Intriguingpropertyofthegcd!Oneofthemulipliershastobenegative.gcd(252,198)=gcd(198,54)=gcd(54,36)=gcd(36,18)=gcd(18,0)=18E.g.gcd(17,5)=1 (i.e.one argument is prime,or relative primes)1=-7 x 17+24 x 5 =8 x 17 27 x 50,17,34,51,68,85,102,119,136 92ProofofLemma1Lemma1:gcd(a,b)=1anda|bc,thena|c.Proof:Applyingtheorem1,s,t:sa+tb=1.Multiplyingthroughbyc,wehavethatsac+tbc=c.Sincea|bc isgiven,weknowthata|tbc,andobviouslya|sac.Thus,itfollowsthata|(sac+tbc).So,wehavethata|c.Alt.proof:Considertheprimefactorizationofa,b,andc.Aside:But,why dont we want to use this property for now?ProofofLemma2Lemma2:Ifprimep|a1anthen i:p|ai.Proof:If n=1,this is immediate since p|a1 then p|a1.Suppose the lemma is true for all n1,thenahasaunique(modulo m)inversea.Proof:Bytheorem1,st:sa+tm=1,sosa+tm1(modm).Sincetm 0(modm),sa 1(modm).Thussisaninverseofa(modm).Theorem2guaranteesthatifra sa 1(modm)andgcd(a,m)=1,thenr s(mod m).Thusthisinverseisuniquemodm.(Allinversesofaareinthesamecongruenceclassass.)Linearcongruencesarethebasisfordoingarithmeticwithverylargeintegers.QEDExample:Findaninverseof4modulo9Sincegcd(4,9)=1,weknowthatthereisaninverseof4,modulo9.UsingtheEuclideanalgorithmtofindthegreatestcommondivisor:9=2 4+1So,-2 4+1 9=1Takemod9bothsides.:-2x41(mod9).Itfollowsthat-2isaninverseof4module9.Wehave:-2x4=-8.And-8mod9=1.Also,soiseveryintegercongruentto-2modulo9,e.g.,-2,7,-11,16,etc.Whatarethesolutionsofthelinearcongruence4x5(mod9)?Sinceweknowthat-2isaninversefor4mod9,wecanmultiplybothsidesofthelinearcongruence:-2 4x-2 5(mod9)Since-81(mod9)and-108(mod9),itfollowsthatx-108(mod9).(Wecancheckthatindeed,4x4 85(mod9).)So,solutionstothecongruenceareintegersxsuchthatx8(mod)9,namely,8,17,26,and-1,-10,etc.AncientChinesePuzzle:Therearecertainthingswhosenumberisunknown.Whendividedby3,theremainderis2;whendividedby5,theremainderis3;andwhendividedby7,theremainderis2.Whatisthenumberofthings?Whatsxsuchthat:xmod3=2xmod5=3xmod7=2Or,equivalently,x2(mod3)x3(mod5)x2(mod7)Statedformally:I.e.,wehavetosolveasetoflinearcongruences.Noteyouneedthedifferent“modulos”tohaveitmakesense.Argh!Guess?x23(mod105)buthow?ChineseRemainderTheoremTheorem:(Chineseremaindertheorem.)Letm1,mn0berelativeprime.Thenthesystemofequationsxai(modmi)(fori=1ton)hasauniquesolutionmodulom=m1mn.Proof:LetMi=m/mi.Thusgcd(mi,Mi)=1.Sobythm3,yi suchthatyi Mi 1(modmi).Nowlet x=iai yi Mi.Sincemi|Mk fork i,we have Mk 0(modmi).So,xmodmi =lal yl Ml modmi =ai yi Mi modmi =aimodmi.Thus,x ai(modmi).Holdsforeachi.Thus,thecongruenceshold.(Uniquenessleftasexercise.)QED102Whats x such that:x 2(mod 3)x 3(mod 5)x 2(mod 7)?m=3 5 7=105M1=m/3=105/3=352isaninverseofM1=35(mod3)(since35x21(mod3)M2=m/5=105/5=211isaninverseofM2=21(mod5)(since21x11(mod5)M3=m/7=151isaninverseofM3=15(mod7)(since15x11(mod7)So,x2 2 35+3 1 21+2 1 15=23323(mod105)Soanswer:x23(mod105)UsingtheChineseRemaindertheorem:Weresolvingequationsinmodulararithmetic!x=iai yi Mim=m1mn.Mi=m/miyi Mi 1(modmi).(So,a1=2,etc.andm1=3etc.)ComputerArithmeticwithLargeIntsByChineseRemainderTheorem,anintegerawhere0a m=mi,gcd(mi,mji)=1,canberepresentedbyasresiduesmodmiasann-tuple:(amodm1,amodm2,amodmn)Implicitly,representstheequationsxai(modmi),withai=amodmi.BytheCRT,thereisauniquesolution(modm)totheseequations.Considerxamodm,withm=mi.Substitutionshowsthatthisxsolvestheequations.Example:Howtorepresentuniquelynon-integerintegerslessthan12bypairs,wherethefirstcomponentistheremainderoftheintegerupondivisionby3andthesecondcomponentistheremainderoftheintegerupondivisionby4?(note:3and4arerelativeprime.)Werepresentxbythetuple(xmod3,xmod4).Findingtheremainderofeachintegerdivideby3and4,weobtain:0=(0,0);1=(1,1);2=(2,2);3=(0,3);4=(1,0);5=(2,1);6=(0,2);7=(1,3);8=(2,0);9=(0,1);10=(1,2);11=(2,3)E.g.5=(5mod3),(5mod4)Notewehavetheright“numberofpairs”,i.e.,12.Oneforeachnumberupto4x3-1.Also,weareusingtwosmallnum