發新話題
打印

97附中第二次填第12題

推到噗浪
推到臉書

97附中第二次填第12題

模的題目
在密碼學中,對於英文,人們將26個字母按順序分別對應整數0到25。現有4個字母構成的
密碼單詞,記4個字母對應的數位分別為x(1),x(2),x(3),x(4)。已知:整數x(1)+2x(2),3x(2),x(3)+2x(4),3x(4)除以26的餘數分別為9,16,23,12,則密碼的單詞是?

註( )中的數字表示下標

此提示在考模的題目
答案是HOPE
很漂亮的題目
請問此題命題來源為何

TOP

引用:
原帖由 ksjeng 於 2009-3-13 04:21 PM 發表
模的題目
在密碼學中,對於英文,人們將26個字母按順序分別對應整數0到25。現有4個字母構成的
密碼單詞,記4個字母對應的數位分別為x(1),x(2),x(3),x(4)。已知:整數x(1)+2x(2),3x(2),x(3)+2x(4),3x(4)除以26的餘數分別為9,16,23,12,則密碼的單詞是?

註( )中的數字表示下標

此提示在考模的題目
答案是HOPE
很漂亮的題目
請問此題命題來源為何
已知
\[x_1 +2x_2 \equiv 9 \pmod{26} ......(1)\]
\[3x_2 \equiv 16 \pmod{26} ......(2)\]
\[x_3 +2x_4 \equiv 23 \pmod{26} ......(3)\]
\[x_4 \equiv 12 \pmod{26} ......(4)\]

先找尋 \(3\) 的乘法反元素,先找尋 \(3x+26y=1\) 的任何一組整數解,

(可以利用 \(3\) 跟 \(26\) 作輾轉相除法,或是尤拉法,或是直接聯想都可以)

解得 \(3\times 9 + 26\times \left(-1\right) =1\) ,因此

\[3\times 9 \equiv 1 \pmod{26}\]

也就是找到了 \(\pmod {26}\) 的完全剩餘系統(complete residue system)中, \(3\) 的乘法反元素是 \(9\),

在(2)與(4)中,左右同時乘上 \(9\),可得
\[ 27 x_2 \equiv 144 \pmod{26}  ⇒  x_2 \equiv 14 \pmod{26}\]
\[27 x_4 \equiv 108 \pmod{26}  ⇒  x_4 \equiv 4 \pmod{26}\]

再帶入在(1)與(3)中,可得
\[x_1 \equiv 9 -2 x_2 \equiv -19 \equiv 7 \pmod{26}\]

\[x_3 \equiv 23 -2x_4 \equiv 15 \pmod{26}\]

因此,可得 \(x_1, x_2, x_3, x_4 \pmod{26}\) 分別同餘到 \(7,14,15,4\)

也就是,對應到字母 \(h, o, p, e\).




以上是利用整數論中的同餘,來解題的。

TOP

數論功力果然深厚
我是使用
a≡b(mod m)則m|a-b的定理

TOP

發新話題