From: Lacroix, Robert [ralacroix@HYDRO.MB.CA]
Sent: Tuesday, February 06, 2001 5:43 PM
To: BUGTRAQ@SECURITYFOCUS.COM
Subject: Re: Pinoy math enthusiast finds fast way to decode RSA
encryption

#!/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