Number Theory: ApplicationsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 2.4–2.6 of [email protected] Theory: ApplicationsResults from Number Theory have countless applications inmathematics as well as in practical applications including security,memory management, authentication, c oding theory, etc. We willonly examine (in breadth) a few here.IHash FunctionsIPseudorandom NumbersIFast Arithmetic OperationsICryptographyHash 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 computingthe remainder of k /m.Hash Functions IIIn general, a hash function should have the following propertiesIIt must be easily com putable.IIt should distribute items as evenly as poss ible 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).Hash Functions IIIHowever, the function is clearly not one-to-one. When twoelements, x16= x2hash to the same value, we call it a collision.There are many met hods 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 open addressing) – when collisions occur,we atte mpt to hash the item into an adjacent hash address.This is known as linear probing.Pseudorandom 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 ev ents.Pseudorandom numbers are numbers that are generated from weakrandom sources such that their distribution is “random enough”.Pseudorandom 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< mPseudorandom 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.Linear 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.Representation of Integers IThis should be old-hat to you, but we revie w 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, e ach coefficient aiis an integer between 0 andb − 1 inclusive.Representation 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 us e the notation(akak−1· · · a2a1a0)bFor b = 10, we omit the parentheses and subscript. We also omitleading 0s.Representation 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)16Base ExpansionAlgorithmThere is a simple and obvious algorithm to c ompute 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?Integer 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.Modular Exponentiation IOne useful arithmetic operation that is greatly simplified ismodular exponentiation.Say we want to computeαnmod mwhere n is a very large integer. We could simply computeα · α · · · · · α| {z }n timesWe m ake sure to mod each time we multiply to prevent theproduct from growing too big. This requires O(n) operations.We c an do better. Intuitively, we can perform a repeated squaringof the base,α, α2, α4, α8, . . .Modular 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 c an compute αnby evaluating each term asαbi2i=α2iif bi= 11 if bi= 0We c an save c omputation because we can simply square previousvalues:α2i= (α2i−1)2Modular Exponentiation I IIWe s till ev aluate each term independently however, since we willneed it in the next term (though the accumulated value is onlymultiplied by 1).Modular Exponentiation IVModular ExponentiationInput : Integers α, m and n = (bkbk−1. . . b1b0) in binary.Output : αnmod mterm = α1if (b0= 1) then2product = α3end4else5product = 16end7for i = 1 . . . k do8term = term × term mod m9if (bi= 1) then10product = product × term mo d
View Full Document
Unlocking...