.Open 19 . Schedule .Table Date .Item Meet'g .Item $Study(2 pts) .Item Bring(5 pts) .Item $Topic(5 pts) .Item Notes .Row Mon Jun 5 .Item 18 .Item Chapter 11 sections 11.4 .Item $Ex .Item Randomization RP ZPP .Row Wed Jun 7 .Item 19 .Item Chapter 11 sections 11.5, 11.6 .Item $Ex .Item Primality .Row Mon Jun 12 .Item 20 .Item Chapters 8, 9, 10, 11 .Item $Ex .Item Review .Row Fri Jun 16 .Item Final .Item Chapters 1, 2, 8, 9, 10, 11 .Item - .Item Comprehensive (200 pts) .Close.Table .Open 11.5 The Complexity of Primality Testing 499 Several proofs in this section rely on deep number theory and so have been left incomplete. Some quick definitions: primes::={ p:2..*. for no n,m:2..(p-1) ( p =n*m ) }. composite::= 2..* ~ primes. Composite is the complement of primes (except for 1). We leave 1 in limbo as neither prime nor composite, I guess. . How do we factor the composite number? Class discussion... I've posted some simple results of Prime Numbers in .See ../samples/primes.html after a question form someone who had read my pages. .Open 11.5.1 The Importance of Testing Primality 499 . Example 11.20 Small primes etc . Public Key Cryptography . Public Key Signatures . Requirements Find large primes fast. Prove factorization is slow. .Close . Ch 11.5.1 pp 499 -- Public-Key Cryptography I've had a few classes talk about RSA Encryption and how hard(or impossible) it is to crack. How long would it really take to crack a 128-bit encryption key using "modern" equipment? months...years...lots of years? How about 256-bit? I don't follow this topic.... but this .See http://www.math.okstate.edu/~wrightd/crypt/crypt-intro/node22.html is a link into a talk on cracking the RSA-129 challenge with 1600 PCs and taking 8 months in the early 1990's. On Google Groups I found that in 1998 .Box RSA Data Security Inc. said last night that a global team of programmers called distributed.net broke a 56-bit Data Encryption Standard key in 39 days, about one-third of the time it took a similar team to break a DES key last year. .Close.Box They used brute force methods which are very sensitive to the length of the key: add a bit, and double the search. Of course the whole P=?=NP thing is about whether brute force search can be improved on. I figure that there a secret places in several countries that are not publishing the speed with which they can crack codes:-) .Open 11.5.2 Introduction to Modular Arithmetic 501 .See ../maths/math_42_Numbers.html (my notes on number theory). . Example 11.21 p=13 . DO Exercise 11.5.1 (below) now . Example 11.22 Tables . Errata on page 502 in first two lines "We can divide any number x by a nonzero y by" . Example 11.23 .Close . Bonus Exercise (20 points) Complete the following template class for arithmetic modulo integer p: .As_is templateMod{ .As_is private: int n; .As_is public: Mod(int i){ n = i%n ; } .As_is int value ( )const { return n; } .As_is Mod

