#!/usr/local/bin/perl -w
# getcycle.pl
# (Copyright) Robert A. Lacroix, Feb. 6, 2001; Winnipeg, Canada
# This algorithm efficiently solves problems of the form 2^x = aN + 1,
# using O(log N) storage and O(log N)(log N) time.
# I am reinventing the wheel, or is it "Goodbye, RSA?"
# Input restrictions: argument N must be a positive odd integer.
# This implementation is subject to machine word size overflow.
#
# Happy Birthday, Vonne.
use integer;
local ($i, $n, $a, $b, $c, $k, $p, $x);
$n = $ARGV[0];
if (($n & 1) == 0) { die "$n is even\n"; }
$a = 0; # multiple of N
$b = 0; # partial 2^x; actually uses 2(log N) bits at a time.
$p = 0; # bit shift offset
$i = 0; # iteration count
while (1 == 1) {
$k = (($b + 1) & ~$b); # mask for least significant 0 bit
last if ($k > 1 && $k == $b+1); # loop exit condition
$a |= $k << $p; # merge into result
$c = -1; # determine bit position (base offset 0)
while ($k != 0) {
$k >>= 1;
$c++;
}
$p += $c; # cumulative offset
$b = ($b >> $c) + $n;
$i++;
}
# complete the solution.
$b = $a * $n + 1;
$x = -1;
while ($b != 0) {
$b >>= 1;
$x++;
}
print "2^$x = $a * $n + 1 in $i iterations\n";
sample run:
getcycle.pl 231
2^30 = 4648233 * 231 + 1 in 12 iterations