Notes Number Theory Applications Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 3 4 3 7 of Rosen cse235 cse unl edu Number Theory Applications Notes 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 I Hash Functions Sect 3 4 p 205 Example 7 I Pseudorandom Numbers Sect 3 4 p 208 Example 8 I Fast Arithmetic Operations Sect 3 6 p 223 I Linear congruences C R T Cryptography Sect 3 6 3 7 Hash Functions I Notes 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 Notes In general a hash function should have the following properties I It must be easily computable I 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 I It must be an onto function surjective Hashing is so useful that many languages have support for hashing perl Lisp Python Hash Functions III Notes 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 I 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 I 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 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 Notes Pseudorandom Numbers I Notes Linear Congruence Method One method for generating pseudorandom numbers is the linear congruential method Choose four integers I m the modulus I a the multiplier I c the increment and I x0 the seed Such that the following hold I 2 a m I 0 c m I 0 xo m Pseudorandom Numbers II Notes Linear Congruence Method 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 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 Linear Congruence Method Example Example Let m 17 a 5 c 2 x0 3 Then the sequence is as follows I xn 1 axn c mod m I x1 5 x0 2 mod 17 0 I x2 5 x1 2 mod 17 2 I x3 5 x2 2 mod 17 12 I x4 5 x3 2 mod 17 11 I x5 5 x4 2 mod 17 6 I x6 5 x5 2 mod 17 15 I x7 5 x6 2 mod 17 9 I x8 5 x7 2 mod 17 13 etc Notes Representation of Integers I Notes This should be old hat to you but we review it to be complete it is also discussed in great detail in your textbook Any integer n can be uniquely expressed in any base b by the following expression n ak bk ak 1 bk 1 a2 b2 a1 b a0 In the expression each coefficient ai is an integer between 0 and b 1 inclusive Representation of Integers II Notes For 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 ak ak 1 a2 a1 a0 b For b 10 we omit the parentheses and subscript We also omit leading 0s Representation of Integers Example Example B9 16 271 8 1011 1001 2 11 161 9 160 176 9 185 2 82 7 81 1 80 128 56 1 185 1 27 0 26 1 25 1 24 1 23 0 22 0 21 1 20 185 You can verify the following on your own 134 1000 0110 2 206 8 86 16 44613 1010 1110 0100 0101 2 127105 8 AE45 16 Notes Base Expansion Notes Algorithm There is a simple and obvious algorithm to compute the base b expansion of an integer Base b Expansion 1 2 3 4 5 6 Input A nonnegative integer n and a base b Output The base b expansion of n q n k 0 while q 6 0 do ak q mod b q b qb c k k 1 7 end 8 output ak 1 ak 2 a1 a0 What is its complexity Integer Operations I Notes You should already know how to add and multiply numbers in binary 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 for q a div d r a mod d The algorithm runs in O q log a but an algorithm that runs in O log q log a exists Modular Exponentiation I Notes One useful arithmetic operation that is greatly simplified is modular exponentiation Say we want to compute n mod m where n is a very large integer We could simply compute z n times We make sure to mod each time we multiply to prevent the product from growing too big This requires O n operations We can do better Intuitively we can perform a repeated squaring of the base 2 4 8 Modular Exponentiation II Notes requiring log n operations instead Formally we note that k k 1 n bk 2 bk 1 2 b1 2 b0 k k 1 bk 2 bk 1 2 2b1 b0 So we can compute n by evaluating each term as i bi 2 2 1 i if bi 1 if bi 0 We can save computation because we can simply square previous values i i 1 2 2 2 Modular Exponentiation III Notes We still evaluate each …
View Full Document
Unlocking...