From: pcl@oxford.ac.uk (Paul Leyland)
Newsgroups: sci.crypt
Subject: Re: Irrational numbers as "strong" RNGs?
Date: 1 Oct 92 13:01:46 GMT
	<1992Oct1.082352.16506@eng.ufl.edu>
Organization: Oxford University Computing Service, 13 Banbury Rd, Oxford, OX2
	6NN
In-reply-to: capsalad@uful07.phys.ufl.edu's message of 1 Oct 92 08:23:52 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... 

Fair enough.  They appear random.

	Is it possible to use some irrational number as the basis for a
   strong random number generator?  For example, suppose that I was to

Yes.  There exist some irrational numbers, the sequence of digits
(bits etc) of which are unpredictable in a useful sense.  In fact,
almost all of them have this property.  (Irrationals are uncountable;
programs to calculate the digits are countable.)

   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

So the secret information would be *which* irrational you would be using?

   considerably more "random" than any deterministic function that could
   be implemented in software.

Eh?  You've just described a number which can be generated by a deterministic
function implemented in software.  What is Mathematica, if it isn't software?
How do you propose to use your digits of an irrational number, if you
can't calculate them more than once (i.e. non-deterministic)?

	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....

Translation: you can expand your keyspace by adding in other quantities.

	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.

It doesn't sound "really stupid".  You just have to ensure that the
bit or digit pattern of your irrational isn't predictable.  If I knew
you were using the digits of 3\pi, I could predict the bit stream and
crack your communications.  Another problem might be that actually
calculating the digits might be computationally expensive.

Paul
--
Paul Leyland <pcl@oxford.ac.uk>          | Hanging on in quiet desperation is
Oxford University Computing Service      |     the English way.
13 Banbury Road, Oxford, OX2 6NN, UK     | The time is come, the song is over.
Tel: +44-865-273200  Fax: +44-865-273275 | Thought I'd something more to say.