(41) Exponentiation & Residue Reduction
04-26-2022, 10:59 AM (This post was last modified: 04-26-2022 01:20 PM by Thomas Klemm.)
Post: #5
 Thomas Klemm Senior Member Posts: 2,145 Joined: Dec 2013
Errata: (41) Exponentiation & Residue Reduction
Errata

342 Appendix

This is the binary decomposition of the exponent 340.

Check: $$2^8 + 2^6 + 2^4 + 2^2 = 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,

$$\left< 2^{340} \right>_{341} = 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

$$\left< 2^{170} \right>_{341} = 1$$.

Proceeding in the same manner, we find

$$\left< 2^{85} \right>_{341} = 32$$,

i.e., 341 is not a strong pseudoprime to the base 2. Also, by using 3 as a base
we find

$$\left< 3^{340} \right>_{341} = 56$$.

Thus, 341 is certainly not an absolute pseudoprime (Carmichael number).

However, for the modulus 2821, we find

$$\left< 2^{2820} \right>_{2821} = \left< 3^{2820} \right>_{2821} = 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 $$\left< 2^{2820} \right>_{2821}$$ has coped with a number having 1346
decimal digits! This has been made possible by the frequent intermediate
modulo reduction that the program employs.

Appendix 343

Original program for the HP-41C:
Code:
01 LBL "AN"        ; call program 02 SF 29           ; decimal point 03 STO 18          ; store modulus 04 RDN             ; get exponent 05 STO 17          ; store exponent 06 RDN             ; get base 07 STO 16          ; store base 08 2               ; constant 09 STO 01          ; store 2 10 LN              ; take logarithm 11 STO 15          ; store log 12 FIX 0           ; display no fractions 13 1               ; constant 14 STO 14          ; store 1 15 0               ; constant 16 STO 02          ; store 0 17 LBL 10          ; subroutine for calculating 18 RCL 17          ; binary representation of ? 19 LN 20 RCL 15 21 / 22 0.000000001     ; add small constant to 23 +               ; avoid inaccurate rounding 24 INT 25 ENTER 26 ST- IND 01 27 PSE             ; display the binary 28 1               ; exponents of ? 29 ST+ 01 30 RDN 31 STO IND 01 32 2 33 X<>Y 34 Y^X 35 ST- 17 36 RCL 17 37 X=0?            ; binary representation 38 GTO 11          ; of ? completed? 39 GTO 10 40 LBL 11          ; subroutine for executing 41 RCL IND 01      ; repeated squaring 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 RCL 18 53 MOD             ; take remainder 54 STO 16          ; modulo ? 55 1 56 ST- IND 01 57 GTO 11 58 LBL 12          ; subroutine for cal- 59 RCL 16          ; culating intermediate 60 ST* 14          ; squaring results 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 76 LBL 13          ; Subroutine for 77 RCL 14          ; recalling and 78 CF 29           ; displaying residue 79 STOP            ; display residue 80 GTO "AN"        ; ready to start over 81 RTN 82 END

Translated program for the HP-42S:
Code:
00 { 141-Byte Prgm } 01▸LBL "AN" 02 SF 29 03 STO 18 04 R↓ 05 STO 17 06 R↓ 07 STO 16 08 2 09 STO 01 10 LN 11 STO 15 12 FIX 00 13 1 14 STO 14 15 0 16 STO 02 17▸LBL 10 18 RCL 17 19 LN 20 RCL 15 21 ÷ 22 0.000000001 23 + 24 IP 25 ENTER 26 STO- IND 01 27 PSE 28 1 29 STO+ 01 30 R↓ 31 STO IND 01 32 2 33 X<>Y 34 Y↑X 35 STO- 17 36 RCL 17 37 X=0? 38 GTO 11 39 GTO 10 40▸LBL 11 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 RCL 18 53 MOD 54 STO 16 55 1 56 STO- IND 01 57 GTO 11 58▸LBL 12 59 RCL 16 60 STO× 14 61 RCL 14 62 RCL 18 63 MOD 64 STO 14 65 1 66 STO- 01 67 RCL 01 68 2 69 X=Y? 70 GTO 13 71 GTO 11 72▸LBL 16 73 RCL 18 74 - 75 RTN 76▸LBL 13 77 RCL 14 78 CF 29 79 STOP 80 GTO "AN" 81 RTN 82 END

Resources
 « Next Oldest | Next Newest »

 Messages In This Thread (41) Exponentiation & Residue Reduction - SlideRule - 04-06-2020, 01:31 PM RE: (41) Exponentiation & Residue Reduction - Werner - 05-08-2020, 01:58 PM RE: (41) Exponentiation & Residue Reduction - Albert Chan - 05-11-2020, 02:55 PM RE: (41) Exponentiation & Residue Reduction - Thomas Klemm - 04-26-2022, 03:17 AM Errata: (41) Exponentiation & Residue Reduction - Thomas Klemm - 04-26-2022 10:59 AM Errata: (41) Exponentiation & Residue Reduction - Thomas Klemm - 04-26-2022, 04:05 PM

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