(38G)Modulo Powering

[Gerald H]

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.