cr.yp.to update
[email protected] 29 Aug 2005 19:33:01 -0000
| Newsgroups | gmane.comp.djb.announce |
|---|---|
| Message-ID | <[email protected]> |
2005-261.html | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++
2005-501.html | 28 +++++++++++++++++++
conferences.html | 37 +++++++++++++++++--------
snuffle/topleft9.c | 2 -
snuffle/topleft9.out | 7 ++++
5 files changed, 137 insertions(+), 12 deletions(-)
diff -ru .old-crypto/2005-261.html cr.yp.to/2005-261.html
--- .old-crypto/2005-261.html 2005-08-26 05:34:45.000000000 -0400
+++ cr.yp.to/2005-261.html 2005-08-29 05:09:01.000000000 -0400
@@ -162,5 +162,80 @@
S intersect (T union X) = (S intersect T) union (S intersect X).
Proof of the distributive law.
Picture of a Venn diagram.
+<p>
+<h2>28 August 2005</h2>
+Class material from Friday:
+View of set definitions as proof strategies.
+To prove that S is a subset of T:
+list elements of S
+and prove, for each element x of S,
+that x is an element of T.
+To prove that S is not a subset of T:
+find an element x of S that's not an element of T,
+and prove it!
+Example: strategy to prove that S intersect T is a subset of S.
+To prove that two sets S, T are equal:
+prove that S is a subset of T,
+and prove that T is a subset of S.
+To list the elements of S union T,
+list the elements of S,
+and list the elements of T.
+To prove that x is in S union T,
+prove that x is in S,
+or prove that x is in T.
+To prove that x is not in S union T,
+prove that x is not in S,
+and prove that x is not in T.
+Example: proof that S is a subset of S union T.
+How to list the elements of S intersect T.
+How to prove that x is in S intersect T.
+How to prove that x is not in S intersect T.
+Set difference:
+x is in S - T
+means that x is in S and x is not in T.
+Example: {3,1,4} - {2,7,1} = {3,4}.
+To prove that x is not in S - T,
+prove that x is not in S,
+or prove that x is in T.
+<p>
+Practice exam, due Friday 2 September:
+For each of the following five statements,
+use the definitions of union, intersection, etc.
+to prove the statement for all sets,
+or disprove the statement by writing down particular sets
+where the statement is not true.
+(1) (A union B) intersect C = A union (B intersect C).
+(2) If A is a subset of B and C is a subset of U-B
+then A intersect C = {}.
+(3) (A - B) union C = A - (B union C).
+(4) (A intersect B) intersect C = A intersect (B intersect C).
+(5) (A xor B) intersect C = A xor (B intersect C).
+Here S xor T means (S-T) union (T-S).
+<p>
+Note that a statement about sets A,B,C,...
+is implicitly a statement about _all_ sets A,B,C,...,
+unless it explicitly says something different.
+To prove the statement,
+you have to prove it for all possible choices of A,B,C,...;
+to disprove the statement,
+you have to disprove it for at least one choice of A,B,C,...
+<p>
+Sample question: ``Prove or disprove that, if A is a subset of B,
+and B is a subset of C, then A is a subset of C.''
+Overly short answer, not spelling out enough details:
+``Proof: Each element of A is an element of C.
+Therefore, A is a subset of C.''
+More detailed answer:
+``Proof: Each element of A is an element of C.
+Specifically,
+if x is an element of A,
+then x is an element of B, since A is a subset of B;
+so x is also an element of C, since B is a subset of C.
+Therefore, A is a subset of C.''
+<p>
+Sample question: ``Prove or disprove that (A union B) union B = A.''
+Adequately detailed answer: ``Disproof: Define A = {1} and B = {2}.
+Then A union B = {1,2},
+so (A union B) union B = {1,2} != {1} = A.''
</body>
</html>
diff -ru .old-crypto/2005-501.html cr.yp.to/2005-501.html
--- .old-crypto/2005-501.html 2005-08-26 05:39:05.000000000 -0400
+++ cr.yp.to/2005-501.html 2005-08-29 05:37:25.000000000 -0400
@@ -112,5 +112,33 @@
Machine finishes in n^(1+o(1)) seconds;
machine costs n^(1+o(1)) dollars.
Beginning of description of sorting machine #4: two-dimensional mesh.
+<h2>28 August 2005</h2>
+One good reference for Schimmler sort
+is Schimmler's 1987 article
+<a href="bib/1987/schimmler.html">Fast sorting on the instruction
+systolic array</a>.
+The second column-sorting step in
+Schimmler's algorithm uses a slightly more complicated
+algorithm than I explained in class,
+saving sqrt(n) parallel compare-exchange steps out of about 8 sqrt(n).
+<p>
+Class material from Friday:
+Odd-even transposition sort of n^(0.5) integers on a one-dimensional mesh.
+Example of odd-even transposition sort.
+Sorting machine #4: two-dimensional mesh using Schimmler sort.
+Example of Schimmler sort.
+Time analysis of Schimmler sort.
+Machine finishes in n^(0.5+o(1)) seconds;
+machine costs n^(1+o(1)) dollars.
+What's covered in a prerequisite course such as MCS/CS 401:
+<ul>
+<li>
+Some reductions of ``time'' for a few important computational problems,
+such as sorting and finding shortest paths.
+<li>
+Some algorithm design techniques,
+such as divide-and-conquer and dynamic programming.
+</ul>
+Research directions after the prerequisite course.
</body>
</html>
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/13.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/13.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/14.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/14.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/16.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/2.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/20.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/20.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/23.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/25
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/25.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/27.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/27.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/28.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/3.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/3.pdf
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/31.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/31.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/32.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/32.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/33.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/33.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/34.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/34.pdf
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/36.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/36.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/38.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/38.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/40.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/40.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/41.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/41.pdf
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/45.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/45.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/46.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/46.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/47.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/47.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/48.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/48.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/49.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/49.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/5.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/5.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/50.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/50.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/51.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/51.pdf
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/52.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/53.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/53.ppt
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/8.mov
New: conferences/2005-crypto/www.iacr.org/conferences/crypto2005/r/8.ppt
diff -ru .old-crypto/conferences.html cr.yp.to/conferences.html
--- .old-crypto/conferences.html 2005-08-08 17:52:33.000000000 -0400
+++ cr.yp.to/conferences.html 2005-08-28 23:13:59.000000000 -0400
@@ -464,7 +464,7 @@
<a href="conferences/2005-schoof/www.math.uoc.gr/AXAK/index.html">mirror</a>.
Travel funded by conference organizers (Anogia).
<p>
-2005.08.14-2005.08.18, plan to attend:
+2005.08.14-2005.08.18, attended:
CRYPTO 2005.
<a href="http://www.iacr.org/conferences/crypto2005/">http://www.iacr.org/conferences/crypto2005</a>;
<a href="conferences/2005-crypto/www.iacr.org/conferences/crypto2005/index.html">mirror</a>.
@@ -474,25 +474,40 @@
Elliptic Curve Cryptography (ECC) 2005.
Denmark Technical University, Copenhagen.
<p>
-2005.11:
+2005.10.15-2005.10.15:
+Security workshop at UIC.
+<p>
+2005.11.05-2005.11.11:
Banff.
<p>
-2006.03:
+2006.03.11-2006.03.15:
Arizona Winter School.
<p>
-2006.04:
-TBA.
+2006.04.03-2006.04.04:
+SHARCS 2006.
+<p>
+2006.04.08-2006.04.09:
+Notre Dame.
+<p>
+2006.04.24-2006.04.26:
+PKC 2006.
+<p>
+2006.05.24-2006.05.26:
+PQCrypto 2006.
+<p>
+2006.05.28-2006.06.01:
+Eurocrypt 2006.
<p>
-2006.04:
-TBA.
+2006.06.19-2006.07.07:
+Wyoming.
<p>
-2006.05:
-TBA.
+2006.07.23-2006.07.28:
+ANTS.
<p>
-2006.08:
+2006.08.20-2006.08.24:
CRYPTO 2006.
<p>
-2006.09-2006.12, plan to attend:
+2006.09-2006.12:
Fields Institute Thematic Program in Cryptography.
</body>
</html>
diff -ru .old-crypto/snuffle/topleft9.c cr.yp.to/snuffle/topleft9.c
--- .old-crypto/snuffle/topleft9.c 2005-08-28 16:57:06.000000000 -0400
+++ cr.yp.to/snuffle/topleft9.c 2005-08-28 17:00:31.000000000 -0400
@@ -104,7 +104,7 @@
long long sum;
long long count;
- for (bits = 1;bits <= 16;++bits) {
+ for (bits = 1;bits <= 8;++bits) {
max = (1 << bits) - 1;
for (keys = 0;keys < 10;++keys) {
k[0] = getchar() & max;
diff -ru .old-crypto/snuffle/topleft9.out cr.yp.to/snuffle/topleft9.out
--- .old-crypto/snuffle/topleft9.out 2005-08-28 16:57:06.000000000 -0400
+++ cr.yp.to/snuffle/topleft9.out 2005-08-28 19:30:12.000000000 -0400
@@ -61,3 +61,10 @@
7 bits, key 0: 134215436 negative, 268435456 total, fraction 0.499991
7 bits, key 1: 134222753 negative, 268435456 total, fraction 0.500019
7 bits, key 2: 134232370 negative, 268435456 total, fraction 0.500055
+7 bits, key 3: 134213168 negative, 268435456 total, fraction 0.499983
+7 bits, key 4: 134216452 negative, 268435456 total, fraction 0.499995
+7 bits, key 5: 134208852 negative, 268435456 total, fraction 0.499967
+7 bits, key 6: 134225442 negative, 268435456 total, fraction 0.500029
+7 bits, key 7: 134216336 negative, 268435456 total, fraction 0.499995
+7 bits, key 8: 134212242 negative, 268435456 total, fraction 0.499980
+7 bits, key 9: 134221003 negative, 268435456 total, fraction 0.500012