This preview shows page 1-2-3-4-5-6-7-51-52-53-54-55-56-57-58-103-104-105-106-107-108-109 out of 109 pages.
IntroductionHash FunctionsPseudorandom NumbersRepresentation of IntegersInteger OperationsModular ExponentiationEuclid's AlgorithmComputing the inverseSolving a linear congruenceC.R.T.ArithmeticCryptographyCaesar CipherAffine CipherRSANumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyNumber Theory: ApplicationsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 2.4–2.6 of [email protected] / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyNumber Theory: ApplicationsResults from Number Theory have countless applications inmathematics as well as in practical applications includingsecurity, memory management, authentication, coding theory,etc. We will only examine (in breadth) a few here.Hash FunctionsPseudorandom NumbersFast Arithmetic OperationsCryptography2 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyHash 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 bycomputing the remainder of k/m.3 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyHash Functions IIIn general, a hash function should have the following propertiesIt must be easily computable.It 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 keyIt must be an onto function (surjective).Hashing is so useful that many languages have support forhashing (perl, Lisp, Python).4 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyHash 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 methods to resolve collisions, here are just afew.Open Hashing (aka separate chaining) – each hash addressis the head of a linked list. W hen collisions occur, the newkey is appended to the end of the list.Closed Hashing (aka open addressing) – when collisionsoccur, we attempt to hash the item into an adjacent hashaddress. This is known as linear probing.5 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyPseudorandom NumbersMany applications, such as randomized algorithms, require thatwe have access to a random source of information (randomnumbers).However, there is not truly random source in existence, onlyweak random sources: s ources t hat appear random, but forwhich we do not know the probability distribution of events.Pseudorandom numbers are numbers that are generated fromweak random sources such that their distribution is “randomenough”.6 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyPseudorandom Numbers ILinear Congruence MethodOne method for generating pseudorandom numbers is thelinear congruential method.Choose four integers:m, the modulus,a, the multiplier,c the increment andx0the seed.Such that the following hold:2 ≤ a < m0 ≤ c < m0 ≤ xo< m7 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyPseudorandom Numbers IILinear Congruence MethodOur goal will be to generate a sequence of pseudorandomnumbers,{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 generatorthat creates a sequence 0, 5, 0, 5, 0, 5, . . . is obvious bad—itsnot uniformly distributed.For these reasons, very large numbers are used in practice.8 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyLinear Congruence MethodExampleExampleLet m = 17, a = 5, c = 2, x0= 3. Then the sequence is asfollows.xn+1= (axn+ c) mod mx1= (5 · x0+ 2) mod 17 = 0x2= (5 · x1+ 2) mod 17 = 2x3= (5 · x2+ 2) mod 17 = 12x4= (5 · x3+ 2) mod 17 = 11x5= (5 · x4+ 2) mod 17 = 6x6= (5 · x5+ 2) mod 17 = 15x7= (5 · x6+ 2) mod 17 = 9x8= (5 · x7+ 2) mod 17 = 13 etc.9 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyLinear Congruence MethodExampleExampleLet m = 17, a = 5, c = 2, x0= 3. Then the sequence is asfollows.xn+1= (axn+ c) mod mx1= (5 · x0+ 2) mod 17 = 0x2= (5 · x1+ 2) mod 17 = 2x3= (5 · x2+ 2) mod 17 = 12x4= (5 · x3+ 2) mod 17 = 11x5= (5 · x4+ 2) mod 17 = 6x6= (5 · x5+ 2) mod 17 = 15x7= (5 · x6+ 2) mod 17 = 9x8= (5 · x7+ 2) mod 17 = 13 etc.10 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyLinear Congruence MethodExampleExampleLet m = 17, a = 5, c = 2, x0= 3. Then the sequence is asfollows.xn+1= (axn+ c) mod mx1= (5 · x0+ 2) mod 17 = 0x2= (5 · x1+ 2) mod 17 = 2x3= (5 · x2+ 2) mod 17 = 12x4= (5 · x3+ 2) mod 17 = 11x5= (5 · x4+ 2) mod 17 = 6x6= (5 · x5+ 2) mod 17 = 15x7= (5 · x6+ 2) mod 17 = 9x8= (5 · x7+ 2) mod 17 = 13 etc.11 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof IntegersEuclid’sAlgorithmC.R.T.CryptographyLinear Congruence MethodExampleExampleLet m = 17, a = 5, c = 2, x0= 3. Then the sequence is asfollows.xn+1= (axn+ c) mod mx1= (5 · x0+ 2) mod 17 = 0x2= (5 · x1+ 2) mod 17 = 2x3= (5 · x2+ 2) mod 17 = 12x4= (5 · x3+ 2) mod 17 = 11x5= (5 · x4+ 2) mod 17 = 6x6= (5 · x5+ 2) mod 17 = 15x7= (5 · x6+ 2) mod 17 = 9x8= (5 · x7+ 2) mod 17 = 13 etc.12 / 109NumberTheory:ApplicationsCSE235IntroductionHashFunctionsPseudorandomNumbersRepresentationof
View Full Document
Unlocking...