Free42: Modulo Powering Programme

[Gerald H]

Free42 can reliably deal with exact calculations on integer arguments with 11 digits (possibly higher, but I'm not sure).

The programme MOD↑ calculates the Yth power of Z modulo base X.

eg For input

7777777

7777777

10^21

the programme returns

951673149961995347697.

Remember: modulo powering provides a quick pseudo-prime test, namely if

a ^ (b - 1) mod b = 1

it's a fairly safe bet b is prime.

Code:

0.    { 60-Byte Prgm }
1.    LBL “MOD↑”
2.    STO 01
3.    +/-
4.    STO 00
5.    R↓
6.    LBL “M↑”
7.    STO 02
8.    R↓
9.    STO 03
10.    SIGN
11.    GTO 00
12.    LBL 01
13.    2
14.    MOD
15.    X≠0?
16.    GTO 02
17.    LASTX
18.    STO/ 02
19.    RCL 03
20.    XEQ “SQM”
21.    STO 03
22.    RCL 02
23.    GTO 01
24.    LBL 02
25.    STO- 02
26.    RCL 04
27.    RCL 03
28.    XEQ “M*”
29.    LBL 00
30.    STO 04
31.    RCL 02
32.    X≠0?
33.    GTO 01
34.    R↓
35.    END


0.    { 45-Byte Prgm }
1.    LBL “SQM”
2.    STO ST Y
3.    1E11
4.    MOD
5.    STO ST Z
6.    –
7.    ENTER
8.    X^2
9.    RCL 00
10.    MOD
11.    X<>Y
12.    R↑
13.    STO* ST T
14.    *
15.    RCL 01
16.    MOD
17.    RCL- ST L
18.    RCL+ ST L
19.    RCL 01
20.    MOD
21.    +
22.    RCL 00
23.    MOD
24.    +
25.    RCL 01
26.    MOD
27.    END


0.    { 60-Byte Prgm }
1.    LBL “M*”
2.    RCL ST X
3.    1E11
4.    MOD
5.    X<>Y
6.    RCL- ST Y
7.    COMPLEX
8.    X<>Y
9.    1E11
10.    MOD
11.    RCL ST Z
12.    RCL- ST Y
13.    RCL* ST Z
14.    X<>Y
15.    RCL* ST Z
16.    COMPLEX
17.    RCL 00
18.    MOD
19.    +
20.    RCL 01
21.    MOD
22.    X<>Y
23.    COMPLEX
24.    RCL 00
25.    MOD
26.    X<>Y
27.    RCL 01
28.    MOD
29.    +
30.    RCL 00
31.    MOD
32.    +
33.    RCL 01
34.    MOD
35.    END