04-06-2020, 01:31 PM
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⁸⁵}₃₄₁ = 32 .
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
"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⁸⁵}₃₄₁ = 32 .
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