离散数学 数论.pptVIP

Discrete MathCS 2800;The Integers and Division;The divides operator;Divides, Factor, Multiple;Results on the divides operator;Divides Relation;Proof of (2) ;Divides Relation;The Division “Algorithm”;What are the quotient and remainder when 101 is divided by 11? ;If a = 7 and d = 3, then q = 2 and r = 1, since 7 = (2)(3) + 1. If a = ?7 and d = 3, then q = ?3 and r = 2, since ?7 = (?3)(3) + 2. ;Theorem:Division “Algorithm” --- Let a be an integer and d a positive integer. Then there are unique integers q and r, with 0 ≤rd, such that a=dq+r.;(Existence, cont.) r is non-negative; also, r d. otherwise if r≥ d, there would be a smaller nonnegative element in S, namely a - d(q0+1) ≥ 0. But then a-d(q0+1), which is smaller than a-dq0, is an element of S, contradicting that a-dq0 was the smallest element of S. So, it cannot be the case that r ≥ d, proving the existence of 0 ≤ r d and q.;b) Uniqueness Suppose ;Modular arithmetic;Time-keeping on a clock gives an example of modular arithmetic. (mod 12 in the US; or mod 24, using the 24hr clock. Naturally imposed by the periodicity of earth’s rotation.);Spiral Visualization of mod;More on congruences;Even even more on congruence;Applications of Congruences;Hashing Functions;Hash Functions ;Hash Function Requirements;Why are these important?;Hash Function Requirements;A Simple Hash Using mod;A Simple Hash Using mod;Collision;Digital Signature Application;Pseudorandom numbers;Pseudorandom numbers;;Pseudorandom numbers;3 million random bits per dollar Quite a bargain…;Cryptology(secret messages);The Caesar cipher;The Caesar cipher;Rot13 encoding;Primes and Greatest Common Divisor;Prime numbers;Fundamental theorem of arithmetic;Fundamental theorem of arithmetic: Strong Induction[from before];Composite factors;Showing a number is prime;Showing a number is composite; On a linux system or in cygwin, enter “factor 899” factor 899 899: 29 31 factor 89999999999999999 89999999999999999: 7 7 13 612244912304: