(33S) Pollard's Rho Factorisation

[Gerald H]

The main programme is SPLIT: given a positive composite integer input N, SPLIT returns a factor < N , possibly neither the smallest nor prime. Maximum value of N is 10^12-1.

LN= gives the size of the programme, CK= is the check sum - these two measures are depressingly meaningful in this calculator, if length or check sum is different on your machine, this has no transcendent meaning, you have simply mis-typed the programme.

The sub programme F takes input integer & calculates the square modulo A, -A must be in B.

F1 LBL F SQUARE MODULO 

F2 ENTER

F3 ENTER

F4 1000000

F5 RMDR

F6 STO Z

F7 -

F8 ENTER

F9 x2

F10 RCL B

F11 RMDR

F12 x<>y

F13 RCL* Z

F14 RCL A

F15 RMDR

F16 ENTER

F17 RCL- A

F18 +

F19 RCL A

F20 RMDR

F21 +

F22 RCL B

F23 RMDR

F24 RCL Z

F25 x2

F26 +

F27 RCL A
LN=99
F28 RMDR
CK=9D84
F29 RTN

Given integers in stack levels X & Y programme X returns the greatest common divisor of the two integers.

X1 LBL X GREATEST COMMON FACTOR

X2 RMDR

X3 LASTx

X4 x<>y

X5 x≠0?

X6 GTO X

X7 R↓
LN=27
X8 ABS
CK=848A
X9 RTN

Programme L finds small factors of input N, the number to be factored. Line 21 suggests alternative upper limits for the search.

L1 LBL L SMALL FACTORS

L2 +/-

L3 STO B

L4 +/-

L5 STO A

L6 4

L7 x>y?

L8 RTN

L9 CLx

L10 2

L11 RMDR

L12 x=0?

L13 RTN

L14 RCL A

L15 √x

L16 FP

L17 x=0?

L18 RTN

L19 LASTx

L20 IP

L21 113 Or 199 Or 283

L22 x>y?

L23 x<>y

L24 1000

L25 ÷

L26 300.002
LN=144
L27 +
CK=BFDC
L28 STO I

A1 LBL A

A2 RCL A

A3 RCL I

A4 IP

A5 RMDR

A6 x=0?

A7 RTN

A8 ISG I

A9 GTO A

A10 1
LN=48
A11 STO C
CK=1B8C
A12 RTN

N1 LBL N

N2 CLx

N3 RCL A

N4 x<>y

N5 x≠y?
LN=21
N6 RTN
CK=33B3
N7 ISG C

D1 LBL D POLLARD’S RHO

D2 1

D3 STO V

D4 STO U

D5 RANDOM

D6 RCL* A
LN=36
D7 IP
CK=9C81
D8 STO X

J1 LBL J

J2 XEQ F

J3 RCL+ C

J4 ENTER

J5 RCL- X

J6 RCL A

J7 XEQ X

J8 1

J9 x≠y?

J10 GTO N

J11 R↓

J12 R↓

J13 DSE U

J14 GTO J

J15 RCL V

J16 RCL+ V

J17 STO V
LN=69
J18 STO U
CK=3D16
J19 R↓

V1 LBL V

V2 XEQ F

V3 RCL+ C

V4 DSE U

V5 GTO V

V6 STO X

V7 RCL V
LN=30
V8 STO U

V9 R↓
CK=098A
V10 GTO J

S1 LBL S SPLIT

S2 XEQ L

S3 x≠0?

S4 GTO D

S5 RCL A
LN=21
S6 LASTx
CK=90F8
S7 RTN