离散数学 数论

1,DiscreteMathCS2800,Prof.BartSModuleNumberTheoryRosen,Sections3-4to3-7.,2,TheIntegersandDivision,Ofcourse,youalreadyknowwhattheintegersare,andwhatdivisionisHowever:Therearesomespecificnotations,terminology,andtheoremsassociatedwiththeseconceptswhichyoumaynotknow.Theseformthebasicsofnumbertheory.Vitalinmanyimportantalgorithmstoday(hashfunctions,cryptography,digitalsignatures;ingeneral,on-linesecurity).,3,Thedividesoperator,Newnotation:3|12TospecifywhenanintegerevenlydividesanotherintegerReadas“3divides12”Thenot-dividesoperator:5|12TospecifywhenanintegerdoesnotevenlydivideanotherintegerReadas“5doesnotdivide12”,4,Divides,Factor,Multiple,Leta,bZwitha0.Defn.:a|b“adividesb”:(cZ:b=ac)“Thereisanintegercsuchthatctimesaequalsb.”Example:312True,but37False.Iffadividesb,thenwesayaisafactororadivisorofb,andbisamultipleofa.Ex.:“biseven”:2|b.Is0even?Is4?,5,Resultsonthedividesoperator,Ifa|banda|c,thena|(b+c)Example:if5|25and5|30,then5|(25+30)Ifa|b,thena|bcforallintegerscExample:if5|25,then5|25*cforallintscIfa|bandb|c,thena|cExample:if5|25and25|100,then5|100,(“commonfacts”butgoodtorepeatforbackground),6,DividesRelation,Theorem:a,b,cZ:1.a|02.(a|ba|c)a|(b+c)3.a|ba|bc4.(a|bb|c)a|c,Corollary:Ifa,b,careintegers,suchthata|banda|c,thena|mb+ncwhenevermandnareintegers.,7,Proofof(2),Showa,b,cZ:(a|ba|c)a|(b+c).Leta,b,cbeanyintegerssuchthata|banda|c,andshowthata|(b+c).Bydefn.of|,weknows:b=as,andt:c=at.Lets,t,besuchintegers.Thenb+c=as+at=a(s+t).So,u:b+c=au,namelyu=s+t.Thusa|(b+c).QED,DividesRelation,Corollary:Ifa,b,careintegers,suchthata|banda|c,thena|mb+ncwhenevermandnareintegers.Proof:Fromprevioustheorempart3(i.e.,a|ba|be)itfollowsthata|mbanda|nc;again,fromprevioustheorempart2(i.e.,(a|ba|c)a|(b+c)itfollowsthata|mb+nc,9,TheDivision“Algorithm”,Theorem:DivisionAlgorithm-Letabeanintegeranddapositiveinteger.Thenthereareuniqueintegersqandr,with0rd,suchthata=dq+r.,Itsreallyatheorem,notanalgorithmOnlycalledan“algorithm”forhistoricalreasons.,qiscalledthequotientriscalledtheremainderdiscalledthedivisoraiscalledthedividend,10,Whatarethequotientandremainderwhen101isdividedby11?,qiscalledthequotientriscalledtheremainderdiscalledthedivisoraiscalledthedividend,11,Ifa=7andd=3,thenq=2andr=1,since7=(2)(3)+1.Ifa=7andd=3,thenq=3andr=2,since7=(3)(3)+2.,So:givenpositiveaand(positive)d,inordertogetrwerepeatedlysubtractdfroma,asmanytimesasneededsothatwhatremains,r,islessthand.,Givennegativeaand(positive)d,inordertogetrwerepeatedlyadddtoa,asmanytimesasneededsothatwhatremains,r,ispositive(orzero)andlessthand.,Theorem:Division“Algorithm”-Letabeanintegeranddapositiveinteger.Thenthereareuniqueintegersqandr,with0rd,suchthata=dq+r.,Proof:Wellusethewell-orderingpropertydirectlythatstatesthateverysetofnonnegativeintegershasaleastelement.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.,qiscalledthequotientriscalledtheremainderdiscalledthedivisoraiscalledthedividend,b)UniquenessSuppose,WithoutlossofgeneralitywemayassumethatqQ.Subtractingbothequationswehave:d(q-Q)=(Rr)(*)So,ddivides(R-r);so,either|d|(Rr)|or(Rr)=0.SincedR-rd(because)i.e.,|R-r|0.ThisensuresthatitwouldtakeexponentialtimeinthelengthofanIDforanopponentto“fake”adifferentdocumenthavingthesameID.,ASimpleHashUsingmod,Letthedomainandcodomainbethesetsofallnaturalnumbersbelowcertainbounds:A=aN|aalim,B=bN|bblimThenanacceptable(althoughnotgreat!)hashfunctionfromAtoB(whenalimblim)ish(a)=amodblim.Ithasthefollowingdesirablehashfunctionproperties:ItcoversorisontoitscodomainB(itsrangeisB).Whenalimblim,theneachbBhasapreimageofaboutthesamesize,Specifically,|h1(b)|=alim/blimoralim/blim.,ASimpleHashUsingmod,However,ithasthefollowinglimitations:Itisnotveryrandom.Whynot?Itisdefinitelynotcryptographicallysecure.Givenab,itiseasytogenerateasthatmaptoit.How?,WeknowthatforanynN,h(b+nblim)=b.,Forexample,ifallasencounteredhappentohavethesameresiduemodblim,theywillallmaptothesameb!(seealso“spiralview”)Butok,ifinputdataisuniformlydistributed.,Collision,Becauseahashfunctionisnotone-to-one(therearemorepossiblekeysthanmemorylocations)morethanonerecordmaybeassignedtothesamelocationwecallthissituationacollision.Whattodowhenacollisionhappens?Onepossiblewayofsolvingacollisionistoassignthefirstfreelocationfollowingtheoccupiedmemorylocationassignedbythehashingfunction.Thereareotherwaysforexamplechaining(Ateachspotinthehashtable,keepalinkedlistofkeyssharingthishashvalue,anddoasequentialsearchtofindtheoneweneed.),DigitalSignatureApplication,Manydigitalsignaturesystemsuseacryptographicallysecure(butpublic)hashfunctionhwhichmapsarbitrarilylongdocumentsdowntofixed-length(e.g.,1,024-bit)“fingerprint”strings.Documentsigningprocedure:Signatureverificationprocedure:,Givenadocumentaandsignaturec,quicklyfindashashb=h(a).Computeb=f1(c).(Possibleiffsinversef1ismadepublic(butnotf).)Comparebtob;iftheyareequalthenthesignatureisvalid.,Notethatifhwerenotcryptographicallysecure,thenanopponentcouldeasilyforgeadifferentdocumentathathashestothesamevalueb,andtherebyattachsomeonesdigitalsignaturetoadifferentdocumentthantheyactuallysigned,andfooltheverifier!,Givenadocumentatosign,quicklycomputeitshashb=h(a).Computeacertainfunctionc=f(b)thatisknownonlytothesignerThisstepisgenerallyslow,sowedontwanttoapplyittothewholedocument.Delivertheoriginaldocumenttogetherwiththedigitalsignaturec.,Whatifhwasnotcryptographicallysecure?,30,Pseudorandomnumbers,31,Pseudorandomnumbers,Computerscannotgeneratetrulyrandomnumbersthatswhywecallthempseudo-randomnumbers!LinearCongruentialMethod:Algorithmforgeneratingpseudorandomnumbers.Choose4integersSeedx0:startingvalueModulusm:maximumpossiblevalueMultipliera:suchthat2aechoUryybJbeyq|rot13HelloWorld,PrimesandGreatestCommonDivisor,40,Primenumbers,Apositiveintegerpisprimeiftheonlypositivefactorsofpare1andpIfthereareotherfactors,itiscompositeNotethat1isnotprime!ItsnotcompositeeitheritsinitsownclassAnintegerniscompositeifandonlyifthereexistsanintegerasuchthata|nand1n*nn.Contradiction.)Thus,nhasadivisornotexceedingnThisdivisoriseitherprimeoracompositeIfthelatter,thenithasaprimefactor(bytheFTA)Ineithercase,nhasaprimefactorlessthann,QED,44,Showinganumberisprime,E.g.,showthat113isprime.SolutionTheonlyprimefactorslessthan113=10.63are2,3,5,and7Noneofthesedivide113evenlyThus,bythefundamentaltheoremofarithmetic,113mustbeprime,How?,45,Showinganumberiscomposite,Showthat899iscomposite.SolutionDivide899bysuccessivelylargerprimes,startingwith2Wefindthat29and31divide899,Onalinuxsystemorincygwin,enter“factor899”factor899899:2931factor8999999999999999989999999999999999:7713612244923076923,12304:222276912304038495:35731093769129485404038495:55897080807699294854040334945723:672472061178021762929485404033420344:22211093323422456427294854043485472:22222315117311757440929485404203484:22310110322910314119348492404203484:2272314516292553111928439237492742742:21389104531282129938319284392329378472:22231321370533840299284392329378472323:3333071120085936708707,Some“random”numbersfactored(using“factor”),Hmm.Apparentpatternofaseveralsmallprimefactorsendingwithoneortwoverylargeprimes.Real?Stillmanymysteriesinprimenumberpatterns,Openquestionsaboutexactdistributionofprimescloselyrelatedtothemainopenprobleminmath:theRiemannhypothesisconcerningdistr.ofzerosoftheRiemannzeta-function.,48,Theorem:Thereareinfinitelymanyprimes.Seeourearlierproofbycontradiction.,Mersennenumbers,Mersennenumber:anynumberoftheform2n-1Mersenneprime:anyprimeoftheform2p-1,wherepisalsoaprimeExample:25-1=31isaMersenneprimeBut211-1=2047isnotaprime(23*89)IfMisaMersenneprime,thenM(M+1)/2isaperfectnumberAperfectnumberequalsthesumofitsdivisorsExample:23-1=7isaMersenneprime,thus7*8/2=28isaperfectnumber28=1+2+4+7+14Example:25-1=31isaMerenneprime,thus31*32/2=496isaperfectnumber,496=2*2*2*2*311+2+4+8+16+31+62+124+248=496,ThelargestprimesfoundareMersenneprimes.Since,2p-1growsfast,andthereisaquiteefficienttestLucas-LehmertestfordeterminingifaMersenneprimeisprime.,51,Lucas-Lehmertest,52,53,So,theresstillsomeeasycashtobemade!,54,9,808,358digitsthatsclose!,55,12Mdigitprimefound!PrizeawardedOct.14!,56,TIMEsBestInventionsof2008.,57,Also,whatspecialpatternsarethere(ifany)inthedigitsofprimenumbers?,Theprimenumbertheorem,Theratioofthenumberofprimesnotexceedingxandx/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/230,So,actuallyx/(lnx1)isbetterestimateofnumberofprimes.,Greatestcommondivisor,Thegreatestcommondivisoroftwointegersaandbisthelargestintegerdsuchthatd|aandd|bDenotedbygcd(a,b)Examplesgcd(24,36)=12gcd(17,22)=1gcd(100,17)=1,63,Relativeprimes,Twonumbersarerelativelyprimeiftheydonthaveanycommonfactors(otherthan1)Rephrased:aandbarerelativelyprimeifgcd(a,b)=1gcd(25,16)=1,so25and16arerelativelyprime,64,Pairwiserelativeprime,Asetofintegersa1,a2,anarepairwiserelativelyprimeif,forallpairsofnumbers,theyarerelativelyprimeFormally:Theintegersa1,a2,anarepairwiserelativelyprimeifgcd(ai,aj)=1whenever1ib)Sorta,bsothatab,andthen(givenb1)(amodb)=b?hmm,EuclidsAlgorithmExample,gcd(372,164)=gcd(164,372mod164).372mod164=372164372/164=3721642=372328=44.gcd(164,44)=gcd(44,164mod44).164mod44=16444164/44=164443=164132=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?Guess,O(logb)divisions.Linearin#digitsofb!Comparetodirectsearchfordivisor.,(Lamesthm.Section4.3),2000+yralg.makesE-commercepossible!,72,IntegersandAlgorithms,73,Base-bnumbersystems,Ordinarily,wewritebase-10representationsofnumbers,usingdigits0-9.Ofcourse,anybaseb1willwork.Foranypositiveintegersn,b,thereisauniquesequenceakak-1a1a0ofdigitsai1:Tofindthevalueoftherightmost(lowest-order)digit,simplycomputenmodb.Now,replacenwiththequotientn/b.Repeatabovetwostepstofindsubsequentdigits,untilnisgone(=0).,78,ConstructingBasebExpansions,procedurebasebexpansion(n:positiveinteger)q:=nk:=0while(q0)beginak:=qmodbq:=q/bk:=k+1endthebasebexpansionofnis(ak-1ak-2.a1a0)b,N=25inbinary?,So,wehave25inbinaryis11001.,80,N=23670inhexadecimal?23670mod16=6;6N=23670/16=1479mod16=776N=1479/16=92mod16=12C76N=92/16=5mod16=55C76,AdditionofIntegersinBinaryNotation,procedureadd(a,b:positiveintegers)c:=0forj:=0ton-1begind:=(aj+bj+c)/2sj:=aj+bj+c-2dc:=dendsj:=cthebinaryexpansionofthesumis(snsn-1.s0)2,thebinaryexpansionsofaandbare:an-1,an-2,a1,a0andbn-1,bn-2,b1,b0,Asyouhaveknownsincegrade1orbefore,Correctnessproof?,Complexity?(#additions),O(n),wherenisnumberofbits!(logofthesizeofthenumber),82,MultiplyingIntegers,proceduremultiply(a,b:positiveintegers)c:=0forj:=0ton-1beginifbjthencj:=ashiftedjplaceselsecj:=0endp:=0forj:=0ton1p:=p+cjpisthevalueofab,thebinaryexpansionsofaandbare:an-1,an-2,a1,a0andbn-1,bn-2,b1,b0,O(n2),Note:Therearemoreefficientalgorithmsformultiplication!,Complexity?(additionsandshifts),ModularExponentiation,Problem:Givenlargeintegersb(base),n(exponent),andm(modulus),efficientlycomputebnmodm.Notethatbnitselfmaycontainaverylargenumberofdigits.Yet,thisisatypeofcalculationthatiscommonlyrequiredinmoderncryptographicalgorithms!Hmm.,ModularExponentiation:UsingBinaryExpansionofexponentn,Notethat:Wecancomputebtovariouspowersof2byrepeatedsquaring.Thenmultiplythemintothepartialproduct,ornot,dependingonwhetherthecorrespondingaibitis1.,Thebinaryexpansionofn,Crucially,wecandothemodmoperationsaswegoalong,becauseofthevariousidentitylawsofmodulararithmetic.Allthenumbersstaysmall.,Problemsolved?,Note:11=(1011)2,So,Bysuccessivelysquaring:,Therefore:,Thealgorithmsuccessivelycomputes:,Example:,86,ModularExponentiation,proceduremodularexponentiation(b:integer,ak1ak2a0:binaryrepresentationofn,m:positiveinteger)x:=1power:=bmodmfori:=0tok1beginifai=1thenx:=(xpower)modmpower:=(powerpower)modmendreturnx,Example:3644mod645Note:644=(1010000100)2Stepsperformedbythealgorithm:,So,3644mod645=36.Keypoint:youcomputesuccessivepowersbutnumbersstaysmallbecauseofrepeatedModoperation!,Aside:3644isHUGEbutfinalanswerbetween0and644.,TwoAdditionalApplications:1-Performingarithmeticwithlargenumbers2-PublicKeySystemrequiresomeadditionalresultsinNumberTheory,AdditionalNumberTheoryResults,Theorem:a,bintegers,a,b0:s,t:gcd(a,b)=sa+tbLemma1:a,b,c0:gcd(a,b)=1anda|bc,thena|cLemma2:Ifpisprimeandp|a1a2an(integersai),theni:p|ai.Theorem2:Ifacbc(modm)andgcd(c,m)=1,thenab(modm).,ProofofTheorem1,Theorem1:ab0st:gcd(a,b)=sa+tbProof:Byinductionoverthevalueofthelargerargumenta.Note:FromEuclidtheorem(“reducingthesizeofa”),weknowthatgcd(a,b)=gcd(b,c)withc=amodb,inwhichcasea=kb+cforsomeintegerk,soc=akb.Withbaandc0berelativeprime.Thenthesystemofequationsxai(modmi)(fori=1ton)hasauniquesolutionmodulom=m1mn.Proof:LetMi=m/mi.Thusgcd(mi,Mi)=1.Sobythm3,yisuchthatyiMi1(modmi).Nowletx=iaiyiMi.Sincemi|Mkforki,wehaveMk0(modmi).So,xmodmi=lalylMlmodmi=aiyiMimodmi=aimodmi.Thus,xai(modmi).Holdsforeachi.Thus,thecongruenceshold.(Uniquenessleftasexercise.),QED,Whatsxsuchthat:x2(mod3)x3(mod5)x2(mod7)?,m=357=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,x2235+3121+2115=23323(mod105)Soanswer:x23(mod105),UsingtheChineseRemaindertheorem:,Weresolvingequationsinmodulararithmetic!,x=iaiyiMi,m=m1mn.,Mi=m/mi,yiMi1(modmi).,(So,a1=2,etc.andm1=3etc.),ComputerArithmeticwithLargeInts,ByChineseRemainderTheorem,anintegerawhere0am=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,weareusingtwosmallnumberstorepresentabiggerone(uptothesize