# Discrete Math CS 2800 Prof. Bart Selman [email protected] Discrete Math CS 2800 Prof. Bart Selman [email protected] Module Number Theory 1 The Integers and Division Of course, you already know what the integers are, and what division is However: There are some specific notations, terminology, and theorems

associated with these concepts which you may not know. These form the basics of number theory. Vital in many important algorithms today (hash functions, cryptography, digital signatures; in general, on-line security). 2 The divides operator New notation: 3 | 12 To specify when an integer evenly divides another integer Read as 3 divides 12 The not-divides operator: 5 | 12

To specify when an integer does not evenly divide another integer Read as 5 does not divide 12 3 Divides, Factor, Multiple Let a,bZ with a0. Def.: a|b a divides b : ( cZ: b=ac) There is an integer c such that c times a equals b. Example: 312 True, but 37 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?

4 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

(common facts but good to repeat for background) 5 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 Proof of (2): a|b means there is an s such that b=as, and a|c means that there is a t such that c=at, so b+c = as+at = a(s+t), so a|(b+c) also. Corollary: If a, b, c are integers, such that a | b and a | c, then

a | mb + nc whenever m and n are integers. 6 More Detailed Version of Proof 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). 7

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 (i.e., a|b a|be) it follows that a | mb and a | nc ; again, from previous theorem part 2 (i.e., (a|b a|c) a | (b + c)) it follows that a | mb + nc The Division Algorithm Theorem: Division Algorithm --- Let a be an integer and d a positive integer. Then there are unique integers q and r, with 0 r < d, such that a = dq+r. Its really just a theorem, not an algorithm

Only called an algorithm for historical reasons. q is called the quotient r is called the remainder d is called the divisor a is called the dividend 9 q is called the quotient r is called the remainder d is called the divisor a is called the dividend What are the quotient and remainder when 101 is divided by 11?

a d q r 101 = 11 9 + 2 We write: q = 9 = 101 div 11 r = 2 = 101 mod 11 10 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. So: given positive a and (positive) d, in order to get r we repeatedly subtract d from a, as many times as needed so that what remains, r, is

less than d. Given negative a and (positive) d, in order to get r we repeatedly add d to a, as many times as needed so that what remains, r, is positive (or zero) and less than d. 11 Theorem: Division Algorithm --- Let a be an integer and d a positive integer. Then there are unique integers q and r, with 0 r

Consider the set of non-negative numbers of the form a - dq, where q is an integer. Hmm. Can this set be empty? Note: this set is non empty since q can be a negative integer with large absolute value). By the well-ordering property, S has a least element, r = a - d q 0. (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.

QED b) Uniqueness (note standard proof structure) Suppose q, Q, R 0 r , R d such that a dq r and a dQ R. Without loss of generality we may assume that q Q. Subtracting both equations we have: d (q-Q) = (R r) So d divides (R-r); so, either |d| |(R

(*) r)| or (R r) = 0; Since d < R - r < d (because 0 r , R d ) i.e., |R-r| < d, we must have R r = 0. So, R = r. Substituting into the original two equations, we have dq = d Q (note d0) and thus q=Q, proving uniqueness. (or directly from (*)) QED

Modular arithmetic If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m divides a-b Notation: a b (mod m) Rephrased: m | a-b Rephrased: a mod m = b mod m If they are not congruent: a b (mod m) Example: Is 17 congruent to 5 modulo 6? Rephrased: 17 5 (mod 6) As 6 divides 17-5, they are congruent Example: Is 24 congruent to 14 modulo 6? Rephrased: 24 14 (mod 6)

As 6 does not divide 24-14 = 10, they are not congruent Note: this is a different use of than the meaning is defined as used before. Spiral Visualization of mod Example shown: modulo-5 arithmetic The spiral/circular view is useful to keep in mind when doing modular arithmetic! 0

(mod 5) 20 15 10 4 19 14 9 (mod 5) 4 8 1 (mod 5)

5 0 3 13 18 3 (mod 5) So, e.g., 19 is congruent to 9 modulo 5. 2

1 6 11 16 21 Congruence classes modulo 5. 7

12 17 22 2 (mod 5) More on congruence Theorem: Let a and b be integers, and let m be a positive integer. Then a b (mod m) if and only if a mod m = b mod m Even more on congruence Theorem: Let m be a positive integer. The integers a and b are congruent modulo m if and

