+- 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: