【正文】 r an opponent to “fake” a different document having the same ID. A Simple Hash Using mod Let the domain and codomain be the sets of all natural numbers below certain bounds: A = {a?N | a alim}, B = {b?N | b blim} Then an acceptable (although not great!) hash function from A to B (when alim≥blim) is h(a) = a mod blim. It has the following desirable hash function properties: – It covers or is onto its codomain B (its range is B). – When alim ? blim, then each b?B has a preimage of about the same size, ? Specifically, |h?1(b)| = ?alim/blim? or ?alim/blim?. A Simple Hash Using mod – However, it has the following limitations: ? It is not very random. Why not? ? It is definitely not cryptographically secure. – Given a b, it is easy to generate a’s that map to it. How? We know that for any n?N, h(b + n blim) = b. For example, if all a’s encountered happen to have the same residue mod blim, they will all map to the same b! (see also “spiral view”) But ok, if input data is uniformly distributed. Collision Because a hash function is not onetoone (there are more possible keys than memory locations) more than one record may be assigned to the same location ? we call this situation a collision. What to do when a collision happens? One possible way of solving a collision is to assign the first free location following the occupied memory location assigned by the hashing function. There are other ways… for example chaining (At each spot in the hash table, keep a linked list of keys sharing this hash value, and do a sequential search to find the one we need. ) Digital Signature Application Many digital signature systems use a cryptographically secure (but public) hash function h which maps arbitrarily long documents down to fixedlength (., 1,024bit) “fingerprint” strings. Document signing procedure: Signature verification procedure: – Given a document a and signature c, quickly find a’s hash b = h(a). – Compute b′ = f ?1(c). (Possible if f’s inverse f ?1 is made public (but not f ?).) – Compare b to b′。 in general, online security). 3 The divides operator New notation: 3 | 12 – To specify when an integer evenly divides another integer – Read as “3 divides 12” The notdivides operator: 5 | 12 – To specify when an integer does not evenly divide another integer – Read as “5 does not divide 12” 4 Divides, Factor, Multiple Let a,b?Z with a?0. Defn.: a|b ? “a divides b” :? (? c?Z: b=ac) “There is an integer c such that c times a equals b.” – Example: 3??12 ? True, but 3?7 ? False. Iff a divides b, then we say a is a factor or a divisor of b, and b is a multiple of a. Ex.: “b is even” :≡ 2|b. Is 0 even? Is ?4? 5 Results on the divides operator If a | b and a | c, then a | (b+c) – Example: if 5 | 25 and 5 | 30, then 5 | (25+30) If a | b, then a | bc for all integers c – Example: if 5 | 25, then 5 | 25*c for all ints c If a | b and b | c, then a | c – Example: if 5 | 25 and 25 | 100, then 5 | 100 (“mon facts” but good to repeat for background) 6 Divides Relation Theorem: ?a,b,c ? Z: 1. a|0 2. (a|b ? a|c) ? a | (b + c) 3. a|b ? a|bc 4. (a|b ? b|c) ? a|c Corollary: If a, b, c are integers, such that a | b and a | c, then a | mb + nc whenever m and n are integers. 7 Proof of (2) Show ?a,b,c ? Z: (a|b ? a|c) ? a | (b + c). Let a, b, c be any integers such that a|b and a|c, and show that a | (b + c). By defn. of | , we know ?s: b=as, and ?t: c=at. Let s, t, be such integers. Then b+c = as + at = a(s+t). So, ?u: b+c=au, namely u=s+t. Thus a|(b+c). QED Divides Relation Corollary: If a, b, c are integers, such that a | b and a | c, then a | mb + nc whenever m and n are integers. Proof: From previous theorem part 3 (., a|b ? a|be) it follows that a | mb and a | nc 。2 = 372?328 = 44. gcd(164,44) = gcd(44, 164 mod 44). – 164 mod 44 = 164?44 ?164/44? = 164?44 b) k+1 is a posite number and it can be written as the product of two positive integers a and b, with 2 ≤a ≤ b ≤ k+1. By the inductive hypothesis, a and b can be written as the product of primes, and so does k+1 , QED What’s missing? Uniqueness proof, soon… Composite factors Theorem: If n is a posite integer, then n has a prime divisor less than or equal to the square root of n Proof – Since n is posite, it has a factor a such that 1an – Thus, n = ab, where a and b are positive integers greater than 1 – Either a≤?n or b≤?n (Otherwise, assume a ?n and b ?n, then ab ?n*?n n. Contradiction.) – Thus, n has a divisor not exceeding ?n – This divisor is either prime or a posite ? If the latter, then it has a prime factor (by the FTA) – In either case, n has a prime factor less than ?n QED 44 Showing a number is prime ., show that 113 is prime. Solution – The only prime factors less than ?113 = are 2, 3, 5, and 7 – None of these divide 113 evenly – Thus, by the fundamental theorem of arithmetic, 113 must be prime How? 45 Showing a number is posite Show that 899 is posite. Solution – Divide 899 by successively larger primes, starting with 2 – We find that 29 and 31 divide 899 On a linux system or in cygwin, enter “factor 899” factor 899 899: 29 31 factor 89999999999999999 89999999999999999: 7 7 13 6122449 23076923 12304: 2 2 2 2 769 12304038495: 3 5 7 3109 37691 29485404038495: 5 5897080807699 294854040334945723: 67 2472061 1780217629 29485404033420344: 2 2 2 1109 3323422456427 294854043485472: 2 2 2 2 2 3 151 173 117574409 29485404203484: 2 2 3 101 103 229