(38G) Pollard's Rho Factorization

04022015, 03:31 PM
(This post was last modified: 06152017 01:54 PM by Gene.)
Post: #1




(38G) Pollard's Rho Factorization
The programme POLRHO 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 subprogrammes, 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: XAns►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: FAns: (((((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: 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)