离散数学数论.ppt

《离散数学数论.ppt》由会员分享，可在线阅读，更多相关《离散数学数论.ppt（127页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、DiscreteMathCS2800Prof.BartSelmanModuleNumberTheoryRosen,Sections3-4to3-7.TheIntegersandDivisionOfcourse,youalreadyknowwhattheintegersare,andwhatdivisionisHowever:Therearesomespecificnotations,terminology,andtheoremsassociatedwiththeseconceptswhichyoumaynotknow.Theseformthebasicsofnumber theory.Vita

2、linmanyimportantalgorithmstoday(hashfunctions,cryptography,digitalsignatures;ingeneral,on-linesecurity).ThedividesoperatorNewnotation:3|12TospecifywhenanintegerevenlydividesanotherintegerReadas“3divides12”Thenot-dividesoperator:5|12TospecifywhenanintegerdoesnotevenlydivideanotherintegerReadas“5doesn

3、otdivide12”Divides,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?ResultsonthedividesoperatorIf a|b and a|c,the

4、n 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)DividesRelationTheorem:a,b,c Z:1.a|02.(a|b a|c)a|(b+c)3.a|ba|bc4.(

5、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.Proofof(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,nam

6、elyu=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+ncTheDivision“Algorithm”Theorem:Divisio

7、nAlgorithm-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 Whatarethequotientandr

8、emainderwhen101isdividedby11?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=101mod11adqrIf 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(pos

9、itive)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.Theorem:Division“Algor

10、ithm”-Letabeanintegeranddapositiveinteger.Thenthereareuniqueintegersqandr,with0rd,suchthata=dq+r.Proof:Wellusethewell-orderingpropertydirectlythatstatesthateverysetofnonnegativeintegershasaleastelement.a)ExistenceWewanttoshowtheexistenceofqandr,withthepropertythata=dq+r,0rd Note:thissetisnonemptysin

11、ceqcanbeanegativeintegerwithlargeabsolutevalue.Considerthesetofnon-negativenumbersoftheforma-dq,whereqisaninteger.Hmm.Canthissetbeempty?Bythewell-orderingproperty,Shasaleastelement,r=a-dq0.(Existence,cont.)risnon-negative;also,rd.otherwiseifrd,therewouldbeasmallernonnegativeelementinS,namelya-d(q0+1

12、)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)UniquenessSupposeWithoutlossofgenera

13、litywemayassumethatq 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 codo

14、main 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

15、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 t

16、hat 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 loc

17、ations)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

18、 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

19、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

20、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 docume

21、nt 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?

22、PseudorandomnumbersPseudorandomnumbersComputers 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

23、 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 WorldPrimesandGreatestCommonDivisorPrimenumbersApositiveintegerpisprimeiftheonlypositivefactorsofpare1andpIfthereareotherfactors,itiscompositeNote

24、that1isnotprime!ItsnotcompositeeitheritsinitsownclassAnintegerniscompositeifandonlyifthereexistsanintegerasuchthata|nand1anFundamentaltheoremofarithmeticFundamentalTheoremofArithmetic:Everypositiveintegergreaterthan1canbeuniquelywrittenasaprimeorastheproductoftwoormoreprimeswheretheprimefactorsarewr

25、itteninorderofnon-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 prim

26、es.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 a

27、s 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,thennhasaprimedivisorlessthanorequaltothesquarerootofnProofS

28、ince 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.,sho

29、w 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?ShowinganumberiscompositeShow that 899 is composite.SolutionDivide 899 by successively larger primes,starting with 2

30、We 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:222276935731093769129485404038495:55897080807699294854040334945723:672472061178021762929485404033420344:222110933234224564272948

31、54043485472:22222315117311757440929485404203484:22310110322910314119348492404203484:22723928439237492742742:21389104531282129938319284392329378472:22231321370533840299284392329378472323:333307Some“random”numbersfactored(using“factor”)Hmm.Apparentpatternofaseveralsmallprimefactorsendingwithoneortwove

32、rylargeprimes.Real?StillmanymysteriesinprimenumberpatternsOpenquestionsaboutexactdistributionofprimescloselyrelatedtothemainopenprobleminmath:theRiemannhypothesisconcerningdistr.ofzerosoftheRiemannzeta-function.Theorem:Thereareinfinitelymanyprimes.Seeourearlierproofbycontradiction.MersennenumbersMer

33、sennenumber: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 p

34、erfect 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.So,theresstillsome

35、easycashtobemade!9,808,358 digits thats close!12Mdigitprimefound!PrizeawardedOct.14!TIMEsBestInventionsof2008.Also,whatspecialpatternsarethere(ifany)inthedigitsofprimenumbers?TheprimenumbertheoremTheratioofthenumberofprimesnotexceedingxandx/ln(x)approaches1asxgrowswithoutboundRephrased:thenumberofpr

36、imenumberslessthanxisapproximatelyx/ln(x)(in1792byGaussat15.)Rephrased:thechanceofannumberxbeingaprimenumberis(roughly)1/ln(x)(density:therearennumbersuptonwithroughlyn/ln(n)beingprime.So,frequencyofprimesamongnnumbersisaround1/ln(n).)So,lessfrequentforhigherxButstill,therearemanyprimes!(keyforcrypt

37、o!)Consider200digitprimenumbersln(10200)460Thechanceofa200digitnumberbeingprimeis1/460Ifweonlychooseoddnumbers,thechanceis2/460=1/230So,actually x/(ln x 1)is better estimate of number of primes.GreatestcommondivisorThegreatestcommondivisoroftwointegersaandb isthelargestintegerdsuchthatd|aandd|bDenot

38、edbygcd(a,b)Examplesgcd(24,36)=12gcd(17,22)=1gcd(100,17)=1RelativeprimesTwonumbersarerelatively primeiftheydonthaveanycommonfactors(otherthan1)Rephrased:aandbarerelativelyprimeifgcd(a,b)=1gcd(25,16)=1,so25and16arerelativelyprimePairwiserelativeprimeA set of integers a1,a2,an are pairwise relatively

39、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

40、(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

41、b!Compare to direct search for divisor.(Lamesthm.Section4.3)2000+yralg.makesE-commercepossible!IntegersandAlgorithmsBase-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 a

42、k-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+

43、1end the base b expansion of n is(ak-1 ak-2.a1 a0)b N=25inbinary?So,wehave25inbinaryis11001.N=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)

44、/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)MultiplyingIntege

45、rsprocedure 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!Co

46、mplexity?(additions and shifts)ModularExponentiation Problem:Givenlargeintegersb(base),n(exponent),andm(modulus),efficientlycomputebnmodm.Notethatbnitselfmaycontainaverylargenumberofdigits.Yet,thisisatypeofcalculationthatiscommonlyrequiredinmoderncryptographicalgorithms!Hmm.ModularExponentiation:Usi

47、ngBinaryExpansionofexponentn 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,becauseofthevariousidentity

48、lawsofmodulararithmetic.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

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

50、4.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.