(41) Exponentiation & Residue Reduction
04-06-2020, 01:31 PM
Post: #1
 SlideRule Senior Member Posts: 1,313 Joined: Dec 2013
(41) Exponentiation & Residue Reduction
Pages 341 & 344 from Number Theory in Science and Communication, Second Enlarged Edition, © Sprinler·Veriag Berlin Heidelberg 1984 and 1986, ISBN 978-3-662-22246-1 (eBoook)

"A. A Calculator Program for Exponentiation and Residue Reduction
We list here a program for calculating the least nonnegative remainder of aⁿ modulo m on a Hewlett-Packard 41C or 41CV pocket calculator. In other words, in our acute bracket notation, the calculator calculates

The 3 variables, the base a, the exponent n and the modulus m are entered into the calculator in that order.
To call the program, which is labeled "AN", from storage, one presses
GTO "AN" .
To calculate, say,
{2³⁴⁰}₃₄₁ ,
one proceeds by pressing the following buttons:
2
ENTER
340
ENTER
341
To start the program, one presses
R/S
After 2 seconds the HP 41 display shows in rapid succession
8.
6.
4.
2.
This is the binary decomposition of the exponent 340.

Check: 28 + 26 + 24 + 22 = 340. Check!

Next, the computer will start the necessary repeated squarings and reductions modulo 341, which will take about 7 seconds. Then the display will show the end result, a 1 (without a decimal point!).
Thus,
{2³⁴⁰)₃₄₁ = 1 .
In other words, 341 is a pseudoprime to the base 2.
Similarly, after pressing 2, ENTER, 170, ENTER, 341, R/S, the display shows in succession:
7.    5.    3.    1.        1
where that last display (the 1 without the decimal point) tells us that
{2¹⁷⁰}₃₄₁ = 1 .
Proceeding in the same manner, we find
{2⁸⁵}₃₄₁ = 1 .
i.e., 341 is not a strong pseudoprime to the base 2. Also, by using 3 as a base we find
{3³⁴⁰}₃₄₁ = 56 .
Thus, 341 is certainly not an absolute pseudoprime (Carmichael number).
However, for the modulus 2821, we find
{2²⁸²⁰}₂₈₂₁ = {3²⁸²⁰}₂₈₂₁ = 1 .
two of the many steps necessary to show that 2821 is an absolute pseudoprime or a Carmichael number
Note that our little calculator with a limited accuracy and a 10-digit display, in calculating (3²⁸²⁰}₂₈₂₁, has coped with a number having 1346 decimal digits! This has been made possible by the frequent intermediate modulo reduction that the program employs.

Listing for "AN"
Comment                          Step    Code
call program                       01       LBL "AN"
decimal point                     02       SF 29
store modulus                    03       STO 18
get exponent                     04       RDN
store exponent                  05       STO 17
get base                           06       RDN
store base                         07       STO 16
constant                           08       2
store 2                             09       STO 01
take logarithm                    10       LN
store log                           11       STO 15
display no fractions             12       FIX 0
constant                           13       1
store 1                             14       STO 14
constant                           15       0
store 0                             16       STO 02
subroutine for calculating     17       LBL 10
binary representation of n    18       RCL 17
19       LN
20       RCL 15
21       /
add small constant to          22       0.000000001
avoid inaccurate rounding     23       +
24       INT
25       ENTER
26       ST- IND 01
display the binary                27       PSE
exponents of n                   28       1
29       ST+ 01
30       RDN
31       STO IND 01
32       2
33       x <> y
34       y^x
35       ST- 17
36       RCL 17
binary representation           37       x = 0?
of n completed?                  38       GTO 11
39       GTO 10
subroutine for executing       40       LBL 11
repeated squaring               41       RCL IND 01
42       x = 0?
43       GTO 12
44       RCL16
45       RCL 18
46       2
47       /
48       x < > y
49       x > y?
50       XEQ 16
51       x²
52       RCL 18
take remainder                   53       MOD
modulo n                           54       STO 16
55       1
56       ST- IND 01
57       GTO 11
subroutine for cal-              58       LBL 12
culating intermediate           59       RCL 16
squaring results                  60       ST* 14
61       RCL 14
62       RCL 18
63       MOD
64       STO 14
65       1
66       ST- 01
67       RCL 01
68       2
69       x = y?
70       GTO 13
71       GTO 11
72       LBL 16
73       RCL 18
74       -
75       RTN
Subroutine for                    76       LBL 13
recalling and                      77       RCL 14
displaying residue                78       CF 29
display residue                    79       STOP
ready to start over              80       GTO "AN"
81       RTN
82       END"