only if there is an integer k such that a = b + km Example: 17 and 5 are congruent modulo 6, so 17 = 5 + 2*6 5 = 17 - 2*6 18 Even even more on congruence Theorem: Let m be a positive integer. If a b (mod m) and c d (mod m), then a+c (b+d) (mod m) and ac bd (mod m) Example We know that 7 2 (mod 5) and 11 1 (mod 5)

Thus, 7+11 (2+1) (mod 5), or 18 3 (mod 5) Thus, 7*11 2*1 (mod 5), or 77 2 (mod 5) 19 Applications of Congruences 20 Hashing Functions Also known as: hash functions, hash codes, or just hashes.

Two major uses: Indexing hash tables Data structures which support O(1)-time access. Creating short unique IDs for long documents. Used in digital signatures the short ID can be signed, rather than the long document. 21 Hash Functions Example: Consider a a record that is identified by the SSN (9 digits) of the customer.

How can we assign a memory location to a record so that later on its easy to locate and retrieve such a record? Solution to this problem a good hashing function. Records are identified using a key (k), which uniquely identifies each record. If you compute the hash of the same data at different times, you should get the same answer if not then the data has been modified. 22 Hash Function Requirements A hash function h: AB is a map from a set A to a smaller set B (i.e., |A| |B|). An effective hash function should have the following properties: It should cover (be onto) its codomain B.

It should be efficient to calculate. The cardinality of each pre-image of an element of B should be about the same. b1,b2B: |h1(b1)| |h1(b2)| That is, elements of B should be generated with roughly uniform probability. Ideally, the map should appear random, so that clearly similar elements of A are not likely to map to the same (or similar) elements of B. 23 Why are these important? To make computations fast and efficient. So that any message can be hashed.

To prevent a message being replaced with another with the same hash value. To prevent the sender claiming to have sent x2 when in fact the message was x1. 24 Hash Function Requirements Furthermore, for a cryptographically secure hash function: Given an element bB, the problem of finding an aA such that h(a)=b should have average-case time complexity of (|B|c) for some c>0. This ensures that it would take exponential time in the length of an ID for an opponent to fake a different document having the same ID. 25

A Simple Hash Using mod Let the domain and codomain be the sets of all natural numbers below certain bounds: A = {aN | a < alim}, B = {bN | b < blim} Then an acceptable (although not great!) hash function from A to B (when alimblim) 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 bB has a preimage of about the same size, Specifically, |h1(b)| = alim/blim or alim/blim.

A Simple Hash Using mod However, it has the following limitations: It is not very random. Why not? For example, if all as encountered happen to have the same residue mod blim, they will all map to the same b! (see also spiral view) It is definitely not cryptographically secure. Given a b, it is easy to generate as that map to it. How? We know that for any nN, h(b + n blim) = b. Collision

