Post Reply 
(39gs) Number Theory Aplet
07-15-2016, 07:10 AM (This post was last modified: 10-04-2017 11:53 AM by Gerald H.)
Post: #1
(39gs) Number Theory Aplet
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:
Find all posts by this user
Quote this message in a reply
Post Reply 




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