《离散数学数论.ppt》由会员分享，可在线阅读，更多相关《离散数学数论.ppt（127页珍藏版）》请在三一办公上搜索。
1、Discrete MathCS 2800,Prof.Bart SelmanModule Number TheoryRosen,Sections 3-4 to 3-7.,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 know.
2、These form the basics of number theory.Vital in many important algorithms today(hash functions,cryptography,digital signatures;in general,on-line security).,The divides operator,New notation:3|12To specify when an integer evenly divides another integerRead as“3 divides 12”The not-divides operator:5|
3、12To specify when an integer does not evenly divide another integerRead as“5 does not divide 12”,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 factor or a
4、divisor of b,and b is a multiple of a.Ex.:“b is even”:2|b.Is 0 even?Is 4?,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 and 25|100,t
5、hen 5|100,(“common facts”but good to repeat for background),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.,Proof of(2),Show a,b,c Z:(a|b a|c)a|(b+c).Let a,b,c be any in
6、tegers 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 integers.Proof:Fr
7、om 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,The Division“Algorithm”,Theorem:Division Algorithm-Let a be an integer and d a positive integer.Then there are unique integers q and r,with 0 r d,suc
8、h 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,What are the quotient and remainder when 101 is divided by 11?,q is called the quotient r is calle
9、d the remainder d is called the divisor a is called the dividend,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 that what remains,r,is l
10、ess 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 and r,with 0 rd,such th
11、at 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 integer with large absolute
12、 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 element in S,namely a-d(q
13、0+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 called the dividend,b
14、)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 dq=d Q(note d0)and th
15、us 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 17 congruent to 5 modu
16、lo 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.,Time-keeping on a clock gives an e
17、xample 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 shown:modulo-5arithmetic
18、,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 let m be a positive inte
19、ger.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,Even even more on congruence,Theorem:Let m be a positive
20、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),Applications of Congruences,Hashing Functions,Also known as:hash functions,hash codes,or just hashes.Two major
21、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.,Hash Functions,Example:Consider a a record that is identified by the SSN(9 digits)of the customer
22、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 identifies each record.If you comput
23、e the hash of the same data at different times,you should get the same answer if not then the data has been modified.,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 the following properties:It should cover(b
24、e 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 appear random,so that clearly“similar”elemen
25、ts of A are not likely to map to the same(or similar)elements of B.,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 sender claiming to have sent x2 when in fact
26、 the message was x1.,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 would take exponential time in the length of an
27、 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 from A to B(when alimblim)is h(a)=a mod blim.It
28、 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 has the following limitations:It is not very ran
29、dom.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 d
30、ata 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 happens?One possible way of solving a collisio
31、n 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.),Digital Sign
32、ature 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 procedure:,Given a document a and signature c,qu
33、ickly 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,
34、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
35、to the whole document.Deliver the original document together with the digital signature c.,What if h was not cryptographically secure?,Pseudorandom numbers,Pseudorandom numbers,Computers cannot generate truly random numbers thats why we call them pseudo-random numbers!Linear Congruential Method:Algo
36、rithm 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 formula:xn+1=(axn+c)mod m,Pseudorandom numbers,Formula:
37、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,Quite random!,Pseudorandom numbers,Formula:xn+1=(axn+c)mod
38、 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 before it repeatsMultiplier 75=16,807 and increment c=0(pure
39、multiplicative generator),3 million random bits per dollarQuite a bargain,Cryptology(secret messages),The Caesar cipher,Julius Caesar used the following procedure to encrypt messagesA function f to encrypt a letter is defined as:f(p)=(p+3)mod 26Where p is a letter(0 is A,1 is B,25 is Z,etc.)Decrypti
40、on:f-1(p)=(p-3)mod 26This is called a substitution cipherYou are substituting one letter with another,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 cipher to each number:f(6)=9,f(14)=17,etc.Full sequence:9,17,5,3,24,3,14,11
41、,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)=14,etc.Full sequence:6,14,2,0,21,0,11,8,4,17,18Convert the numbers bac
42、k to letters 6=g,14=0,etc.Full sequence:“go cavaliers”,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 Hello World|rot13Uryyb Jbeyq echo Uryyb Jbeyq|rot13Hello World,Primes and Gr
43、eatest Common Divisor,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 classAn integer n is composite if and only if there exists an integer a such that
44、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 written inorder of non-decreasing sizeExamples100=2*2*5*5182=2*7*1329820=2*2*
45、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 product of primes.1-Hypothesis P(n)-n can be written as the product of primes.2
46、 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
47、 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 equal to the square root of nProofSince n is composite,it has a factor a su
48、ch 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 than n,QED,Showing a number is prime,E.g.,show that 113 is prime.SolutionThe on
49、ly 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?,Showing a number is composite,Show that 899 is composite.SolutionDivide 899 by successively larger primes,starting with 2We find that 29 and 31 divi
50、de 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 5897080807699294854040334945723:67 2472061 178021762929485404033420344:2 2 2 1109 3323422456427294854043485472
