第七章一般習題

page 173

7.1.2. (a) 求 x^2=133 mod{143}所有解。(b) 求 x^2=77 mod{143}的所有解。

p = 143; 
    Solve[{x^2 == 133, Modulus == p}, 
      Mode -> Modular]

p = 143; 
    Solve[{x^2 == 77, Modulus == p}, 
      Mode -> Modular]

第七章電腦習題

page 174

7.2.1. 試求26055在質數模34807之下的平方根。

p = 34807; y = 26055; {PrimeQ[p], Mod[p, 4] == 3}

{x = PowerMod[y, (p + 1)/4, p], p - x}

PowerMod[x, 2, p] == y

Clear[x]; p = 34807; 
    Solve[{x^2 == 26055, Modulus == p}, 
      Mode -> Modular]

7.2.2. 試求70470720在模2333378389之下所有的平方根。

n = 2333378389; y = 70470720; 
    a = FactorInteger[n]
Mod[p = {a[[1]][[1]], a[[2]][[1]]}, 4] == {3, 
        3}

x = PowerMod[y, (p + 1)/4, p]

PowerMod[x, 2, p] == Mod[y, p]

w = {x[[1]], -x[[2]]};
<< NumberTheory`NumberTheoryFunctions`
ChineseRemainderTheorem[{x, -x}, p]
ChineseRemainderTheorem[{w, -w}, p]

7.2.3. 試利用第一節中的方法，求48382在質數模83987之下的平方根。將你所得到的答案平方後看看是否正確。請問你所得到的是那一個數的平方根？

p = 83987; y = 48382; {PrimeQ[p], Mod[p, 4] == 3}

x = PowerMod[y, (p + 1)/4, p]

PowerMod[{x, p - x}, 2, p]
{PowerMod[x, 2, p] == y, 
      PowerMod[x, 2, p] == p - y}