(38G) (& 39G, 39gs, 40G & 40gs): Shanks Square Form Factorization Programme - Printable Version +- 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: END``` RE: 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).