《离散数学数论》PPT课件.ppt
《《离散数学数论》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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学数论 离散数学 数论 PPT 课件
链接地址:https://www.31ppt.com/p-5588171.html