第二章一般習題

pages 41 - 43

2.1.1. 考慮質數101。(a) 找出整數 x 與 y 使得 17x+101y=1 (b) 找出 17^{-1} mod101。

ExtendedGCD[17, 101]
PowerMod[17, -1, 101]

2.1.2. 考慮質數 31。(a) 解同餘方程式 7d=1 mod 30。(b) 假設你將一信息表示成模31之下的一個整數 m。將 m 加密為 c=m^7 mod 31。請問你如何將密文 c=21 解密？

PowerMod[7, -1, 30]

Solve[{7*d == 1, Modulus == 30}, d, 
      Mode -> Modular]

PowerMod[21, 13, 31]

PowerMod[22, 7, 31]

2.1.8. 解同餘方程式 3^k\equiv 2 mod{65537}。

Do[If[PowerMod[3, (2^11) m, 65537] == 2, 
        Print["m=", m]], {m, 1, 31, 2}]

k = (2^11)*27

PowerMod[3, %, 65537] == 2

第二章電腦習題

page 43

2.2.1. 計算 gcd(8765, 23485)。

GCD[8765, 23485]

2.2.2. (a) 找出整數 x , y 使 65537x+3511y= 1 (b) 找出整數 x , y 使 65537x+3511y= 17。

ExtendedGCD[65537, 3511]

ExtendedGCD[65537, 3511]*17

65537*(-1405) + 3511*26226
65537*(-23885) + 3511*445842

2.2.3.  試問 3^{1234567} 的最後五位數為何？

Mod[1234567, EulerPhi[100000]]

PowerMod[3, %, 100000]

2.2.4.  解同餘方程式 314x\equiv 271 mod{11111}。

Solve[{314*x == 271, Modulus == 11111}, x, 
      Mode -> Modular]

Mod[PowerMod[314, -1, 11111]*271, 11111]

Mod[314*10298, 11111] == 271

2.2.5.  求同餘方程式 216x\equiv 66 mod{606} 的所有解。

x = 
        Mod[PowerMod[36, -1, 101]*11, 101];
Table[x + 101  j, {j, 0, 5}]

Clear[x]
Solve[{216*x == 66, Modulus == 606}, x, 
      Mode -> Modular]

Mod[216*Table[48 + 101  k, {k, 0, 5}], 606]

2.2.6.  找一整數使得被 101 除餘 17, 被 201 除餘 18, 而被 301 除餘 19。

<< NumberTheory`NumberTheoryFunctions`
ChineseRemainderTheorem[{17, 18, 19}, {101, 201, 301}]

Mod[%, {101, 201, 301}]

2.2.7. 令 n=391=17x23。證 2^{n-1}\not\equiv 1 mod n 並求 j>0 使得 2^j\equiv 1 mod n。

n = 391; PowerMod[2, n - 1, n] == 1

Do[If[PowerMod[2, j, n] == 1, Print[j]], {j, n - 1}]

2.2.8. 令 n=84047x65497。找整數 x 與 y 使 x^2\equiv y^2 mod n 但 x\not\equiv \pm y mod n。

a = 84047; b = 65497; {x = (a + b)/2, y = (a - b)/2}

n = a*b;
Mod[x^2, n] == Mod[y^2, n]
Mod[x, n] == Mod[y, n]
Mod[x, n] == Mod[-y, n]

2.2.9. 試證 3 的確是質數 65537 的一個原根。

PowerMod[3, 2^15, 65537]

2.2.9. 令 M=\pmatrix{1 &2 &4\cr 1 &5 &25\cr 1 &14 &196}。
(a) 求 M 在模 101 之下的逆方陣。
(b) 試問在那一個質數模 p 之下 M 沒有逆方陣？

PolynomialMod[Inverse[{{1, 2, 4}, {1, 5, 25}, {1, 14, 196}}], 
      101]

Det[{{1, 2, 4}, {1, 5, 25}, {1, 14, 196}}] // FactorInteger