Post Reply 
(41) Exponentiation and Residue Reduction
09-13-2019, 12:32 PM (This post was last modified: 09-13-2019 07:51 PM by SlideRule.)
Post: #1
(41) Exponentiation and Residue Reduction
from Number Theory in Science and Communication, M.R. Schroeder, second enlarged edition, Springer-Verlag {pgs. 341-344}

PHP Code:
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 calculatorIn other
words
in our acute bracket notation the calculator calculates
(aⁿ)⒨ .                                                                        
The 3 variablesthe base a the exponent n and the modulus m are entered
into the calculator in that order
.
     
To call the programwhich is labeled "AN"from storageone presses
     GTO   
"AN"
To calculatesay,
     (
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
2⁸ 2⁶ 2⁴ 2² 340. Check!
     
Nextthe computer will start the necessary repeated squarings and
reductions modulo 341which will take about 7 secondsThen the display
will show the end result
a 1 (without a decimal point!).
Thus,
     (
2³⁴⁰)₃₄₁ .
In other words341 is a pseudoprime to the base 2.
     Similarly
after pressing 2ENTER170ENTER341R/Sthe display
shows in succession
:
     
7. 5. 3. 1.     1
where that last display 
(the 1 without the decimal pointtells us that
     
(2¹⁷⁰)₃₄₁ .
Proceeding in the same mannerwe find
     
(2⁸⁵)₃₄₁ 32 .
i.e., 341 is not a strong pseudoprime to the base 2. Alsoby using 3 as a base
we find
     
(3³⁴⁰)₃₄₁ 56 .
Thus341 is certainly not an absolute pseudoprime (Carmichael number).
     
However, for the modulus 2821we find
     
(2²⁸²⁰)₂₈₂₁ = (3^²⁸²⁰)₂₈₂₁ .
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 (32820~821has 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   RCL 16
                             45   RCL 18
                             46   2
                             47   
/
                             
48   x < > Y
                             49   x 
y?
                             
50   XEQ 16
                             51   x
^2
                             52   RCL18
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 

real gems are yet to be revealed from 'obscure' sources.

BEST!
SlideRule

ps: follow-on to this thread, HP-41 Modulo function, in the General Forum HP Calculators (and very old HP Computers)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
(41) Exponentiation and Residue Reduction - SlideRule - 09-13-2019 12:32 PM



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