From: cbbrowne@csi.uottawa.ca (Christopher Browne)
Subject: Re: Irrational numbers as "strong" RNGs?
Organization: Dept. of Computer Science, University of Ottawa
Date: Fri, 2 Oct 92 14:10:46 GMT

In article <1992Oct1.082352.16506@eng.ufl.edu> capsalad@uful07.phys.ufl.edu (Dave Schulman) writes:
>     Here's something that's been troubling me for a while: Bearing in
>mind that 1) commercially available software (Mathematica, Maple,
>etc.) are capable of computing & displaying hundreds of digits of,
>say, pi in next to no time (thousands of digits if you let the program
>run overnight), and that 2) the digits of pi (well, the first billion
>or so anyway) so far appear to be "normal"; that is, they appear with
>roughly equal frequency... 

Well, looking at the Maple situation; it's got 10000 digits of Pi as a
"built-in" thing.  People tend to check out what Pi looks like as one
of their first bits of "playing" with it, so the SCG put 10K digits
in.

I would be totally unsurprised to hear that Wolfram did the same with
Mathematica.

What this means is that there's a table of 10000 digits (which can
probably get BCD packed into about 5K as a "no-brainer" optimization).
I once get Maple going to compute digit 10001.  I didn't wait for it
to find it; it probably would take a LONG time.  Hours?  Days?  Weeks?
I don't know which.

>     Is it possible to use some irrational number as the basis for a
>strong random number generator?  For example, suppose that I was to
>use the decimal part of 17 * (pi * e ^ 5), specifying in advance or
>perhaps as part of a public key sequence which decimal digit would be
>used as the starting point.  If I were to use the aforementioned idea
>with the proviso that the "key" would begin at the 175th digit, this
>would appear to be usable as a random-number generation scheme
>considerably more "random" than any deterministic function that could
>be implemented in software.

It's PROBABLY going to be pretty random; I think there have been a
number of theses in statistics/number theory on the arrangement of
digits in Pi.

Unfortunately, any irrational number whose properties are "ugly"
enough for encryption purposes is probably gonna be a pain to compute
to any significant number of decimal places.

Remember as well that the term "irrational" applies to numbers whose
digits DO have lots of patterns; the only requirement is that the
period be non-constant.

>     Of course, I could further muddle things by factoring in more
>obscure yet easy-to-remember numbers, such as, oh, the inverse
>fine-structure constant, Feigenbaum's number, the wavelengths of the
>Fraunhofer lines....
>
>     If this is a really stupid idea, please tell me so that I can
>quit wasting brain and silicon power on it.  If not, feel free to use
>it if you haven't thought of it already.

I don't think it's stupid, it's just not likely to be {\bf practical}.
This is true of MANY things in math...  

Of late, I've been doing stuff on solving minimum cost network
problems.  There's some recent "cute" algorithms that are
theoretically wonderful.  Unfortunately, the "classic" Simplex method
will beat 'em into the ground for any problems that are not absolutely
ENORMOUS (and that current hardware probably couldn't solve EITHER
way).

Enough work, and perhaps one of the algorithms may be made practical.
And in working on improvements, some other idea may come out.  Working
with irrational number patterns probably works this way too.

-- 
Christopher Browne
cbbrowne@csi.uottawa.ca
University of Ottawa
Master of System Science Program
Newsgroups: sci.crypt