BEST!
SlideRule
05-08-2020, 01:58 PM
Post: #2
 Werner Senior Member Posts: 648 Joined: Dec 2013
RE: (41) Exponentiation & Residue Reduction
Stack-only, without synthetics, 50 bytes
Calculate R := B^X mod M
Code:
                L       X       Y       Z       T 01>LBL"Z^YMOD"          M       X       B 02 ABS 03 1 04 RDN 05 RDN 06>LBL 02       M       X       B       R 08 2 09 ST/ Y 10 X<> L                M       X/2     B       R 11 X<>Y 12 INT 13 ST- L        FP(X)   IP(X)   M       B       R 14 RDN 15 X<> L 16 X=0?         M       FP(X)   B       R       X 17 GTO 00 18 RDN         @ R := MOD(R*B,M); 19 STx Y 20 X<>Y         M       R.B     B       X 21 LASTX 22 MOD 23 X<> Z         24>LBL 00       M       -       B       R       X 25 RDN         @ B := MOD(B^2,M); 26 STx X        M       B^2     R       X 27 LASTX 28 MOD          M       B       R       X       X 29 RUP 30 X!=0?        M       X       B       R 31 GTO 02 32 RCL Z 33 END

Cheers, Werner
05-11-2020, 02:55 PM (This post was last modified: 05-11-2020 07:30 PM by Albert Chan.)
Post: #3
 Albert Chan Senior Member Posts: 1,646 Joined: Jul 2018
RE: (41) Exponentiation & Residue Reduction
(05-08-2020 01:58 PM)Werner Wrote:  Stack-only, without synthetics, 50 bytes
Calculate R := B^X mod M ...

Amazing !
I touch up a bit so that it can copy/paste directly into Free42 (52 bytes)
Code:
01▸LBL "Z↑YMOD" 02 ABS 03 1 04 R↓ 05 R↓ 06▸LBL 02 07 2 08 STO÷ ST Y 09 X<> ST L 10 X<>Y 11 IP 12 STO- ST L 13 R↓ 14 X<> ST L 15 X=0? 16 GTO 00 17 R↓ 18 STO× ST Y 19 X<>Y 20 LASTX 21 MOD 22 X<> ST Z 23▸LBL 00 24 R↓ 25 STO× ST X 26 LASTX 27 MOD 28 R↑ 29 X≠0? 30 GTO 02 31 RCL ST Z 32 END

Example 123^456 mod 789:

123 [Enter] 456 [Enter] 789 [XEQ] "Z↑YMOD" ﻿ ﻿ ﻿ ﻿ → 699

This version does binary ladder expoentiation from right to left, like this:
Code:
(define (pow-mod b x m r)   (if (fxzero? x) r       (pow-mod [mod (* b b) m] [fx/ x 2] m         [if (even? x) r (mod (* b r) m)] )))

scheme> (trace pow-mod)
(pow-mod)
scheme> (pow-mod 123 456 789 1)
|(pow-mod 123 456 789 1)
|(pow-mod 138 228 789 1)
|(pow-mod 108 114 789 1)
|(pow-mod 618 57 789 1)
|(pow-mod 48 28 789 618)
|(pow-mod 726 14 789 618)
|(pow-mod 24 7 789 618)
|(pow-mod 576 3 789 630)
|(pow-mod 396 1 789 729)
|(pow-mod 594 0 789 699)
|699
699
 « Next Oldest | Next Newest »

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