(39gs) Number Theory Aplet - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: General Software Library (/forum-13.html) +--- Thread: (39gs) Number Theory Aplet (/thread-6559.html) (39gs) Number Theory Aplet - Gerald H - 07-15-2016 07:10 AM Edit 2016-07-17: improved version of INVM. Edit 2016-07-20: improved version of SQFO. Edit 2016-09-26: improved NXPRM & PRPRM to give correct answers for low values of input. The programmes in NT Aplet are meant to be accessed via an aplet in the 39gs. Sadly the 38G does not have enough memory to accomodate all the programmes & function correctly. To create the aplet: 1 Enter all the programmes below in the Program Catalog; 2 Actuate the built-in Function aplet; 3 Run the programme SVIEW; 4 Save the aplet under the name NT; 5 Actuate the aplet NT; 6 Actuate the key VIEW to see the available commands; 7 Choose the command you wish to use. Code: ``` The available commands are: TIME          displays time & date π?            tests integer for primality π↑            finds the least prime greater than input π↓            finds the greatest prime less then input Rand π        finds a random prime Composite        produces an integer the product of two primes Split            finds a factor of composite integer input Next Cornacchia    given D & P, integers & P prime, finds the first solution of x^2+G*y^2=P, G>D Next Modf Corn    given D & P, integers & P prime, finds the first solution of x^2+G*y^2=4*P, G>D & G=0 or 3 MOD 4 Jacobi        returns the Kronecker sign of quadratic residue √(X)MODπ    finds modulo a prime square root of integer, returns zero for no square root Bézout        Extended GCD Z* Inverse        finds multiplicative inverse of an integer modulo an integer, returns zero for no inverse    BEZO Ans►L0: Ans(1)►X: L0(2)►I: (X,1)►Z0: (I,0)►Z1: WHILE RE(Z1) REPEAT Z1►Z3: Z0-INT(RE(Z0)/RE(Z1))*Z1►Z1: Z3►Z0: END: IM(Z0): {Ans,ROUND((RE(Z0)-X*Ans)/I,0),RE(Z0)}*SIGN(RE(Z0)):  COMPNR {MIN(Ans,6)}►L0: Ans(1): RUN PFOR: CONCAT({Ans},L0)►L0: Ans(2): RUN PFOR: Ans*L0(1): CORN4 Ans►L1: Ans(1)►Y: L1(2)►Z: IF Ansn>=2.5E11 THEN MSGBOX " π>= 2.5E11": ELSE IF Z==2 THEN √(8-Y): IFTE(FRAC(Ans),0,{Ans,1}): ELSE {-Y,Z}: RUN SQRTMODP: IF Ans THEN ABS((Ans-Y) MOD 2*Z-Ans)►B: 2*Z►A: INT(2*√Z)►L: WHILE B>L REPEAT A MOD B►R: B►A: R►B END: √((4*Z-B^2)/Y)►C: IFTE(FRAC(Ans),0,{B,C}): END: END: END: CORNA Ans►L1: Ans(1)►W: L1(2)►Y: {-W,Y}: RUN SQRTMODP: IF Ans THEN MAX(Ans,Y-Ans)►B: Y►A: INT(√Y)►U: WHILE B>U REPEAT A MOD B►Z: B►A: Z►B: END: √((Y-B^2)/W): IF FRAC(Ans) THEN 0: ELSE {B,Ans}: END: END: FACT RUN SFAC: IF Ans==2 THEN {N,1}: RUN SQFO: ELSE N: END: GCD WHILE  U REPEAT U►T: V MOD U►U: T►V: END: IBEZ INPUT Ans;"Bézout";"LIST";"u, v";{7,541}: RUN BEZO: MSGBOX Ans: ICOMP RUN INPI: RUN COMPNR: MSGBOX Ans:  ICORN INPUT Ans;"NEXT CORNACCHIA";"LIST";"d, π in x^2+d*y^2=π";{0,10007}: RUN NEXTCORN: MSGBOX Ans: ICORN4 INPUT Ans;"NEXT MODIFIED CORNACCHIA";"LIST";"d=0,3MOD4,π<2.5E11 in x^2+dy^2=4π ";{0,10007}: RUN NEXTC4: MSGBOX Ans: IFAC RUN INPI: RUN FACT: MSGBOX Ans:  IINV INPUT Ans;"Z* Inverse";"LIST";"z, m";{7,541}: RUN INVM: MSGBOX Ans: IJAC INPUT Ans;"JACOBI TEST";"LIST";"TEST # & MOD";{7,541}: RUN JACOB: MSGBOX Ans: INPI INPUT Ans; "INPUT #"; "INTEGER";"";8616460799:  INVM RUN BEZO: IFTE(Ans(3)==1,Ans(1) MOD I,0):  INXPR RUN INPI: RUN NXPRM: MSGBOX Ans: IPPT RUN INPI: RUN PPT: MSGBOX Ans:  IPRIM RUN INPI: RUN PRIM: MSGBOX Ans: IPRVPR RUN INPI: RUN PRPRM: MSGBOX Ans: IRANP RUN RANPRM: MSGBOX Ans:  ISRMP INPUT Ans;"√ MOD π";"LIST";"TEST # & π";{777,10007}:  RUN SQRTMODP: MSGBOX Ans: JACOB Ans►L1: Ans(1)►A: L1(2)►B: IF B==-1 THEN SIGN(A+.1): ELSE IF B THEN IF (A MOD 2)+(B MOD 2)  THEN 0►V: WHILE NOT(B MOD 2) REPEAT B/2►B: V+1►V: END: 1: IF V MOD 2 THEN IF ABS((A MOD 8)-4)==1  THEN -1: END: END: Ans►K: IF B<0 THEN -B►B: IF A<0 THEN -K►K: END: END: WHILE A REPEAT 0►V: WHILE NOT(A MOD 2) REPEAT V+1►V: A/2►A: END: IF V MOD 2 THEN IF ABS((B MOD 8)-4)==1   THEN -K►K: END: END: IF (A MOD 4)*(B MOD 4)==9 THEN -K►K: END:  ABS(A)►R: B MOD R►A: R►B:  END: (B==1)K: ELSE 0: END: ELSE ABS(A)==1: END: END: MMOD X MOD 1000000►I: X-Ans►X: H MOD 1000000►J: H-Ans: ((X*Ans MOD M+((X*J MOD M+I*Ans MOD -M) MOD -M))MOD -M+I*J )MOD M►X: NEXTC4 Ans►L1: Ans(1)►S: L1(2)►T: DO (S+MAX(3-(S MOD 4),1)) MOD (4*T)►S: {S,T}: RUN CORN4: UNTIL Ans≠0 END: {Ans,S,T}: NEXTCORN Ans►L1: Ans(1)►S: L1(2)►T: DO (S+1) MOD T►S: {S,T}: RUN CORNA: UNTIL Ans≠0 END: {Ans,S,T}:  NXPRM IF Ans<2 THEN 2: ELSE Ans-(NOT Ans MOD 2) ►L: DO L+2►L: DISP 5;"Testing: "Ans: L: RUN PRIM: UNTIL Ans END: L: END: PFOR INT(RANDOM*10^Ans): IF ANS>999999999960 THEN 999999999989: ELSE RUN NXPRM: END: PMOD 1►X: WHILE N REPEAT IF  N MOD 2 THEN N-1►N: A►H: RUN MMOD: END: A: RUN SMOD: Ans►A: N/2►N: END:  X: POLρ Ans►M: 0►K: DO 1►C: 1+K►K: FLOOR(RANDOM*M)►X: X►Y: DO FOR Z=1 TO C STEP 1; Y: RUN SMOD: Ans+K►Y: X-Ans►U: M►V: RUN GCD: ABS(Ans)►V: IF Ans≠1 THEN BREAK: END: END: IF Ans==1 THEN C*2►C: Y►X: FOR Z=1 TO C STEP 1; RUN SMOD: Ans+K: END: Ans►Y: END: UNTIL V≠1 END: UNTIL V≠M END: BEEP 1024;.05: DISP 3;V: FREEZE: POWMOD Ans►L0: L0(1)►A: L0(2)►N: L0(3)►M: RUN PMOD: PPT Ans►R: 1►S: DO S+1►S: Ans►A: R►N: Ans►M: RUN PMOD: Ans-S►U: M►V: RUN GCD: ABS(Ans)►V: IF Ans==1 THEN 0►V: 1: ELSE RUN PRIM: IF Ans THEN R: WHILE NOT(Ans MOD V) REPEAT Ans/V: END: Ans►R: IF R==1 THEN 1: ELSE 0►V: 1: END: ELSE V►R: 0: END: END: UNTIL Ans END: V: PRIM RUN SFAC: IF  Ans==2 THEN N: RUN RABIN: END: PRPRM IF Ans<4 THEN 2: ELSE Ans+(NOT Ans MOD 2)►L: DO L-2►L: DISP 5;"Testing: "Ans: L: RUN PRIM: UNTIL Ans END: L: END:  RABIN Ans►M: INT(RANDOM*(Ans-3))+2►A: RUN SPSF:   RANPRM ERASE: 12: RUN PFOR: SFAC Ans►N: IF 4>N THEN 1: ELSE IF N MOD 2 THEN 1►K: √N: IF FRAC(Ans) THEN FOR I=3 TO MIN(Ans,113) STEP 2; IF NOT N MOD I THEN I►N: 0►K: BREAK: END: END: IFTE(K,IFTE(N<127*131,1,2),0): ELSE Ans►N: 0: END: ELSE 2►N: 0: END: END: SMOD Ans►F: F MOD 1000000►I: F-Ans: (((((Ans^2 MOD -M+Ans*I MOD M) MOD -M)+Ans*I MOD M)MOD -M)+I^2)MOD M: SPSF M-1►N: 0►P: DO P+1►P: N/2►N: UNTIL  Ans MOD 2 END: RUN PMOD: IF  Ans==1  OR  Ans==M-1 THEN 1: ELSE FOR  R=2 TO P STEP 1; RUN SMOD: IF  Ans==M-1 THEN 1: BREAK: END: IF  Ans==1 THEN 0: BREAK: END: END: END: Ans==1: SQFO Ans►L0: ERASE: L0(2)►M: Ans*L0(1)►A: INT(√Ans)►P: Ans►S: A-Ans^2►Q: SYSEVAL 259588: IF Ans THEN IF Ans==1 THEN {2*A,1}: RUN SQFO: ELSE 0►C: INT(√(8*S))►L: DO Q/(2-(Q 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: A►U: R►V: RUN GCD: IF Ans==1 THEN S-((S-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: SQRTMODP Ans►L1: Ans(2)►M: L1(1) MOD M►C: √Ans MOD M►Q: IF FRAC(Ans) THEN L1: RUN JACOB: IF Ans==1 THEN M-1►D: 0►E: WHILE NOT(D MOD 2) REPEAT D/2►D: E+1►E: END: 1►G: WHILE Ans≠-1 REPEAT 1+G►G: {Ans,M}: RUN JACOB: END: G►A: D►N: RUN PMOD: Ans►L: C►A: (D-1)/2►N: RUN PMOD: Ans►Q: RUN SMOD: Ans►X: C►H: RUN MMOD: Ans►O: C►H: Q►X: RUN MMOD: Ans►Q: WHILE O≠1 REPEAT 0►P: WHILE Ans≠1 REPEAT P+1►P: O►A: 2^P►N: RUN PMOD: END: L►A: 2^(E-P-1)►N: RUN PMOD: Ans►H: RUN SMOD: Ans►L: P►E: Q►X: RUN MMOD: Ans►Q: L►X: O►H: RUN MMOD: Ans►O: END: ELSE 0►Q: END: END: Q: SVIEW SETVIEWS "TIME";TIM;7; π?;IPRIM;7; "π^n?";IPPT;7; π↑;INXPR;7; π↓;IPRVPR;7; "Rand π";IRANP;7; Composite;ICOMP;7; Split;IFAC;7; "Next Cornacchia";ICORN;7; "Next Modf Corn";ICORN4;7;  Jacobi;IJAC;7; "√(X)MODπ";ISRMP;7; Bézout;IBEZ;7; "Z* Inverse";IINV;7; " ";SQFO;7; " ";SQRTMODP;7; " ";CORNA;7; " ";CORN4;7; " ";NEXTCORN;7; " ";NEXTC4;7; " ";JACOB;7; " ";PMOD;7; " ";SMOD;7; " ";MMOD;7; " ";GCD;7; " ";BEZO;7; " ";INVM;7; " ";PPT;7; " ";INPI;7; " ";FACT;7; " ";RANPRM;7; " ";COMPNR;7; " ";PFOR;7; " ";PRPRM;7; " ";NXPRM;7; " ";PRIM;7; " ";SFAC;7; " ";RABIN;7; " ";SPSF;7; " ";POWMOD;7; " ";POLρ;7: TIM DISPTIME:```