Foundations in Programming
Foundations in Programming CS 160
Popular in Course
Popular in ComputerScienence
This 6 page Class Notes was uploaded by Betty Kertzmann on Monday September 21, 2015. The Class Notes belongs to CS 160 at Colorado State University taught by John Applin in Fall. Since its upload, it has received 9 views. For similar materials see /class/210166/cs-160-colorado-state-university in ComputerScienence at Colorado State University.
Reviews for Foundations in Programming
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/21/15
10608 Integers Primes and some Cryptography Rosen 34 35 37 I Integers I Of course you already know what the integers are and what division is I But There are some speci c notation terminology and theorems associated with these oonoepis which you may not know I These form the basics of number then u Vital in many important algorithms hash functions wyptography digital signatures I Integer Division I If a and b are integers with a 1quot 0 we say that a divides b ifthere Is an integer c such that b ac a When a divides b we say that 5 l5 afactor of b and l5 a multiple of a u The notation a b denotes that a divides b Examples a Does 5 10 a Does 5 15 a Does 2 5 I Division Theo rem Theorem Let a b and c be integers Then i ifabandacthenabc ll ifa b then a be for all integers c Ii ifabandbcthenac I Division Theorem I Corollary Ifa b and c be integers such thatalbandalcthenambnc Whenever m and n are integers I Integer division I The Division Algorithm Leta be an integer and d a positive integer Then there are unique integers q and r with 0 s rlt d such that a dq r a dis called the divisor u qis called the quotient q a div d u ris called the remainder r a mod d a d in Java u Examples 711373p2 10608 l Integer division Examples Given a 13 and d 4 what are the values of q and r Since 134 3 14 we know that u q13div43and u r 13mod4 1 Given a 96 and d 15 what are the values of qand r Since 9715 6 715 we know that u q97div156and u r97mod15 7 I Modular Arithemetic If a and b are integers and m is a positive integer then a is congruent to b modulo m if m divides ab u Notation a E 1 mod m Example Is 17 congruent to 5 modulo 6 a As 6 divides 175 they are congruent Example Is 24 congruent to 14 modulo 6 a As 6 does not divide 2414 10 they are not congruent Modular Arithmetic cont Theorem Let a and b be integers and let m be a positive integer Then a E b mod m if and only if a mod m b mod m a m b m inJavanota39 Example Is 17 congruent to 5 modulo 6 u Rephrased does 17 E 5 mod 6 n17mod65mod6 distinguish between b mod m and b mod m Exam le Is 24 congruent to 14 modulo 6 n Rephrased 24 E 14 mod 6 n 24mod6 14mod6 I Modular Arithmetic cont 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 u 17 5 26 u 5 17 26 Applications of modular arithmetic Hash functions Hash functions provides fast access to data of the form key value Common hash function Keys Indexes Keyvalue pairs k mOd m records D X I B72 B73 John Smith 15551234 gtgti image from httpenwikipediaorgwikiImageHASHTBOBsvg l Pseudorandom Numbers A linear congruential methods uses the following rule xn1 a xn 0 mod m m modulus a multiplier c increment xo seed Example m9 a7 c4 x03 generates 3786120453786120453 10608 The Ceasar Cipher Ceasar s cipher shift each letter three letters forward To express mathematically replace letters with numbers 0 25 and encrypt the number using a function fdefined by fp p3 mod 26 BEE 1 Where p corresponds to a letter O is A 1 is B 25 is Z etc Decryption f1p p3 mod 26 This is called a substitution cipher issue with a substitution cipher image from http enwikipediaorgwikilmage Caesar3svg Prime Numbers Prime Numbers Prime integer greater than 1 that is divisible only by 1 and itself Examples 2 3 5 7 11 13 17 19 23 29 There are infinitely many primes Composite numbers n A nonprime positive integer greater than 1 is called composite An integer n is composite if and only if there exists an integer a such that a n and 1 lt a lt n Examples 9 is composite because it is divisible by 3 The Fundamental Thm of Arithmetic I Theorem Every positive integer greater than 1 can be written uniguely as a prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size Examples 1 100 2255 2252 182 2 7 13 298202235771 641 641 999 33 37 1024 210 UUUUD Showing a number is prime Theorem If n is a composite integer then n has a prime divisor less than or equal to n I As a result an integer is prime if it is not divisible by any prime less than or equal to its square root Example show that 101 is prime The only primes not exceeding 101 are 235 and 7 101 is not divisible by 235 or 7 Therefore 101 is prime 10608 EXarnple I Is 899 prime or composite I Solution u Divide 899 by successively larger primes lt 899 starting with 2 n We nd that 29 and 31 divide 899 I FUN FACT On a unix system enter Tactor 899 gt Factor 599 899 29 Greatest Common Divisors and Least Common Multiples Greatest Common Divisor GCD I The greatest common divisor of two integers a and b is the largest integer d such that d a and d b u Denoted by gcdab I Examples a god 24 36 12 u gcd17221 u gcd100171 Find all positive common divisors 0 both integers hen take the largest Easy way to nd gcd Relatively Prime I Two numbers are relatively prime if they don t have any common ctors otherthan 1 n Rephrased a and b are relatively prime if god ab 1 I gcd 25 39 1 so 25 and 39 are relatively prime Least Common Multiple I The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b u Denoted by lcm a b I Example lcm10 25 50 I What is lcm 95256 432 a 95256 233572 4322433 D cm 53233572 2433 2max343max537max2U 243572 190 12 I And in general 1cmab prm ibip m rbxmpm n I Theorem Let a and b be positive integers Then ab gcdab Icmab I Example a PC 1025 5 cm 1025 50 102 5 0 10608 An Application of Number Theory The RSA Cryptosystem Ceasar Cipher revisited I You encrypt using c pkmod 26 k is the encryption key and decrypt by shifting by k pc kmod 26 Le k is the decryption key I If you know the encryption key you know the decryption key I Problem Need a safe way to send the encryption key i Public key cryptography I Eliminate the need for securely sending the encryption key use a public key a I generate public and private keys in I publish my public key a You encode a message into numbers and encryp them a ny I who know the private key can decrypt i Public key cryptography I We use such technology on a daily basis Whenever we visit a secure website http5 address I RSA encryption Rivest Shamir Adleman uses ideas from numbertheory to make all that possible RSA encryption The encryption process C Me mod n I M integer representing the plaintext I C the encrypted message I n a product oftwo large prime numbers pq I e a numberwhich is relatively prime to p1q1 I Public key e n i RSA decryption How to decrypt a message M Cd mod n I n pq where pq are prime I d can be computed knowing epq I Private key d n I lfyou could factor n you could nd out the private key I But it turns out that it s practically impossible to factor very large num ers 10608 i Eernple SSH When you connect ssh checks if server key is the game as last time and uses the key to encryp a a Representations of Integers Here s how a knownhosts file looks like 5319csculustateedu129E246175 Siberia Rosen 36 v4ch 1VKU7EWZDhZLu VlGSSEthNJzzGWYEj kgfjmuJDPHcHleFZ Representing Integers 7 Binary Decimal etc i Representations ofIntegers I Until now we talked about this informally heorem Let bbe a positive integer greaterthan 1 hen if quotis a positive integer it can be expressed I Need to know about it since computers work umquely m the form in binary n aka akbk1 ab1 a where k is a nonnegative integer am 3 ak ar nonnegative Integers less than b and ah a 0 Example base a 496 10 Automationwa