Re: encryption with pi

From: Russell Harper (rharper1661_at_rogers.com)
Date: 07/31/04 

Date: Sat, 31 Jul 2004 16:16:42 GMT

"Bob Silverman" <pubkeybreaker@aol.comstuff> wrote in message
news:20040730173049.16456.00000568@mb-m14.aol.com...
> Sigh.
>
> I get tired of this. I am competent to judge.
>
> The proposed cipher is easily broken. Computing the
> n'th digit of Pi can be done in constant time (without
> computing prior values) by an algorithm of
> Simon Plouffe. The algorithm is quite fast.

These are the first few terms, in hexadecimal:

3.2222222222222
0.0212212212212
0.000ACEF6DC435
0.000055038C3FD
0.00000326FE6DE
0.000000215CBB9
0.000000017B1AA
0.0000000011B17
0.0000000000DB6
0.00000000000AF
0.0000000000008
...

Because at least the first two terms are repeating, in order to calculate
any hexadecimal digit, you have to add each term from the first (or zeroth)
up to some limit and using full precision, i.e. no short cuts!

You can discard some leading digits, but not all. For example, consider the
sequence ...1000000... appearing somewhere in pi. While adding up the terms,
it is possible to get ...0FFFFFF... in the process. If you don't keep enough
digits, then you might prematurely report the '1' as a '0', discard it, and
end up displaying ...0000000... instead of ...1000000... This problem is not
unique to the Borwein, Bailey and Plouffe formula, any converging sequence
can "carry forward".

However, the formula is very simple and ideally suited to binary computers,
so maybe that's why it was given the descriptor "miraculous"?

Russell

Relevant Pages