Because a hash function is not one-to-one (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 fixed-length (e.g.,

1,024-bit) fingerprint strings. Document signing procedure: Given a document a to sign, quickly compute its hash b = h(a). Compute a certain function c = f(b) that is known only to the signer This step is generally slow, so we dont want to apply it to the whole document. Deliver the original document together with the digital signature c. Signature verification procedure: Given a document a and signature c, quickly find as hash b = h(a). Compute b = f 1(c). (Possible if fs inverse f 1 is made public (but not f ).) Compare b to b; if they are equal then the signature is valid. What if h was not cryptographically secure? Note that if h were not cryptographically secure, then an opponent could easily forge a different document a that hashes to the same value b, and thereby attach

someones digital signature to a different document than they actually signed, and fool the verifier! Pseudorandom numbers 30 Pseudorandom numbers Computers cannot generate truly random numbers thats why we call them pseudo-random numbers! Linear Congruential Method: Algorithm for generating pseudorandom numbers. Choose 4 integers

Seed x0: starting value Modulus m: maximum possible value Multiplier a: such that 2 a < m Increment c: between 0 and m In order to generate a sequence of pseudorandom numbers, {xn | 0 xn

Pseudorandom numbers Formula: xn+1 = (axn + c) mod m Let x0 = 3, m = 9, a = 7, and c = 4 x1 = 7x0+4 = 7*3+4 = 25 mod 9 = 7 x2 = 7x1+4 = 7*7+4 = 53 mod 9 = 8 x3 = 7x2+4 = 7*8+4 = 60 mod 9 = 6 x4 = 7x3+4 = 7*6+4 = 46 mod 9 = 1 x5 = 7x4+4 = 7*1+4 = 46 mod 9 = 2 x6 = 7x5+4 = 7*2+4 = 46 mod 9 = 0 x7 = 7x6+4 = 7*0+4 = 46 mod 9 = 4 x8 = 7x7+4 = 7*4+4 = 46 mod 9 = 5 32

Pseudorandom numbers Formula: xn+1 = (axn + c) mod m Let x0 = 3, m = 9, a = 7, and c = 4 This sequence generates: 3, 7, 8, 6, 1, 2, 0, 4, 5, 3 , 7, 8, 6, 1, 2, 0, 4, 5, 3 Note that it repeats! But it selects all the possible numbers before doing so The common algorithms today use m = 232-1 You have to choose 4 billion numbers before it repeats Multiplier 75 = 16,807 and increment c=0 (pure multiplicative generator) 33

Cryptology (secret messages) 34 The Caesar cipher Julius Caesar used the following procedure to encrypt messages A function f to encrypt a letter is defined as: f(p) = (p+3) mod 26 Where p is a letter (0 is A, 1 is B, 25 is Z, etc.) Decryption: f-1(p) = (p-3) mod 26

This is called a substitution cipher You are substituting one letter with another 35 The Caesar cipher Encrypt go cavaliers Translate to numbers: g = 6, o = 14, etc. Full sequence: 6, 14, 2, 0, 21, 0, 11, 8, 4, 17, 18 Apply the cipher to each number: f(6) = 9, f(14) = 17, etc. Full sequence: 9, 17, 5, 3, 24, 3, 14, 11, 7, 20, 21 Convert the numbers back to letters 9 = j, 17 = r, etc. Full sequence: jr wfdydolhuv

Decrypt jr wfdydolhuv Translate to numbers: j = 9, r = 17, etc. Full sequence: 9, 17, 5, 3, 24, 3, 14, 11, 7, 20, 21 Apply the cipher to each number: f-1(9) = 6, f-1(17) = 14, etc. Full sequence: 6, 14, 2, 0, 21, 0, 11, 8, 4, 17, 18 Convert the numbers back to letters 6 = g, 14 = 0, etc. Full sequence: go cavaliers 36 Rot13 encoding

A Caesar cipher, but translates letters by 13 instead of 3 Then, apply the same function to decrypt it, as 13+13=26 Rot13 stands for rotate by 13 Example: >echo Hello World | rot13 Uryyb Jbeyq > echo Uryyb Jbeyq | rot13 Hello World 37 Primes and Greatest Common Divisor

Prime numbers A positive integer p is prime if the only positive factors of p are 1 and p If there are other factors, it is composite Note that 1 is not prime! Its not composite either its in its own class An integer n is composite if and only if there exists an integer a such that a | n and 1 < a < n 39 Fundamental theorem of arithmetic Fundamental Theorem of Arithmetic:

Every positive integer greater than 1 can be uniquely written as a prime or as the product of two or more primes where the prime factors are written in order of non-decreasing size Examples 100 = 2 * 2 * 5 * 5 182 = 2 * 7 * 13 29820 = 2 * 2 * 3 * 5 * 7 * 71 In a fundamental sense, primes are the building blocks of the natural numbers. Fundamental theorem of arithmetic: Strong Induction [from before] Show that if n is an integer greater than 1, then n can be written as the

product of primes. 1 - Hypothesis P(n) - n can be written as the product of primes. 2 Base case P(2) 2 can be written a 2 (the product of itself) 3 Inductive Hypothesis - P(j) is true for 2 j k, j integer. 4 Inductive step? Whats missing? Uniqueness proof, soon a) k+1 is prime in this case its the product of itself; b) k+1 is a composite 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 Composite factors Theorem: If n is a composite integer, then n has a prime divisor less than or equal to the square root of n Proof Since n is composite, it has a factor a such that 1 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 composite

If the latter, then it has a prime factor (by the FTA) In either case, n has a prime factor less than n QED Showing a number is prime E.g., show that 113 is prime. How? Solution The only prime factors less than 113 = 10.63 are 2, 3, 5, and 7 None of these divide 113 evenly

Thus, by the fundamental theorem of arithmetic, 113 must be prime 43 Showing a number is composite Show that 899 is composite. Solution Divide 899 by successively larger primes, starting with 2 We find that 29 and 31 divide 899 44 On a linux system or in cygwin, enter factor 899 > factor 899

