(38G) Pollard's Rho Factorization

[Gerald H]

The programme POL-RHO finds an integer factor, not necessarily the smallest or prime, for positive integer input N, the value taken from the stack in Home view.

The programme has two sub-programmes, see below.

POL—RHO

Ans►M:
0►K:
DO
1►C:
1+K►K:
FLOOR(RANDOM*M)►X:
X►Y:
DO
FOR Z=1 TO C STEP 1;
Y:
RUN SMOD:
Ans+K►Y:
X-Ans►U:
M►V:
RUN GCD:
ABS(Ans)►V:
IF Ans≠1 THEN
BREAK:
END:
END:
IF Ans==1 THEN
C*2►C:
Y►X:
FOR Z=1 TO C STEP 1;
RUN SMOD:
Ans+K:
END:
Ans►Y:
END:
UNTIL
V≠1
END:
UNTIL
V≠M
END:
BEEP 1024;.05:
DISP 3;V:
FREEZE:

The programme SMOD finds the square of Ans modulo M.

SMOD

Ans►F:
F MOD 1000000►I:
F-Ans:
(((((Ans^2 MOD -M+Ans*I MOD M)MOD -M)+Ans*I MOD M)MOD -M)+I^2)MOD M:

The programme GCD finds the greatest common factor of values stored in U & V, the GCF being returned as Ans & stored in V.

GCD

WHILE
U
REPEAT
U►T:
V MOD U►U:
T►V:
END: