(38G) (& 39G, 39gs, 40G & 40gs): Shanks Square Form Factorization Programme

[Gerald H]

Edit: More efficient programme.
Edit: Replaced syseval in 39gs & later models with CLVAR L0.

For input

{N,M}

N, M integers, N composite the programme tries to find a factor of N. As the continued fraction expansion may be too short for factorisation, in which case the programme returns the message "Elliptic Period", the parameter M acts as a multiplier, thus increasing the probability of successful factorisation.

eg {541*107,1} is successfully factorised with multiplier 1.

Should factorisation with M=1 not be successful try some small multiplier, eg M=3, 5, 7.....You may have to remove the multiplier from any factor the programme finds.

The programme on the 38G uses one sub-programme GCD, see below.

The programme's name is SQFO

Code:


Ans►L0:
ERASE:
L0(2)►M:
Ans*L0(1)►A:
INT(√Ans)►P:
Ans►S:
A-Ans^2►Q:
SYSEVAL 532358: @For 339gs, 40G & 40gs CLRVAR L0.
IF Ans THEN
IF Ans==1 THEN
{2*A,1}:
RUN SQFO:
ELSE
0►C:
INT(√(8*S))►L:
DO
Q:
Ans/(2-(Ans MOD 2)):
IF Ans≤L THEN
CONCAT({Ans},L0)►L0:
END:
S-((S+P)MOD Q)►P:
(A-Ans^2)/Q►Q:
INT(√Ans)►R:
NOT C►C:
IF Ans THEN
IF Q==1 THEN
BEEP 512;.5:
MSGBOX "Elliptic Period":
STOP:
END:
Q==R^2:
IF Ans THEN
NOT POS(L0,R):
END:
END:
UNTIL
Ans
END:
R►U: @ For 40G & 40gs
A►V: @ replace these three lines
RUN GCD: @ with GCD(A,R).
IF Ans==1 THEN
S:
Ans-((Ans-P) MOD R):
DO
Ans►P:
(A-Ans^2)/R►R:
S-((S+P)MOD Ans):
UNTIL
P==Ans
END:
R/(2-(R MOD 2)):
ELSE
BEEP 4444;.1:
END:
END:
ELSE
P:
END:
IF NOT(Ans MOD M) THEN
Ans/M:
END:
BEEP 1024;.02: 

GCD

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

[Gerald H]

For those interested in the history of HP calculators, identical SQFO (except for the SYSEVAL number) programmes required for the factorisation of

8,616,460,799

using input

{8616460799,1}

HP 38G: 598 sec

HP 40G: 666 sec.

HP 39gs: 225 sec (added on 2016-07-13).