899: 29 31 >factor 89999999999999999 89999999999999999: 7 7 13 6122449 23076923 Some random numbers factored (using factor) 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 1031411 9348492404203484: 2 2 7 23 14516292553111 928439237492742742: 2 13 89 10453 12821 2993831 9284392329378472: 2 2 2 31321 37053384029 9284392329378472323: 3 3 3 307 1120085936708707 Hmm. Apparent pattern of a several small prime factors ending with one or two very large primes. Real? Still many mysteries in prime number patterns Open questions about exact distribution of primes closely related to the main open problem in math: the Riemann hypothesis concerning distr. of zeros of

the Riemann zeta-function. Theorem: There are infinitely many primes. See our earlier proof by contradiction. 47 Mersenne numbers Mersenne number: any number of the form 2n-1 Mersenne prime: any prime of the form 2p-1, where p is also a prime Example: 25-1 = 31 is a Mersenne prime But 211-1 = 2047 is not a prime (23*89)

If M is a Mersenne prime, then M(M+1)/2 is a perfect number A perfect number equals the sum of its divisors Example: 23-1 = 7 is a Mersenne prime, thus 7*8/2 = 28 is a perfect number 28 = 1+2+4+7+14 Example: 25-1 = 31 is a Merenne prime, thus 31*32/2 = 496 is a perfect number 496 = 2*2*2*2*31 1+2+4+8+16+31+62+124+248 = 496 The largest primes found are Mersenne primes. Since, 2p-1 grows fast, and there is an extremely efficient test Lucas-Lehmer test for determining if a Mersenne prime is prime

Lucas-Lehmer test 50 Heres something to work on 51 9,808,358 digits thats close! 52 Also, what special patterns are there (if any) in the digits of prime numbers?

53 The prime number theorem The ratio of the number of primes not exceeding x and x/ln(x) approaches 1 as x grows without bound Rephrased: the number of prime numbers less than x is approximately x/ln(x) Rephrased: the chance of an number x being a prime number is (roughly) 1 / ln(x) (density: there are n numbers up to n with roughly n/ln(n) being prime. So, frequency of primes among n numbers is around 1/ln(n).) so, less frequent for higher x Consider 200 digit prime numbers ln (10200) 460 The chance of a 200 digit number being prime is 1/460

If we only choose odd numbers, the chance is 2/460 = 1/230 So, actually x /(ln x 1) is better estimate of number of primes . Greatest common divisor The greatest common divisor of two integers a and b is the largest integer d such that d | a and d | b Denoted by gcd(a,b) Examples gcd (24, 36) = 12 gcd (17, 22) = 1 gcd (100, 17) = 1 Relative primes

Two numbers are relatively prime if they dont have any common factors (other than 1) Rephrased: a and b are relatively prime if gcd (a,b) = 1 gcd (25, 16) = 1, so 25 and 16 are relatively prime 59 Pairwise relative prime A set of integers a1, a2, an are pairwise relatively prime if, for all pairs of numbers, they are relatively prime Formally: The integers a1, a2, an are pairwise relatively

prime if gcd(ai, aj) = 1 whenever 1 i < j n. Example: are 10, 17, and 21 pairwise relatively prime? gcd(10,17) = 1, gcd (17, 21) = 1, and gcd (21, 10) = 1 Thus, they are pairwise relatively prime Example: are 10, 19, and 24 pairwise relatively prime? Since gcd(10,24) 1, they are not 60 More on gcds Given two numbers a and b, rewrite them as: a p1a1 p2a2 ... pnan , b p1b1 p2b2 ... pnbn Example: gcd (120, 500) 120 = 23*3*5 = 23*31*51

500 = 22*53 = 22*30*53 Then compute the gcd by the following formula: gcd(a, b) p1min(a1 ,b1 ) p2min(a2 ,b2 ) ... pnmin(an ,bn ) Example: gcd(120,500) = 2min(3,2) 3min(1,0) 5min(1,3) = 22 30 51 = 20 Least common multiple The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b. Denoted by lcm (a, b) lcm(a, b) p1max(a1 ,b1 ) p2max(a2 ,b2 ) ... pnmax(an ,bn )

Example: lcm(10, 25) = 50 What is lcm (95256, 432)? 95256 = 233572, 432=2433 lcm (233572, 2433) = 2max(3,4)3max(5,3)7max(2,0) = 24 35 72 = 190512 lcm and gcd theorem Theorem: Let a and b be positive integers. Then a*b = gcd(a,b) * lcm (a, b) Example: gcd (10,25) = 5, lcm (10,25) = 50 So, 10*25 = 5*50 Example: gcd (95256, 432) = 216, lcm (95256, 432) = 190512 So, 95256*432 = 216*190512

