試分析求整數k，k介於1~65536(含)間，且滿足 (3^k) ≡ 2 mod 65537。
提示：3為質數65537的原根(primitive root)，代表3的1到65536不同次方mod 65537會產生1到65536之所有相異整數，不過順序可能有所不同。同時已知 ( 2^32) ≡ 1 mod 65537，且 ( 2^16) ≡ 65536 mod 65537。
2007-11-20 07:10:17 · 4 個解答 · 發問者 玉儒 1 in 科學 ➔ 數學
3^k ≡ 2 ( mod 65537 )
=> 3^( 32 k ) ≡ 2^32 ≡ 1 mod 65537
65537 is a prime & 3 is not divided by 65537
by Fermat's Theorem
3^ ( 65537 - 1 ) ≡ 1 ( mod 65537 )
=> 3^ ( 65536)≡ 1 ( mod 65537 )
=> 3^( 32k ) ≡ 1 ≡ 3^ ( 65536 )
=> k = 2048
2007-11-23 12:35:29 · answer #1 · answered by 失去羽翼的羊 6 · 0⤊ 0⤋
001的答案錯了!
32k應該是65536的倍數
事實上
3^2048≡-8 or 65529 (mod 65537)
正確答案是2048*27=55296
2007-11-28 15:22:47 · answer #2 · answered by mathmanliu 7 · 0⤊ 0⤋
解出來的我承認他神.....
2007-11-22 21:13:09 補充：
先求出K的最小值吧...
2007-11-22 15:23:14 · answer #3 · answered by ? 4 · 0⤊ 0⤋
這個題目是外星人問你的嗎?!-.-
2007-11-22 10:45:39 · answer #4 · answered by ? 4 · 0⤊ 0⤋