:

Two dimensional simple random walk to factorize integer

Maple 2021

aRandStep2D := proc(X0, Y0, dx, dy)
local X, Y, P, R;
P := Array(1 .. 2);
R := rand(1 .. 8)();
if R = 1 then X := X0 - dx; Y := Y0 + dy; end if;
if R = 2 then X := X0; Y := Y0 + dy; end if;
if R = 3 then X := X0 + dx; Y := Y0 + dy; end if;
if R = 4 then X := X0 - dx; Y := Y0; end if;
if R = 5 then X := X0 + dx; Y := Y0; end if;
if R = 6 then X := X0 - dx; Y := Y0 - dy; end if;
if R = 7 then X := X0; Y := Y0 - dy; end if;
if R = 8 then X := X0 + dx; Y := Y0 - dy; end if;
P[1] := X; P[2] := Y;
return P;
end proc

SetStart := proc(b)
local alpha, R, P;
P := Array(1 .. 2);
alpha := rand(1 .. b)();
P[1] := alpha*b;
P[2] := alpha*b;
return P;
end proc

RandomFactTpq := proc(N, pb, dx, dy)
local alpha, X, Y, f, P, counter, B, n, T;
P := Array(1 .. 2);
counter := 0; f := 1;
B := floor(evalf(sqrt(N))); #Set maximal searching steps
T := floor(evalf(sqrt(N))); #For SetStart's use
P := SetStart(T);
X := P[1]; Y := P[2];
while f = 1 and counter < B do  #loop
n := pb - X - Y;
f := gcd(N, n);
if f > 1then break; end if;
P := aRandStep2D(X, Y, dx, dy); #A random move
X := P[1]; Y := P[2];
if X < 1 or Y < 1 or N - pb - 1 < X or X <= Y then
P := SetStart(T);       # Restart when out of borders
X := P[1]; Y := P[2];
end if;
counter := counter + 1;    #Counting the searched steps
end do;
if  f>1  then print(Find at point (X, Y), found divisor = f, searching steps = counter);
else print(This*time*finds*no*result, test*again!); end if;
end proc

﻿