Number Theory: ApplicationsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 3.4–3.7 of [email protected] Theory: ApplicationsResults from Number Theory have countless applications inmathematics as well as in practical applications including security,memory management, authentication, coding theory, etc. We willonly examine (in breadth) a few here.IHash Functions (Sect. 3.4, p. 205, Example 7)IPseudorandom Numbers (Sect. 3.4, p. 208, Example 8)IFast Arithmetic Operations (Sect. 3.6, p. 223)ILinear congruences, C.R.T., Cryptography (Sect. 3.6 & 3.7)NotesHash Functions ISome notation: Zm= {0, 1, 2, . . . , m − 2, m − 1}Define a hash function h : Z → Zmash(k) = k mod mThat is, h maps all integers into a subset of size m by c omputingthe remainder of k/m.NotesHash Functions IIIn general, a hash function should have the following propertiesIIt must be easily computable.IIt should distribute items as evenly as possible among allvalues addresses. To this end, m is usually chosen to be aprime number. It is also common practice to define a hashfunction that is dependent on each bit of a keyIIt must be an onto function (surjective).Hashing is so useful that many languages have support for hashing(perl, Lisp, Python).NotesHash Functions IIIHowever, the function is clearly not one-to-one. When twoelements, x16= x2hash to the same value, we c all it a collision.There are many methods to resolve collisions, here are just a few.IOpen Hashing (aka separate chaining) – each hash address isthe head of a linked list. When collisions occur, the new key isappended to the end of the list.IClosed Hashing (aka op e n addressing) – when collisions occur,we attempt to hash the item into an adjacent hash address.This is known as linear probing.NotesPseudorandom NumbersMany applications, such as randomized algorithms, require that wehave access to a random source of information (random numbers).However, there is not truly random source in existence, only weakrandom sources: sources that appear random, but for which we donot know the probability distribution of events.Pseudorandom numbers are numbers that are generated from weakrandom sources such that their distribution is “random enough”.NotesPseudorandom Numbers ILinear Congruence MethodOne method for generating pseudorandom numbers is the linearcongruential method.Choose four integers:Im, the modulus,Ia, the multiplier,Ic the increment andIx0the seed.Such that the following hold:I2 ≤ a < mI0 ≤ c < mI0 ≤ xo< mNotesPseudorandom Numbers IILinear Congruence MethodOur goal will be to generate a sequence of pseudorandom numbers,{xn}∞n=1with 0 ≤ xn≤ m by using the congruencexn+1= (axn+ c) mod mFor certain choices of m, a, c, x0, the sequence {xn} becomesperiodic. That is, after a certain point, the sequence begins torepeat. Low periods lead to poor generators.Furthermore, some choices are better than others; a generator thatcreates a sequence 0, 5, 0, 5, 0, 5, . . . is obvious bad—its notuniformly distributed.For these reasons, very large numbers are used in practice.NotesLinear Congruence MethodExampleExampleLet m = 17, a = 5, c = 2, x0= 3. Then the sequence is as follows.Ixn+1= (axn+ c) mod mIx1= (5 · x0+ 2) mod 17 = 0Ix2= (5 · x1+ 2) mod 17 = 2Ix3= (5 · x2+ 2) mod 17 = 12Ix4= (5 · x3+ 2) mod 17 = 11Ix5= (5 · x4+ 2) mod 17 = 6Ix6= (5 · x5+ 2) mod 17 = 15Ix7= (5 · x6+ 2) mod 17 = 9Ix8= (5 · x7+ 2) mod 17 = 13 etc.NotesRepresentation of Integers IThis should be old-hat to you, but we review it to be complete (itis also discussed in great detail in your textbook).Any integer n can be uniquely expressed in any base b by thefollowing expression.n = akbk+ ak−1bk−1+ · · · + a2b2+ a1b + a0In the expression, each coefficient aiis an integer between 0 andb − 1 inclusive.NotesRepresentation of Integers IIFor b = 2, we have the usual binary representation.b = 8, gives us the octal representation.b = 16 gives us the hexadecimal representation.b = 10 gives us our usual decimal system.We use the notation(akak−1· · · a2a1a0)bFor b = 10, we omit the parentheses and subscript. We also omitleading 0s.NotesRepresentation of IntegersExampleExample(B9)16= 11 · 161+ 9 · 160= 176 + 9 = 185(271)8= 2 · 82+ 7 · 81+ 1 · 80= 128 + 56 + 1= 185(1011 1001)2= 1 · 27+ 0 · 26+ 1 · 25+ 1 · 24+ 1 · 23+0 · 22+ 0 · 21+ 1 · 20= 185You can verify the following on your own:134 = (1000 0110)2= (206)8= (86)1644613 = (1010 1110 0100 0101)2= (127105)8= (AE45)16NotesBase ExpansionAlgorithmThere is a simple and obvious algorithm to compute the base bexpansion of an integer.Base b ExpansionInput : A nonnegative integer n and a base b.Output : The base b expansion of n.q ← n1k ← 02while q 6= 0 do3ak← q mod b4q ← bqbc5k ← k + 16end7output (ak−1ak−2· · · a1a0)8What is its complexity?NotesInteger Operations IYou should already know how to add and multiply numbers inbinary expansions.If not, we can go through some examples.In the textbook, you have 3 algorithms for computing:1. Addition of two integers in binary expansion; runs in O(n).2. Product of two integers in binary expansion; runs in O(n2)(an algorithm that runs in O(n1.585) exists).3. div and mod forq = a div dr = a mod dThe algorithm runs in O(q log a) but an algorithm that runs inO(log q log a) exists.NotesModular Exponentiation IOne useful arithmetic operation that is greatly simplified ismodular exponentiation.Say we want to com puteαnmo d mwhere n is a very large intege r. We could simply computeα · α · · · · · α| {z }n timesWe make sure to mod each time we multiply to prevent theproduct from growing too big. This requires O(n) operations.We can do better. Intuitively, we can perform a repeated squaringof the base,α, α2, α4, α8, . . .NotesModular Exponentiation I Irequiring log n operations instead.Formally, we note thatαn= αbk2k+bk−12k−1+···+b12+b0= αbk2k× αbk−12k−1× · · · × α2b1× αb0So we can compute αnby evaluating each term asαbi2i=α2iif bi= 11 if bi= 0We can save computation because we can simply square previousvalues:α2i= (α2i−1)2NotesModular Exponentiation I IIWe still evaluate each term independently however, since we willneed it in the next term (though the accumulated value is onlymultiplied by 1).NotesModular Exponentiation IVModular ExponentiationInput : Integers α, m and n = (bkbk−1. . .
View Full Document
Unlocking...