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
Example 11.20 Small primes etc
Public Key Cryptography
Public Key Signatures
Requirements
- Find large primes fast.
- 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).
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
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
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:
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...).
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:
[ 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.
Exercise 11.5.3 Quadratic Residues
Best avoided.