03-15-2015, 08:22 AM
The programme POWMOD takes a list of 3 integers from the HOME stack,
eg { 2 , 540 , 541}
& returns
2 ^ 540 MOD 541
in Ans & variable X.
Answers are correct for positive integer values of the 3 integers < 10^12.
POWMOD
Ans►L0:
L0(1)►A:
L0(2)►N:
L0(3)►M:
RUN PMOD:
The programme PMOD uses the values in A, N & M to calculate
A ^ N MOD M.
PMOD
1►X:
WHILE N
REPEAT
IF N MOD 2
THEN
A►H:
RUN MMOD:
N-1►N:
END:
A►F:
RUN SMOD:
Ans►A:
N/2►N:
END:
X:
The programme MMOD finds
X * H MOD M.
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:
The programme SMOD finds
Ans ^2 MOD M.
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:
If you're interested in number theory on the 38G try this:
http://www.hpcalc.org/hp38/math/numtheory38.zip
If you replace MMOD & SMOD with the newer versions here all programmes are valid up to 10^12 - 1.
eg { 2 , 540 , 541}
& returns
2 ^ 540 MOD 541
in Ans & variable X.
Answers are correct for positive integer values of the 3 integers < 10^12.
POWMOD
Ans►L0:
L0(1)►A:
L0(2)►N:
L0(3)►M:
RUN PMOD:
The programme PMOD uses the values in A, N & M to calculate
A ^ N MOD M.
PMOD
1►X:
WHILE N
REPEAT
IF N MOD 2
THEN
A►H:
RUN MMOD:
N-1►N:
END:
A►F:
RUN SMOD:
Ans►A:
N/2►N:
END:
X:
The programme MMOD finds
X * H MOD M.
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:
The programme SMOD finds
Ans ^2 MOD M.
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:
If you're interested in number theory on the 38G try this:
http://www.hpcalc.org/hp38/math/numtheory38.zip
If you replace MMOD & SMOD with the newer versions here all programmes are valid up to 10^12 - 1.