Euclids Algorithm for GCD Finding GCDs by comparing prime factorizations can be difficult when the prime factors are not known! And, no fast alg. for factoring is known. (except ) On quantum computer! Euclid discovered: For all ints. a, b, gcd(a, b) = gcd((a mod b), b). Sort a,b so that a>b, and then (given b>1) (a mod b) < a, so problem is simplified. Euclid of Alexandria 325-265 B.C.

Theorem: Let a =bq+r, where a,b,q,and r are integeres. Then gcd(a,b) = gcd(b,r) Suppose a and b are the natural numbers whose gcd has to be determined. And suppose the remainder of the division of a by b is r. Therefore a = qb + r where q is the quotient of the division. Any common divisor of a and b is also a divisor of r. To see why this is true, consider that r can be written as r = a qb. Now, if there is a common divisor d of a and b such that a = sd and b = td, then r = (sqt)d. Since all these numbers, including sqt, are whole numbers, it can be seen that r is divisible by d.

The above analysis is true for any divisor d; thus, the greatest common divisor of a and b is also the greatest common divisor of b and r. Euclidean Algorithm Lemma: Let a = bq + r, where a, b, q, and r are integers. Then gcd(a, b) = gcd(b, r) procedure procedure (a,b:positive integers) x := a y := b while y 0 Arises when r = 0. So, y begin divides x. But x:=y and r := x mod y

y:=0, so return x. Also x := y y := r note that gcd(a,0) = a. end { gcd(a, b) is x } What about the y=0 case? 66 Do we need a >= b? hmm Euclids Algorithm Example gcd(372,164) = gcd(164, 372 mod 164). 2000+=yr3721642

alg. makes 372 mod 164 = 372164372/164 = 372328 = 44. E-commerce gcd(164,44) = gcd(44, 164 mod 44). possible! 164 mod 44 = 16444164/44 = 164443 = 164132 = 32. gcd(44,32) = gcd(32, 44 mod 32) = gcd(32,12) = gcd(12, 32 mod 12) = gcd(12,8) = gcd(8, 12 mod 8) = gcd(8,4) = gcd(4, 8 mod 4) = gcd(4,0) = 4. So, we repeatedly swap the numbers. Largest first. mod reduces

them quickly! Complexity? Guess O(log b) divisions. Linear in #digits of b! Compare to direct search for divisor. (Lame`s thm. Section 4.3) Integers and Algorithms 68 Base-b number systems

Ordinarily, we write base-10 representations of numbers, using digits 0-9. Of course, any base b>1 will work. For any positive integers n,b, there is a unique sequence Hmm. What about base 1? ak ak-1 a1a0 of digits ai

i Complexity of algs.: i always think about, what i 0 is the length of the input. Some problems still hard even with unary input 69 n a b Base Systems

Theorem: Base b expansion of a number 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 = ak bk + ak-1 bk-1 + + a1 b + a0 Where k is a non-negative integer, a0, a1, , ak are nonnegative integers less than b, and ak 0 (Proof by induction) 70 Bases of Particular Interest Used only because we have 10 fingers Base b=10 (decimal):

10 digits: 0,1,2,3,4,5,6,7,8,9. Used internally in all Base b=2 (binary): modern 2 digits: 0,1. (Bits=binary digits.) computers Base b=8 (octal): Octal digits correspond to 8 digits: 0,1,2,3,4,5,6,7. groups of 3 bits Base b=16 (hexadecimal): 16 digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F Hex digits give groups of 4 bits

Converting to Base b (An algorithm, informally stated.) To convert any integer n to any base b>1: To find the value of the rightmost (lowest-order) digit, simply compute n mod b. Now, replace n with the quotient n/b. Repeat above two steps to find subsequent digits, until n is gone (=0). Constructing Base b Expansions procedure base b expansion (n:positive integer) q := n k := 0 while (q 0)

begin ak := q mod b q := q / b k := k + 1 end {the base b expansion of n is (ak-1 ak-2 . . . a1 a0 )b } 74 N=25 in binary? N 25 a0 25 mod 2 1 N 25 / 2 12 a1 12 mod 2 0 N 12 / 2 6

