cryptograph(y|er) jokes? (Superpolynomial subexponential runtimes, or, How to Give a Math Lecture at a Party, by Eric Hughes)
Jeff.Hodges at KingsMountain.com
Jeff.Hodges at KingsMountain.com
Thu Jun 24 19:47:47 EDT 2004
it's kinda long, but I was at the Cryptorights party (as were many others on
this list) where Eric did this and it was really very funny.
JeffH
available at..
http://www.xent.com/FoRK-archive/oct00/0429.html
http://www.cryptorights.org/events/2000/superpolynomial.html
> Subject: How to Give a Math Lecture at a Party.
> Date: Tue, 17 Oct 2000 20:32:09 -0700
> From: Eric Hughes <eh at ricochet.net>
> To: Dan Haney <salvarsan at std.com>
How to Give a Math Lecture at a Party.
1. Pick the right party. I would suggest the RSA patent expiration
party
to benefit the CryptoRights Foundation, but that party has already
happened. (See http://cryptorights.org/events/patent-benefit.html )
1a. Ensure that there are a bunch of people at the party who've had
to learn more about modular rings than they ever thought they
would.
1b. Ensure that these people have also had to think about
analysis of runtimes.
1c. In short, ensure that there are a bunch of cypherpunks and their
fellow-travellers hanging around.
2. Have the MC give away the punch line by announcing that you're going to
sing a funny song.
3. Begin by insisting that the MC was mistaken. Announce that you're
going to give a math lecture instead, and turn on the overhead
projector. (Props are important signals of intent here.)
4. Put up, in sequence, the following four slides. Prepare the slides to
be unnecessarily notational.
4-1. A description of the RSA algorithm. Include the statement N=pq and
make sure to include the notation for the Euler totient function.
4-2. A description of the algorithmic runtime of the Number Field
Sieve. It's really messy. Write it all out and go through it
in loving detail. Talk about the best known constants. Be sure
to drop Don Copperfield's name, because many good mathematical
cryptography lectures do so. Point out that the logarithm of a
logarithm is uncommon.
4-3. The assertion that the runtime of the NFS is slower than every
polynomial function in the limit of large inputs. Use first
order logic notation to avoid as many understandable words as
possible.
4-4. The assertion that the runtime of the NFS is faster than every
exponential function with arbitrary constant base in the limit
of large inputs. Again, use first order logic notation.
5. Say the words, "So the NFS has ..." and proceed without pause to the
next step.
6. Break into song. Sing the following lyrics to the obvious Mary Poppins
tune.
> Superpolynomial subexponential runtimes.
> Even though in practice it would take you several lifetimes,
> If you ran it long enough you'd always find those two primes.
> Superpolynomial subexponential runtimes
>
> E to the root-log root-log-log [4x]
>
> When I was but a naive lad first coding two's and three's
> I thought the only "orders of" were trivialities.
> But when I saw this function something opened up to me
> The elegance of computational complexity.
>
> [Chorus]
>
> I was at a meeting when up came a man in black
> Who told me that his agency had mounted an attack.
> Convincing him was fruitless that his budget would collapse
> All I know his trumpeter will soon be playing Taps.
>
> [Chorus]
>
> In virtual environments has grown up a debate
> Of whether strong cryptography can overthrow the state.
> But several such technologies including public key
> Shall herald in the coming age of crypto-anarchy.
>
> Superpolynomial subexponential runtimes
> Superpolynomial subexponential runtimes
> Superpolynomial subexponential runtimes
> Superpolynomial subexponential runtimes
6a. Pause during each round of applause so the audience can hear all
the words.
Eric
----
--
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list