Re: [FWP] crypt() fun

[Ariel Scolnicov <ariels@compugen.co.il>]

sthoenna@efn.org (Yitzchak Scott-Thoennes) writes:

> In article <20000613113552.J525@rahul.net>, Bennett Todd <bet@rahul.net> wrote:
> > 	my $last = '';
> > 	my $cur = random_string_gen();
> > 	my @lag = ($cur);
> > 	while (1) {
> > 		$last = $cur;
> > 		$cur = crypt($cur, $cur);
> > 		last if $last eq $cur;
> > 		$cur = random_string_gen() and @lag=($cur) if $lag[0] eq $cur;
> > 		push @lag, $cur;
> > 		$last = $cur;
> > 		$cur = crypt($cur, $cur);
> > 		last if $last eq $cur;
> > 		$cur = random_string_gen() and @lag=($cur) if shift(@lag) eq $cur;
> > 		if ($#lag > 10000) {
> > 			$cur = random_string_gen();
> > 			@lag = ($cur);
> > 		} else {
> > 			push @lag, $cur;
> > 		}
> > 	}
> 
> Ok, I give up trying to understand what this is supposed to accomplish.
> Can you annotate it?
> 
> > or thereabouts. Naturally it'd be rather more painful to try and say
> > this sort o' thing in C :-).
> 
> In C you would probably use a circular buffer (with start and end pointers)
> in place of @lag.  I don't see anything inherently painful to do in C here.
> 

To detect a cycle, you can use a constant-memory algorithm.  WARNING:
THIS IS UNTESTED CODE!

# Does f loop when started on 0?
my ($x, $x2);
$x = $x2 = 0;
do {
    $x = f($x);
    $x2 = f(f($x2));
} while ($x != $x2);                    # assuming "==" valid for f()'s type

The loop terminates when a cycle is found (and only then, and always
finds a cycle if there is one).  Think of 2 people running on an
unlimited road, one twice as fast as the other.

However, I'm fairly confident that DES has no known fixpoints.
Perhaps some modification would...

-- 
Ariel Scolnicov        |"GCAAGAATTGAACTGTAG"            | ariels@compugen.co.il
Compugen Ltd.          |Tel: +972-2-6795059 (Jerusalem)	\ We recycle all our Hz
72 Pinhas Rosen St.    |Tel: +972-3-7658514 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555    http://3w.compugen.co.il/~ariels

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe