+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (38G) (& 39G, 39gs, 40G & 40gs): Shanks Square Form Factorization Programme (/thread-3483.html)
(38G) (& 39G, 39gs, 40G & 40gs): Shanks Square Form Factorization Programme - Gerald H - 03-26-2015 04:12 PM
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:
ENDRE: HP 38G (& 39G, 39gs, 40G & 40gs): Shanks Square Form Factorization Programme - Gerald H - 03-27-2015 06:41 AM
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).