+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (38G) Pollard's Rho Factorization (/thread-3540.html)
(38G) Pollard's Rho Factorization - Gerald H - 04-02-2015 03:31 PM
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: