>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 19 [Text Version]
Session: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] (19) [20]
Thu Jun 8 13:03:05 PDT 2006

# 19

## Schedule

 Date Meet'g Study(2 pts) Bring(5 pts) Topic(5 pts) Notes Mon Jun 5 18 Chapter 11 sections 11.4 Ex Randomization RP ZPP Wed Jun 7 19 Chapter 11 sections 11.5, 11.6 Ex Primality Mon Jun 12 20 Chapters 8, 9, 10, 11 Ex Review Fri Jun 16 Final Chapters 1, 2, 8, 9, 10, 11 - Comprehensive (200 pts)

## 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:

1. primes::={ p:2..*. for no n,m:2..(p-1) ( p =n*m ) }.
2. composite::= 2..* ~ primes.
3. Composite is the complement of primes (except for 1).
4. 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 [ ../samples/primes.html ] after a question form someone who had read my pages.

### 11.5.1 The Importance of Testing Primality 499

#### Requirements

1. Find large primes fast.
2. Prove factorization is slow.

### 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 [ 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

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.

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:-)

### 11.5.2 Introduction to Modular Arithmetic 501

[ ../maths/math_42_Numbers.html ] (my notes on number theory).

#### Errata on page 502 in first two lines

"We can divide any number x by a nonzero y by"

### Bonus Exercise (20 points)

Complete the following template class for arithmetic modulo integer p:
` 	template<int p>Mod{`
` 	private: int n;`
` 	public: Mod(int i){ n = i%n ; }`
`     int value ( )const { return n; }`
`     Mod<p> operator + ( Mod<p> j) { return Mod<p>(n+i.value()); }`
` 	   ...`
` 	}//Mod`

### 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:

5. x^(2n) = (x^2)^n, and
6. x^(2n+1) = x * (x^2)^n.

So for example:

7. 2^100 = (2^2)^50 = 4^50,
8. 4^50 = (4^2)^25 = 16^25,
9. 16^25 = 16* (16^2)^12 = 16 * 256^12,
10. 16 * 256^12 = 16 * (256^2)^6 = 16* 65536^6,
11. 16* 65536^6 = 16 * (65536^2)^3 = 16 * 4294967296^3,
12. ...

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:

13. 2^99 mod 100 = 2 * (2^2)^49 = 2 * 4^49.
14. 4^49 = 4*(4^2)^24 = 4* 16^24,
15. 16^24 = (16^2)^12 = 56^12 = (56^2)^6 = 36^6 = (36^2)^3 = 96^3,
16. 96^3 = 96 * 96^2 = 96 * 16,

So

17. 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++: [ ../examples/fast.pow.cc ]

18. Stephen Collins wrote this in PHP::Modulo Exponentiation. It calculates exponentiation in a matrix 10 by 10 for any give mod p. [ modulo ]

### 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 [ ../maths/math_42_Numbers.html#Carmichael_numbers ] [ CarmichaelNumber.html ]

### 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...).

#### 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?

#### 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: [ PrattCertificate.html ] [ ppp.html ] (This last has a very clean expression of doubling power algorithm).

### 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?

### 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.

Best avoided.

## 11.7 References for Chapter 11 510

. . . . . . . . . ( end of section 19) <<Contents | End>>

# Next -- Review

I will give you a handout to read and review as your assigned exercise.

For more 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.

# Standard Definitions

1. FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
2. ND::="Non-deterministic", a machine that can try out many possibilities and always guesses the right choice. Note: For a given problem a ND solution is simpler and easier to understand than a deterministic one. We study ND machines to discover how to use them as high-level designs for more complicated deterministic machines. Plus it's fun.
3. PDA::="Push down Automata", a machine with a finite control and a single stack for remembering intermediate data. Kind of like half a TM.
4. RJB::=The author of this document, [ ../index.html ]
5. |-RJB="Richard J Botting, Comp Sci Dept, CSUSB".
6. Schedule::= See http://www.csci.csusb.edu/dick/cs546/schedule.html.
7. Search::= See http://www.csci.csusb.edu/dick/cs546/lookup.php.
8. Syllabus::= See http://www.csci.csusb.edu/dick/cs546/syllabus.html, and also see [ syllabus.html ] (my generic syllabus).
9. TBA::="To Be Announced".
10. TM::="Turing Machine".
11. NTM::="Nondeterministic Turing Machine".
12. nondeterministic::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
13. DTM::="Deterministic Turing Machine".
14. runtime::=run_time,
15. run_time::="The number of steps a TM takes before it halts when start on a given input".
16. complexity::="The largest run_time for any word with a given length" , usually expressed as an assymptotic (Big-O) formula.
17. P::@problem=class of problems that a DTM can compute in polynomial_time.
18. NP::@problem=class of problems that a NTM can compute in polynomial_time.
19. polynomial_time::=An algorithm/TM is said to halt in polynomial time if the number of steps given n items of data is less than O(n^c) for some constant c.

# From Logic

20. LOGIC::= See http://www.csci.csusb.edu/dick/maths/logic_25_Proofs.html

21. (LOGIC)|- (ei): Existential instantiation -- if P is true of something then we can substitute a new variable for it.
22. (LOGIC)|- (eg): existential generalization -- if P is true of this thing then it is true of something!
23. (LOGIC)|- (given): a proposition that is assumed as part of a Let...End Let argument. Typically if A and B and C then D starts with assuming A,B, and C are given. They are called the hypotheses.
24. (LOGIC)|- (goal): a proposition that we wish to prove. Typically the part after the then in an if...then... result. This is called the conclusion.
25. (LOGIC)|- (def): By definition of a term defined above.
26. (LOGIC)|- (algebra): Either by using well known algebraic results, or by use a series of algebraic steps.
27. (LOGIC)|- (RAA): Reduce to absurdity. The end of a Let/Po/Case/Net that establishes the negation of the last set of assumptions/hypotheses.