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.
Example 11.20 Small primes etc
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:-)
[ ../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
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: