Number Theory Applications CSE235 Number Theory Applications Introduction Hash Functions Pseudorandom Numbers Slides by Christopher M Bourke Instructor Berthe Y Choueiry Representation of Integers Euclid s Algorithm C R T Spring 2006 Cryptography Computer Science Engineering 235 Introduction to Discrete Mathematics 1 109 Sections 2 4 2 6 of Rosen Number Theory Applications Number Theory Applications CSE235 Introduction Hash Functions Pseudorandom Numbers Results from Number Theory have countless applications in mathematics as well as in practical applications including security memory management authentication coding theory etc We will only examine in breadth a few here Representation of Integers Hash Functions Euclid s Algorithm Pseudorandom Numbers C R T Fast Arithmetic Operations Cryptography Cryptography 2 109 Hash Functions I Number Theory Applications CSE235 Introduction Hash Functions Pseudorandom Numbers Representation of Integers Euclid s Algorithm C R T Cryptography 3 109 Some notation Zm 0 1 2 m 2 m 1 Define a hash function h Z Zm as h k k mod m That is h maps all integers into a subset of size m by computing the remainder of k m Hash Functions II Number Theory Applications CSE235 In general a hash function should have the following properties Introduction It must be easily computable Hash Functions Representation of Integers It should distribute items as evenly as possible among all values addresses To this end m is usually chosen to be a prime number It is also common practice to define a hash function that is dependent on each bit of a key Euclid s Algorithm It must be an onto function surjective Pseudorandom Numbers C R T Cryptography 4 109 Hashing is so useful that many languages have support for hashing perl Lisp Python Hash Functions III Number Theory Applications CSE235 Introduction Hash Functions Pseudorandom Numbers Representation of Integers Euclid s Algorithm C R T Cryptography 5 109 However the function is clearly not one to one When two elements x1 6 x2 hash to the same value we call it a collision There are many methods to resolve collisions here are just a few Open Hashing aka separate chaining each hash address is the head of a linked list When collisions occur the new key is appended to the end of the list Closed Hashing aka open addressing when collisions occur we attempt to hash the item into an adjacent hash address This is known as linear probing Pseudorandom Numbers Number Theory Applications CSE235 Introduction Hash Functions Pseudorandom Numbers Representation of Integers Euclid s Algorithm C R T Cryptography 6 109 Many applications such as randomized algorithms require that we have access to a random source of information random numbers However there is not truly random source in existence only weak random sources sources that appear random but for which we do not know the probability distribution of events Pseudorandom numbers are numbers that are generated from weak random sources such that their distribution is random enough Pseudorandom Numbers I Linear Congruence Method Number Theory Applications One method for generating pseudorandom numbers is the linear congruential method CSE235 Introduction Choose four integers Hash Functions m the modulus Pseudorandom Numbers a the multiplier Representation of Integers c the increment and Euclid s Algorithm C R T x0 the seed Such that the following hold Cryptography 2 a m 0 c m 0 xo m 7 109 Pseudorandom Numbers II Linear Congruence Method Number Theory Applications CSE235 Introduction Hash Functions Pseudorandom Numbers Representation of Integers Euclid s Algorithm Our goal will be to generate a sequence of pseudorandom numbers xn n 1 with 0 xn m by using the congruence xn 1 axn c mod m For certain choices of m a c x0 the sequence xn becomes periodic That is after a certain point the sequence begins to repeat Low periods lead to poor generators C R T Cryptography Furthermore some choices are better than others a generator that creates a sequence 0 5 0 5 0 5 is obvious bad its not uniformly distributed For these reasons very large numbers are used in practice 8 109 Linear Congruence Method Example Number Theory Applications CSE235 Introduction Hash Functions Pseudorandom Numbers Representation of Integers Euclid s Algorithm C R T Cryptography 9 109 Example Let m 17 a 5 c 2 x0 3 Then the sequence is as follows xn 1 axn c mod m Linear Congruence Method Example Number Theory Applications CSE235 Introduction Hash Functions Pseudorandom Numbers Representation of Integers Euclid s Algorithm C R T Cryptography 10 109 Example Let m 17 a 5 c 2 x0 3 Then the sequence is as follows xn 1 axn c mod m x1 5 x0 2 mod 17 0 Linear Congruence Method Example Number Theory Applications CSE235 Introduction Hash Functions Pseudorandom Numbers Representation of Integers Euclid s Algorithm C R T Cryptography 11 109 Example Let m 17 a 5 c 2 x0 3 Then the sequence is as follows xn 1 axn c mod m x1 5 x0 2 mod 17 0 x2 5 x1 2 mod 17 2 Linear Congruence Method Example Number Theory Applications CSE235 Introduction Hash Functions Example Let m 17 a 5 c 2 x0 3 Then the sequence is as follows xn 1 axn c mod m x1 5 x0 2 mod 17 0 Pseudorandom Numbers x2 5 x1 2 mod 17 2 Representation of Integers x3 5 x2 2 mod 17 12 Euclid s Algorithm C R T Cryptography 12 109 Linear Congruence Method Example Number Theory Applications CSE235 Introduction Hash Functions Example Let m 17 a 5 c 2 x0 3 Then the sequence is as follows xn 1 axn c mod m x1 5 x0 2 mod 17 0 Pseudorandom Numbers x2 5 x1 2 mod 17 2 Representation of Integers x3 5 x2 2 mod 17 12 Euclid s Algorithm x4 5 x3 2 mod 17 11 C R T Cryptography 13 109 Linear Congruence Method Example Number Theory Applications CSE235 Introduction Hash Functions Example Let m 17 a 5 c 2 x0 3 Then the sequence is as follows xn 1 axn c mod m x1 5 x0 2 mod 17 0 Pseudorandom Numbers x2 5 x1 2 mod 17 2 Representation of Integers x3 5 x2 2 mod 17 12 Euclid s Algorithm x4 5 x3 2 mod 17 11 C R T x5 5 x4 2 mod 17 6 Cryptography 14 109 Linear Congruence Method Example Number Theory Applications CSE235 Introduction Hash Functions Example Let m 17 a 5 c 2 x0 3 Then the sequence is as follows xn 1 axn c mod m x1 5 x0 2 mod 17 0 Pseudorandom Numbers x2 5 x1 2 mod 17 2 Representation of Integers x3 5 x2 2 mod 17 12 Euclid s Algorithm x4 5 x3 2 mod 17 11 C R T x5 5 x4 2 mod 17 6 Cryptography x6 5 x5 2 mod 17 15 15 109 Linear Congruence Method Example Number Theory Applications CSE235 Introduction Hash Functions Example
View Full Document
Unlocking...