第七章        電話賭局

pages 161 - 173

例題01 試問5及2在模p=11之下的平方根為何？                          (1-7)

p = 11; y = {5, 2}; Mod[p, 4] == 3

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

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

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

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

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

例題02 試求26951623672在模p=98573007539之下的平方根。

p = 98573007539; {PrimeQ[p], Mod[p, 4] == 3}

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

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

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

例題03 試解同餘方程式 x^2\equiv 71 mod{77}。

p = {7, 11}; y = 71; 
    Mod[p, 4] == {3, 3}
x = PowerMod[y, (p + 1)/4, p]

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

Clear[x]; 
    Solve[{x^2 == y, Modulus == p[[1]]*p[[2]]}, 
      Mode -> Modular]

例題04 令n=34222273=9803x3491。求x^2=19101358 mod{34222273}的解。

p = {9803, 3491}; 
    y = 19101358; {PrimeQ[p], 
      Mod[p, 4] == {3, 3}}
x = PowerMod[y, (p + 1)/4, p]

w = {x[[1]], -x[[2]]};
ChineseRemainderTheorem[{x, -x}, p]
ChineseRemainderTheorem[{w, -w}, p]

Clear[x]; 
    Solve[{x^2 == y, Modulus == p[[1]]*p[[2]]}, 
      Mode -> Modular]

例題05 選兩被4除餘3質數 p=2038074743 , q=1190494759 相乘得n=2426317299991771937傳四郎。四郎選隨機 x=1414213562373095948 在模n之下算出其平方 y=x^2=740843181258626192 mod{n}。

p = 2038074743; q = 1190494759; n = p*q

x = 1414213562373095948; y = PowerMod[x, 2, n]

z = PowerMod[y, {(p + 1)/4, (q + 1)/4}, {p, q}]

w = {z[[1]], -z[[2]]};
{ChineseRemainderTheorem[z, {p, q}], 
      ChineseRemainderTheorem[-z, {p, q}], 
      ChineseRemainderTheorem[w, {p, q}], 
      ChineseRemainderTheorem[-w, {p, q}]}

GCD[%[[1]] - %[[3]], n]

{% == p, % == q}

例題06 考慮一簡化遊戲，只有五張牌為：Ten(10),Jack(J), Queen(Q), King(K), Ace(A)}而每一參賽者發一牌，點數最高者為嬴家。用 a=01, b=02,... 將牌轉化為數

abc = " abcdefghijklmnopqrstuvwxyz";
\(\(no = "000102030405060708091011121314151617181920212223242526";\)\)
digitalize = 
        Table[StringTake[abc, {i}] -> 
            StringTake[no, {2*i - 1, 2*i}], {i, 1, 27}];
alphabetize = 
        Table[StringTake[no, {2*i - 1, 2*i}] -> 
            StringTake[abc, {i}], {i, 1, 27}];
Q[plaintext_] := StringReplace[plaintext, digitalize];
Qd[plaintext_] := ToExpression[Q[plaintext]];
A[digit_] := StringReplace[digit, alphabetize];

c = {c10 = Qd["ten"], c11 = Qd["jack"], c12 = Qd["queen"], 
        c13 = Qd["king"], c14 = Qd["ace"]}

p = 2396271991; a = 1234567; b = 7654321;
{PrimeQ[p], GCD[{a, b}, p - 1]}
{a', b'} = PowerMod[{a, b}, -1, p - 1]

d = PowerMod[c, b, p]

RandomRelist[x_List] := 
      Block[{n = x, p}, 
        Do[p = Random[Integer, {1, i}]; 
          n[[{p, i}]] = n[[{i, p}]], {i, Length[x]}]; n]

SeedRandom[8]

d1 = d[[RandomRelist[Range[5]]]]

PowerMod[d1[[4]], a, p]

PowerMod[%, b', p]

PowerMod[%, a', p]

A[ToString[%]]

PowerMod[d1[[1]], b', p]

A[ToString[%]]

例題07 我們回到上面那個簡化的遊戲。在那兒所選的 p 不是隨機的。

PowerMod[c, (p - 1)/2, p]

{d1, PowerMod[d1, (p - 1)/2, p]}

PowerMod[d1[[2]], a, p]

PowerMod[%, b', p]

PowerMod[%, a', p]

A["0" <> ToString[%]]