Nth digit of PI

[Tim Dixon]

On Mon, 05 Jun 2000 19:55:08 GMT, Rajarshi Ray <rajarshi at home.com>
wrote:

>Besides the gee-whiz aspect of such algorithms, do they have any value?
>After all, what makes pi pi is ALL of its digits in a particular
>sequence.

I can think of a great use for such an algorithm, if one existed (I
think this is a misunderstanding and a closer examination will reveal
that all they've found is that such an algorithm isn't theoretically
impossible or something like that).

The strongest possible encryption is a secret key one time pad.  A one
time pad is an encryption method by which each byte (or couple bytes)
is encrypted using a different key which is discarded and not used
again.  It's not possible to break this kind of encryption without
compromising the "key pad" itself because discovering one byte tells
you nothing about any of the other bytes.  Being unable to test a
sequence of bytes makes it impossible to tell whether you've cracked
the byte or not, and even if you did that, you'd still not have the
rest of the message.  An advantage is the the algorithm can be very
simple (a simple XOR against the key would suffice) because the
security is in the key, not the algorithm.

There are two problems:  one is that it's a secret key system and not
a public key system, so it's not useful for many applications.  It
doesn't work for something like SSL or PGP, for instance.  This is a
characteristic of secret key systems.

The second is the enormous effort involved in producing one time pads.
You need enough bits in your pad to encrypt the entire message;
essentially for a 16K message, your key would have to be 16K long as
well.  Naturally, you need to get the key to the recipient via some
secure means and communicate what portion of the pad is used by a
particular message.

Suppose, however, that you could get digit 'n' of pi directly (or e,
or any other inifinte, nonrepeating sequence).  All I have to do is
communicate which digit of pi the message key starts at, and I can
generate the rest of the key.  I still have the unbreakable nature of
the one time pad, but now I only have to keep secret the starting
point; I can generate the key on the fly.  Keeping *that* secure is
still nontrivial, of course. :-)

>
>Kirby Urner wrote:
>> 
>> Here's another "math through programming" challenge:
>> 
>> Recent number theory breakthrough:  you can get the
>> nth digit of PI without doing all the work needed
>> to compute all the digits up to the nth digit (same
>> with some other numbers -- not sure if we know all
>> the relevant criteria as to which).