《《离散数学数论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《离散数学数论》PPT课件.ppt（127页珍藏版）》请在三一办公上搜索。
1、1,Discrete MathCS 2800,Prof.Bart SelmanModule Number TheoryRosen,Sections 3-4 to 3-7.,2,The Integers and Division,Of course,you already know what the integers are,and what division isHowever:There are some specific notations,terminology,and theorems associated with these concepts which you may not k
2、now.These form the basics of number theory.Vital in many important algorithms today(hash functions,cryptography,digital signatures;in general,on-line security).,3,The divides operator,New notation:3|12To specify when an integer evenly divides another integerRead as“3 divides 12”The not-divides opera
3、tor:5|12To specify when an integer does not evenly divide another integerRead as“5 does not divide 12”,4,Divides,Factor,Multiple,Let a,bZ with a0.Defn.:a|b“a divides b”:(cZ:b=ac)“There is an integer c such that c times a equals b.”Example:312 True,but 37 False.Iff a divides b,then we say a is a fact
4、or or a divisor of b,and b is a multiple of a.Ex.:“b is even”:2|b.Is 0 even?Is 4?,5,Results on the divides operator,If 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 an
5、d 25|100,then 5|100,(“common facts”but good to repeat for background),6,Divides Relation,Theorem:a,b,c Z:1.a|02.(a|b a|c)a|(b+c)3.a|b a|bc4.(a|b b|c)a|c,Corollary:If a,b,c are integers,such that a|b and a|c,then a|mb+nc whenever m and n are integers.,7,Proof of(2),Show a,b,c Z:(a|b a|c)a|(b+c).Let a
6、,b,c be any integers such that a|b and a|c,and show that a|(b+c).By defn.of|,we know s:b=as,and t:c=at.Let s,t,be such integers.Then b+c=as+at=a(s+t).So,u:b+c=au,namely u=s+t.Thus a|(b+c).QED,Divides Relation,Corollary:If a,b,c are integers,such that a|b and a|c,then a|mb+nc whenever m and n are int
7、egers.Proof:From previous theorem part 3(i.e.,a|b a|be)it follows that a|mb and a|nc;again,from previous theorem part 2(i.e.,(a|b a|c)a|(b+c)it follows that a|mb+nc,9,The Division“Algorithm”,Theorem:Division Algorithm-Let a be an integer and d a positive integer.Then there are unique integers q and
8、r,with 0 r d,such that a=dq+r.,Its really a theorem,not an algorithm Only called an“algorithm”for historical reasons.,q is called the quotient r is called the remainder d is called the divisor a is called the dividend,10,What are the quotient and remainder when 101 is divided by 11?,q is called the
9、quotient r is called the remainder d is called the divisor a is called the dividend,11,If 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 th
10、at 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“Algorithm”-Let a be an integer and d a positive integer.Then there are unique integers q a
11、nd r,with 0 rd,such that a=dq+r.,Proof:Well use the well-ordering property directly that states that every set of nonnegative integers has a least element.Existence We want to show the existence of q and r,with the property that a=dq+r,0 r d,Note:this set is non empty since q can be a negative integ
12、er with large absolute value.,Consider the set of non-negative numbers of the form a-dq,where q is an integer.Hmm.Can this set be empty?,By the well-ordering property,S has a least element,r=a-d q0.,(Existence,cont.)r is non-negative;also,r d.otherwise if r d,there would be a smaller nonnegative ele
13、ment in S,namely a-d(q0+1)0.But then a-d(q0+1),which is smaller than a-dq0,is an element of S,contradicting that a-dq0 was the smallest element of S.So,it cannot be the case that r d,proving the existence of 0 r d and q.,q is called the quotient r is called the remainder d is called the divisor a is
14、 called the dividend,b)UniquenessSuppose,Without loss of generality we may assume that q Q.Subtracting both equations we have:d(q-Q)=(R r)(*)So,d divides(R-r);so,either|d|(R r)|or(R r)=0.Since d R-r d(because)i.e.,|R-r|d,we must have R r=0.So,R=r.,Substituting into the original two equations,we have
15、 dq=d Q(note d0)and thus q=Q,proving uniqueness.(or directly from(*),QED,Modular arithmetic,If a and b are integers and m is a positive integer,then“a is congruent to b modulo m”if m divides a-bNotation:a b(mod m)Rephrased:m|a-bRephrased:a mod m=b mod mIf they are not congruent:a b(mod m)Example:Is
16、17 congruent to 5 modulo 6?Rephrased:17 5(mod 6)As 6 divides 17-5,they are congruentExample:Is 24 congruent to 14 modulo 6?Rephrased:24 14(mod 6)As 6 does not divide 24-14=10,they are not congruent,Note:this is a different use of“”than the meaning“is defined as”used before.,Note“=“sign.,16,Time-keep
17、ing on a clock gives an example of modular arithmetic.(mod 12 in the US;or mod 24,using the 24hr clock.Naturally imposed by the periodicity of earths rotation.),Spiral Visualization of mod,3(mod 5),2(mod 5),1(mod 5),0(mod 5),4(mod 5),0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,Example
18、 shown:modulo-5arithmetic,So,e.g.,19 is congruent to 9 modulo 5.,The spiral/circular view is usefulto keep in mind when doingmodular arithmetic!,Congruence classesmodulo 5.,Collapses infiniteset of numbers into5 classes.,Where is-1?,Where is-7?,More on congruences,Theorem:Let a and b be integers,and
19、 let m be a positive integer.Then a b(mod m)if and only if a mod m=b mod m,Theorem:Let m be a positive integer.The integers a and b are congruent modulo m if and only if there is an integer k such that a=b+kmExample:17 and 5 are congruent modulo 6,so17=5+2*6 5=17-2*6,19,Even even more on congruence,
20、Theorem:Let m be a positive integer.If a b(mod m)and c d(mod m),then a+c(b+d)(mod m)and ac bd(mod m)ExampleWe know that 7 2(mod 5)and 11 1(mod 5)Thus,7+11(2+1)(mod 5),or 18 3(mod 5)Thus,7*11 2*1(mod 5),or 77 2(mod 5),20,Applications of Congruences,21,Hashing Functions,Also known as:hash functions,ha
21、sh codes,or just hashes.Two major uses:Indexing hash tablesData structures which support O(1)-time access.Creating short unique IDs for long documents.Used in digital signatures the short ID can be signed,rather than the long document.,22,Hash Functions,Example:Consider a a record that is identified
22、 by the SSN(9 digits)of the customer or customer name itself(mapped into binary number).How can we assign a memory location to a record so that later on its easy to locate and retrieve such a record?Solution to this problem a good hashing function.Records are identified using a key(k),which uniquely
23、 identifies each record.If you compute the hash of the same data at different times,you should get the same answer if not then the data has been modified.,23,Hash Function Requirements,A hash function h:AB is a map from a set A to a smaller set B(i.e.,|A|B|).An effective hash function should have th
24、e following properties:It should cover(be onto)its codomain B.It should be efficient to calculate.The cardinality of each pre-image of an element of B should be about the same.b1,b2B:|h1(b1)|h1(b2)|That is,elements of B should be generated with roughly uniform probability.Ideally,the map should appe
25、ar random,so that clearly“similar”elements of A are not likely to map to the same(or similar)elements of B.,24,Why are these important?,To make computations fast and efficient.So that any message can be hashed.To prevent a message being replaced with another with the same hash value.To prevent the s
26、ender claiming to have sent x2 when in fact the message was x1.,25,Hash Function Requirements,Furthermore,for a cryptographically secure hash function:Given an element bB,the problem of finding an aA such that h(a)=b should have average-case time complexity of(|B|c)for some c0.This ensures that it w
27、ould take exponential time in the length of an ID for an opponent to“fake”a different document having the same ID.,A Simple Hash Using mod,Let 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 f
28、rom 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.,A Simple Hash Using mod,However,it ha
29、s 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 s
30、ame b!(see also“spiral view”)But ok,if input data is uniformly distributed.,Collision,Because 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
31、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
32、 search to find the one we need.),Digital Signature Application,Many 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 pr
33、ocedure:,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 differe
34、nt 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
35、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?,30,Pseudorandom numbers,31,Pseudorandom numbers,Computers cannot generate truly random numbers thats why we call them p
36、seudo-random numbers!Linear Congruential Method: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 m,apply the for
37、mula:xn+1=(axn+c)mod m,32,Pseudorandom numbers,Formula:xn+1=(axn+c)mod mLet x0=3,m=9,a=7,and c=4x1=7x0+4=7*3+4=25 mod 9=7x2=7x1+4=7*7+4=53 mod 9=8x3=7x2+4=7*8+4=60 mod 9=6x4=7x3+4=7*6+4=46 mod 9=1x5=7x4+4=7*1+4=11 mod 9=2x6=7x5+4=7*2+4=18 mod 9=0 x7=7x6+4=7*0+4=4 mod 9=4x8=7x7+4=7*4+4=32 mod 9=5,Qui
38、te random!,33,Pseudorandom numbers,Formula:xn+1=(axn+c)mod mLet x0=3,m=9,a=7,and c=4This sequence generates:3,7,8,6,1,2,0,4,5,3,7,8,6,1,2,0,4,5,3Note that it repeats!But it selects all the possible numbers before doing soThe common algorithms today use m=232-1You have to choose 4 billion numbers bef
39、ore it repeatsMultiplier 75=16,807 and increment c=0(pure multiplicative generator),34,3 million random bits per dollarQuite a bargain,35,Cryptology(secret messages),36,The Caesar cipher,Julius Caesar used the following procedure to encrypt messagesA function f to encrypt a letter is defined as:f(p)
40、=(p+3)mod 26Where p is a letter(0 is A,1 is B,25 is Z,etc.)Decryption:f-1(p)=(p-3)mod 26This is called a substitution cipherYou are substituting one letter with another,37,The Caesar cipher,Encrypt“go cavaliers”Translate to numbers:g=6,o=14,etc.Full sequence:6,14,2,0,21,0,11,8,4,17,18Apply the ciphe
41、r to each number:f(6)=9,f(14)=17,etc.Full sequence:9,17,5,3,24,3,14,11,7,20,21Convert the numbers back to letters 9=j,17=r,etc.Full sequence:jr wfdydolhuvDecrypt“jr wfdydolhuv”Translate to numbers:j=9,r=17,etc.Full sequence:9,17,5,3,24,3,14,11,7,20,21Apply the cipher to each number:f-1(9)=6,f-1(17)=
42、14,etc.Full sequence:6,14,2,0,21,0,11,8,4,17,18Convert the numbers back to letters 6=g,14=0,etc.Full sequence:“go cavaliers”,38,Rot13 encoding,A Caesar cipher,but translates letters by 13 instead of 3Then,apply the same function to decrypt it,as 13+13=26Rot13 stands for“rotate by 13”Example:echo Hel
43、lo World|rot13Uryyb Jbeyq echo Uryyb Jbeyq|rot13Hello World,Primes and Greatest Common Divisor,40,Prime numbers,A positive integer p is prime if the only positive factors of p are 1 and pIf there are other factors,it is compositeNote that 1 is not prime!Its not composite either its in its own classA
44、n integer n is composite if and only if there exists an integer a such that a|n and 1 a n,Fundamental theorem of arithmetic,Fundamental Theorem of Arithmetic:Every positive integer greater than 1 can be uniquely written as a prime or as the product of two or more primes where the prime factors are w
45、ritten inorder of non-decreasing sizeExamples100=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.,Fundamental theorem of arithmetic:Strong Inductionfrom before,Show that if n is an integer greater than 1,then n can be written as the pro
46、duct 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
47、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,QED,Whats missing?,Uniqueness proof,soon,Composite factors,Theorem:If n is a composite integer,then n has a prime divisor less than or
48、 equal to the square root of nProofSince n is composite,it has a factor a such that 1 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 tha
49、n n,QED,44,Showing a number is prime,E.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 prime,How?,45,Showing a number is composite,Show that 899 is composite.SolutionD
50、ivide 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 23076923,12304:2 2 2 2 7693 5 7 3109 3769129485404038495:5 5897080807699294854040334945
