Question

求计算过程：

一：3^97 mod 353
二：3^233 mod 353

Answer 1

一. 因 3^6=729 3^6mod353=23
(3^6)^2 mod 353= (23)^2
3^12 mod 353= 529mod 353= 176
3^24mod353= 176^2mod353 =30976mod 353= 265
3^48mod353= 265^2mod 353=331
97 = 48+24+24 +1
所以 3^97mod353= (3^48mod353)( 3^24mod353)(3^24mod353)(3mod353)
= (265mode 353)(176mod 353)( 176mod 353)(3mode 353)
= (46640mode 353) (176mod 353)(3mod 353)
= (44mod353)( 176mode 353)(3mod 353)
= 23232mode 353
= 287
二. 3^233mod 353= (3^48mode 353)^2(3^39mode 353)
= (287mode 353)^2 (3^24mode 353) (3^12mode353)(3^3mode 353)
= (82369mod 353) (265mod 353)(176mod 353)( 27mode353)
= [(120mode 353) (256mod353)][(176mod353) (27mod353)]
= ( 30720mode 353)(4752mod353)
= (9mod 353) (163mod353)
= (1467mod 353)
= 55