(38G) (& 39G, 39gs, 40G & 40gs): Shanks Square Form Factorization Programme
03-26-2015, 04:12 PM (This post was last modified: 06-15-2017 01:55 PM by Gene.)
Post: #1
 Gerald H Senior Member Posts: 1,459 Joined: May 2014
(38G) (& 39G, 39gs, 40G & 40gs): Shanks Square Form Factorization Programme
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
 « Next Oldest | Next Newest »

 Messages In This Thread (38G) (& 39G, 39gs, 40G & 40gs): Shanks Square Form Factorization Programme - Gerald H - 03-26-2015 04:12 PM RE: HP 38G (& 39G, 39gs, 40G & 40gs): Shanks Square Form Factorization Programme - Gerald H - 03-27-2015, 06:41 AM

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