[6848] in cryptography@c2.net mail archive
Re: recurrence relation (iterated nonlinear map)
daemon@ATHENA.MIT.EDU (John Denker)
Sat Mar 25 21:48:04 2000
Message-Id: <4.2.2.20000325212637.03f7b100@surfcity.research.att.com>
Date: Sat, 25 Mar 2000 21:43:13 -0500
To: Bram Cohen <bram@gawth.com>, cryptography@c2.net
From: John Denker <jsd@research.att.com>
In-Reply-To: <Pine.LNX.4.10.10003251243130.3998-100000@ultra.gawth.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format=flowed
At 12:50 PM 3/25/00 -0800, Bram Cohen wrote:
>Given that f(x+1) = f(x) * f(x) + c, does anybody know how to express f(x)
>in closed form?
Well... That's an example of an iterated nonlinear map. Such things have
been extensively studied. For some values of c, for some initial
conditions, the iterates quickly converge to fixed points, in which case
there is a very simple closed form :-). For other values of c, you get
chaos, in which case there are some simple things you can say, but probably
not the sort of closed form you were wishing for.
Even in the chaotic regime, such maps do not make good digital
pseudo-random number generators. Basically they act like shift registers,
reading out successive insignificant digits of c. When c is a real
honest-to-goodness real number, the behavior can be quite
interesting; when c is a float I suspect it's much less interesting. But
I'm not a expert. If you really want to know, there are _serious_ experts
on this topic, and dozens of scholarly books.
Cheers --- jsd
