1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 14Milos [email protected] Sennott SquareIntegers: applications, base conversions.M. HauskrechtCS 441 Discrete mathematics for CSModular arithmetic in CSModular arithmetic and congruencies are used in CS:– Pseudorandom number generators– Hash functions– Cryptology2M. HauskrechtCS 441 Discrete mathematics for CSPseudorandom number generators• Some problems we want to program need to simulate a random choice. • Examples: flip of a coin, roll of a diceWe need a way to generate random outcomes Basic problem: – assume outcomes: 0, 1, .. N– generate the random sequences of outcomes• Pseudorandom number generators let us generate sequences that look random• Next: linear congruential methodM. HauskrechtCS 441 Discrete mathematics for CSPseudorandom number generatorsLinear congruential method• We choose 4 numbers:• the modulus m, • multiplier a, • increment c, and • seed x0, such that 2 =< a < m, 0 =< c < m, 0 =< x0< m.• We generate a sequence of numbers x1, x2x3 ... xn ... such that 0 =< xn< m for all n by successively using the congruence:• xn+1= (a.xn+ c) mod m3M. HauskrechtCS 441 Discrete mathematics for CSPseudorandom number generatorsLinear congruential method: •xn+1= (a.xn+ c) mod mExample: • Assume : m=9,a=7,c=4, x0= 3•x1= 7*3+4 mod 9=25 mod 9 =7•x2= 53 mod 9 = 8•x3= 60 mod 9 = 6•x4= 46 mod 9 =1•x5= 11 mod 9 =2•x6= 18 mod 9 =0• ....M. HauskrechtCS 441 Discrete mathematics for CSHash functionsA hash function is an algorithm that maps data of arbitrary length to data of a fixed length.The values returned by a hash function are called hash values or hash codes. Example: JohnMaryPeterAnnCharles0001020304..19Hash function4M. HauskrechtHash functions• Problem: Given a large collection of records, how can we store and find a record quickly?• Solution: Use a hash function calculate the location of the record based on the record’s ID. • Example: A common hash function is • h(k) = k mod n, where n is the number of available storage locations.012345678ID: 35 35 mod 9= 8ID: 21 21 mod 9= 3M. HauskrechtCS 441 Discrete mathematics for CSHash functionAn example of a hash function that maps integers (including very large ones) to a subset of integers 0, 1, .. m-1 is: h(k) = k mod mExample: Assume we have a database of employes, each with a unique ID – a social security number that consists of 8 digits. We want to store the records in a smaller table with m entries. Using h(k) function we can map a social secutity number in the database of employes to indexes in the table. Assume: h(k) = k mod 111Then: h(064212848) = 064212848 mod 111 = 14h(037149212) = 037149212 mod 111 = 655M. HauskrechtHash functions• Problem: two documents mapped to the same location012345678ID: 39 39 mod 9= 3ID: 21 21 mod 9= 3M. HauskrechtHash functions• Solution 1: move the next available location– Method is represented by a sequence of hash functions to try01 2 345678ID: 39 39 mod 9= 3ID: 21 21 mod 9= 3h0(k) = k mod nh1(k) = (k+1) mod n…hm(k) = (k+m) mod n6M. HauskrechtHash functions• Solution 2: remember the exact location in a secondary structure that is searched sequentially012345678ID: 39 39 mod 9= 3ID: 21 21 mod 9= 3ID: 21Loc: 3ID: 39Loc: 4M. HauskrechtCS 441 Discrete mathematics for CSCryptologyEncryption of messages.• Ceasar cipher: • Shift letters in the message by 3, last three letters mapped to the first 3 letters, e.g. A is shifted to D, X is shifted to A How to represent the idea of a shift by 3?• There are 26 letters in the alphabet. Assign each of them a number from 0,1, 2, 3, .. 25 according to the alphabetical order. A B C D E F G H I J K L M N O P Q R S T U Y V X W Z0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25• The encryption of the letter with an index p is represented as:• f(p) = (p + 3) mod 267M. HauskrechtCS 441 Discrete mathematics for CSCryptologyEncryption of messages using a shift by 3.• The encryption of the letter with an index p is represented as:• f(p) = (p + 3) mod 26Coding of letters:A B C D E F G H I J K L M N O P Q R S T U Y V X W Z0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25• Encrypt message:– I LIKE DISCRETE MATH–M. HauskrechtCS 441 Discrete mathematics for CSCryptologyEncryption of messages using a shift by 3.• The encryption of the letter with an index p is represented as:• f(p) = (p + 3) mod 26Coding of letters:A B C D E F G H I J K L M N O P Q R S T U Y V X W Z0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25• Encrypt message:– I LIKE DISCRETE MATH– L 0LNH GLYFUHVH PDVK.8M. HauskrechtCS 441 Discrete mathematics for CSCryptologyHow to decode the message ? • The encryption of the letter with an index p is represented as:• f(p) = (p + 3) mod 26Coding of letters:A B C D E F G H I J K L M N O P Q R S T U Y V X W Z0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25• What method would you use to decode the message:• f-1(p) = (p-3) mod 26M. HauskrechtRepresentations of Integers• In the modern world, we use decimal, or base 10, notation to represent integers. For example when we write 965, we mean 9·102 + 6·101 + 5·100 . • We can represent numbers using any base b, where b is a positive integer greater than 1.• The bases b = 2 (binary), b = 8 (octal) , and b= 16 (hexadecimal) are important for computing and communications• The ancient Mayans used base 20 and the ancient Babylonians used base 60.9M. HauskrechtBase b Representations• We can use positive integer b greater than 1 as a baseTheorem 1: Let b be a positive integer greater than 1. Then if n is a positive integer, it can be expressed uniquely in the form:n = akbk+ ak-1bk-1+ …. + a1b + a0where k is a nonnegative integer, a0,a1,…. akare nonnegative integers less than b, and ak≠ 0. The aj, j = 0,…,k are called the base-b digits of the representation.• The representation of n given in Theorem 1 is called the base b expansion of n and is denoted by (akak-1….a1a0)b.• We usually omit the subscript 10 for base 10 expansions.M. HauskrechtBinary ExpansionsMost computers represent integers and do arithmetic with binary (base 2) expansions of