Реализации алгоритмов/Метод Лемана

Алгоритм Лемана (или алгоритм Шермана Лемана) детерминировано раскладывает данное натуральное число $~n$ на множители за $~O(n^{1/3})$ арифметических операций.

Delphi

{ Если N является простым, функция вернет -1 }
function GetLehmanFactor(N: Integer): Integer;
var
  I, k, d, A, B, t, dd: Integer;
begin
  Result := -1;

  { Проверка делителей до n^(1/3) }
  for I := 2 to Trunc(Power(N, 1/3)) do
    if N mod I = 0 then begin
      Result := I;
      exit;
    end;

  for k := 1 to Trunc(Power(N, 1/3)) do
    for d := 0 to Trunc( Power(N, 1/6) / (4 * Sqrt(k)) ) + 1 do begin
      A := Trunc(Sqrt(4*k*N)) + d;
      t := Sqr(A) - 4*k*N;

      if t < 0 then
        continue;

      B := Trunc(Sqrt(t));
      if Sqr(B) = t then begin
        ASSERT( (A+B)*(A-B) mod N = 0 );    { Всегда выполняется }

        dd := GCD(A-B, N);

        if (1 < dd) and (dd < N) then begin
          Result := dd;
          exit;
        end;
      end;
    end;
end;

Perl

#!/usr/bin/perl -w
use Math::BigInt;
$N = Math::BigInt->new();
sub nod
 {
 return  $_[0] != 0  ?  nod ( ( $_[1] % $_[0] ), $_[0] )  :  $_[1];
 }
 sub Lehman {
 
	for ($i=2; $i < int($N**1/3);$i++) {
		if (($N % $i) == 0) {
			$Result = $i;
			return 1;
		}
	}
	
	for ($k=1; $k < int($N**1/3); $k++) {
		for ($d=0; $d < int(($N**(1/6))/(4*($k**.5)))+1; $d++) {
			$A = int((4*$k*$N)**.5)+$d;
			$t = ($A**.5) - 4*$k*$N;
		
	
	
			return -1 if $t < 0;
	
			$B = int($t**.5);
	
			if (($B**2) == $t ) {
				$dd = nod($A-$B, $N);
		
				if (1 > $dd and $dd < $N) {
					$Result = $dd;
					return 1;
				}
			}
		}
	}
	return 1;
}
print "Please, input a number N="; chomp($N=<STDIN>);
	if (Lehman == -1) {
		print "Number $N is prime\n";
	} else {
		print "Number $N is not prime\n";
	}