a2 6 mod 2 0 N 6 / 2 3 a 3 3 mod 2 1 N 3 / 2 1 a4 1 mod 2 1 So, we have 25 in binary is 11001. N= 23670 in hexadecimal? 23670 mod 16 = 6; N= 23670/16 = 1479 mod 16 = 7 N= 1479/16 = 92 mod 16 = 12 N= 92/16 = 5 mod 16 = 5

6 76 C76 5C76 76 Addition of Integers in Binary Notation As you have known since grade 1 or before Correctness proof?

procedure add (a,b:positive integers) c := 0 for j := 0 to n - 1 Complexity? (#additions) begin d := (aj + bj + c) / 2 O(n), sj := aj + bj + c - 2d where n is number of bits! c := d (log of the size of the end number)

sj := c {the binary expansion of the sum is (sn sn-1 . . . s0 )2 } {the binary expansions of a and b are: an-1,an-2, a1,a0 and bn-1,bn-2, b1,b0} Multiplying Integers procedure multiply (a,b:positive integers) c := 0 Complexity? (additions and shifts) for j := 0 to n - 1 begin O(n2)

if bj then cj := a shifted j places else cj := 0 end p := 0 for j := 0 to n 1 p := p + cj {p is the value of ab } {the binary expansions of a and b are: an-1,an-2, a1,a0 and 78 bn-1,bn-2, b1,b0} Note: There are more efficient algorithms for multiplication! Modular Exponentiation

Problem: Given large integers b (base), n (exponent), and m (modulus), efficiently compute bn mod m. Note that bn itself may be completely infeasible to compute and store directly. E.g. if n is a 1,000-bit number, then bn itself will have far more digits than there are atoms in the universe! Yet, this is a type of calculation that is commonly required in modern cryptographic algorithms! Hmm. Modular Exponentiation: Using Binary Expansion of exponent n The binary expansion of n

Note that: n b b (b 2 k 1 ak 1 ) a k 1 2 k 1 a k 2 2 k 2 a0 2 0 (b

2 k 2 ak 2 ) 2 0 a0 (b ) We can compute b to various powers of 2 by repeated squaring. Then multiply them into the partial product, or not, depending on whether the corresponding ai bit is 1. Problem solved?

Crucially, we can do the mod m operations as we go along, because of the various identity laws of modular arithmetic. All the numbers stay small. 11 3 Example: So, Note: 11 = (1011)2 311 383231 32 9; 34 9 2 81;38 812 6561

By successively squaring: Therefore: 11 8 2 1 3 3 3 3 65619 3 177,147 The algorithm successively computes: 2 4

## Recently Viewed Presentations

• The Toulmin Method of Argument. Toulmin's basic understanding of argument includes several elements: A claim. Groundsthat state the reason for the claim. Qualifications that identify possible exceptions to the claim. Based on evidence of some sort. A warrant that explains...
• The Various Focuses of Needs Analysis. Hutchinson and Waters (1987) divide needs into target needs(i.e. what the learner needs to do in the target situation) and learning needs(i.e. what the learner needs to do in order to learn).The analysis of...
• These are typically of high interest to your entire audience of readers (town news such as a new park or community center). Parts of a Newspaper What is a newspaper?A newspaper is a publication that is printed and distributed, usually...
• Depletion Code System Yunlin Xu T.K. Kim T.J. Downar School of Nuclear Engineering Purdue University March 28, 2001 Content Motivation Motivation Why do we need depletion code system? Basic tool for Nuclear Reactor fuel cycle analysis NERI/DOE projects at Purdue...
• Bulletin Board General announcements can now be sent to coaches, schools, districts, and administrators. The bulletin board can be accessed from each level's dashboard. When active messages are available, the envelope icon will change from empty to full.
• Soldier for Life Campaign . Mission. Soldier for Life . connects. Army, governmental, and community efforts to build relationships that facilitate successful reintegration of our Soldiers, Retired Soldiers, Veterans, and their Families in order to keep them Army Strong and...
• Dino Diorama--The students use a shoebox and supplies such as construction paper, markers, and other things to re-create their dinosaur's habitat. Dino Bingo—create cards using the dinosaurs that the children made fact files on. Call out facts about each dinosaur...
• European Periods of Floral Design Renaissance Period Baroque Period Flemish Period French Styles English Georgian Period Victorian Period Arrangements were large, tall, pyramidal and symmetrically balanced Arrangement was twice the height of container Flowers were loose, airy and uncrowded Symmetrical...