operator + ( Mod

j) { return Mod

(n+i.value()); } .As_is ... .As_is }//Mod . 11.5.3 The Complexity of Modular-Arithmetic Computations 503 . Ch 14, ch11 pp 503 -- Complexity Could you explain how the book derived that the complexity of Modular Arithmetic comes to O(n^3)? Step 2 is where I get lost. . Ch 11.5.3 pp 503 -- Recursive Doubling Can you explain the \"recursive doubling\" trick that let us compute x^p-1 The trick is a classic divide and conquer algorithm: x^(2n) = (x^2)^n, and x^(2n+1) = x * (x^2)^n. So for example: 2^100 = (2^2)^50 = 4^50, 4^50 = (4^2)^25 = 16^25, 16^25 = 16* (16^2)^12 = 16 * 256^12, 16 * 256^12 = 16 * (256^2)^6 = 16* 65536^6, 16* 65536^6 = 16 * (65536^2)^3 = 16 * 4294967296^3, ... If we only need the answer modulo some `p` then we do all the calculations in modulo `p` arithmetic and so avoid the exponential explosion. For example: with all calculation mod 100: 2^99 mod 100 = 2 * (2^2)^49 = 2 * 4^49. 4^49 = 4*(4^2)^24 = 4* 16^24, 16^24 = (16^2)^12 = 56^12 = (56^2)^6 = 36^6 = (36^2)^3 = 96^3, 96^3 = 96 * 96^2 = 96 * 16, So 2^99 mod 100 = 2 * 4 * 96 * 16 mod 100 = 88. (Which shows that the last two0 decimal digits of 2^99 are 88) Here is an old implementation in C++: .See ../examples/fast.pow.cc Stephen Collins wrote this in PHP :: Modulo Exponentiation. It calculates exponentiation in a matrix 10 by 10 for any give mod p. .See http://ihsproductions.net/modulo .Open 11.5.4 Random-Polynomial Primality Testing 504 . Ch 11.5.4 pp 504 -- Random-Polynomial Primality Testing Erratum? "If p is prime, then x^(p-1) = 1" Yes... they forgot to add "modulo p"! . Theorem 11.24 Composite in RP The proof is incomplete and informal. Also see .See ../maths/math_42_Numbers.html#Carmichael_numbers .See http://mathworld.wolfram.com/CarmichaelNumber.html .Close .Open 11.5.5 Nondeterministic Primality Tests 505 . Ch 11.5.5 pp 505 -- The Complexity of Primality Testing The section talks about nondeterministic primality tests. Is there a deterministic primailty test? Yes.... but we don't know how to do it as quickly with some good guesses. (And it may not be possible to speed up the deterministic version...). . Theorem 11.25 composite in NP . Ch 11.5.5 pp 505 -- Nondeterministic Primality Tests Please give a example of Theorem 11.25. A set of composite numbers is in NP. To be more precise: the theorem proves that the `set` of all composite numbers is in NP. In other words, given a number we can find out if it is composite in polynomial time by making the `right` guess. . Ch 11.5 pp 505 -- composite numbers Can you go over why composite numbers are NP? . Ch 11.5 pp 505 -- Nondeterministic Primality Could you go over Theorem 11.25 . Ch 11.5.5 pp 505-506 -- Nondeterministic Primality Test Can you elaborate on Theorem 11.25? . Theorem 11.26 prime in NP . Ch 11.5 pp 506 -- Primes in NP Could you please go over the proof for Theorem 11.26? Arrrrrrgh! Are you sure... it is not on the final. The citation takes to the work published by Pratt in 1975. On the web there are resources: .See http://mathworld.wolfram.com/PrattCertificate.html .See http://www.cs.rutgers.edu/~chvatal/notes/ppp/ppp.html (This last has a very clean expression of doubling power algorithm). .Close . Ch 11 pp 508/472 -- NP = co-NP Theorem 11.2 (which is in a different section) is referenced at the end of this section to show that if we can demonstrate that primes are NP-complete (or composites are NP-complete), then NP = co-NP. I\'m not sure why the proof works. Could you go over this proof in class? .Open 11.5.6 Exercises for Section 11.5 508 . Exercise 11.5.1 Modulo 13 Arithmetic Looks easy... OK for CSCI546 only. . Exercise 11.5.2 x^560 Hmmmmm.... Acceptable for full credit by CSCI646. . Exercise 11.5.3 Quadratic Residues Best avoided. .Close .Close . 11.6 Summary of Chapter 11 508 . 11.7 References for Chapter 11 510 .Close 19 . Next -- Review I will give you a handout to read and review as your assigned exercise. For more see .See ./20.html . Notes (Ex): Do as many of the relevant exercises as you have time for. You may work in a team of up to 4 students and hand in one joint solution. Bring to class one written solution to an exercise. This must not be a solution to an exercise marked with an asterisk(*) to earn full credit. One of the authors will be invited to present the solution to the class -- failure will loose points. Students taking CS646 must hand in the solution to an exercise marked with an exclamation mark(!) to earn full credit. Or in preparation for this class Exercise 11.5.2. (Study): Read & think about the assigned items. Submit one question by selecting the submit button at the top of the web page. To earn complete credit you need to do this at least 90 minutes before the start of class. Hints. Read each section twice -- once the easy bits and then the tough bits. Use a scratch pad and pencil as you read. (Topic): To earn all the possible points you must: turn up on time, not leave early, present work when called upon, and take part in discussions.