第八章一般習題

page 193

8.1.2. 解同餘方程式 2^x\equiv 14 mod{19}

p = 19; alp = 2; bet = 14; 
    L = Table[
        If[PowerMod[alp, k, p] == bet, 1, 0], {k, 
          p - 1}];
Position[L, Max[L]][[1]][[1]]

8.1.5. 解同餘方程式 3^x\equiv 2 mod{65537}                      (1-14)

ph[p_, alp_, bet_, q_, r_] := 
      Do[b[0] = bet; 
c[0] = 
          PowerMod[{alp, bet}, (p - 1)/q, p]; 
d[0] = 
          Table[If[
              PowerMod[c[0][[1]], k, p] == c[0][[2]], 
              1, 0], {k, 0, q - 1}]; 
x[
            0] = Position[d[0], Max[d[0]]][[1]][[1]] - 
            1; 
b[i_] := b[i] = 
            Mod[b[i - 1]*PowerMod[alp, -q^(i - 1)*x[i - 1], p], 
              p]; 
c[i_] := c[i] = 
            PowerMod[{alp, b[i]}, {(p - 1)/q, (p - 1)/q^(i + 1)}, 
              p]; 
d[i_] := d[i] = 
            Table[If[
                PowerMod[c[i][[1]], k, p] == c[i][[2]], 
                1, 0], {k, 0, q - 1}]; 
x[
            i_] := x[
              i] = Position[d[i], Max[d[i]]][[1]][[1]] - 
              1; 
Print["x=", 
          Sum[q^k*x[k], {k, 0, r - 1}], " mod ", q^r]]

<< NumberTheory`NumberTheoryFunctions`
p = 65537; alp = 3; bet = 2;
{PrimeQ[p], PrimitiveRoot[p], FactorInteger[p - 1]}

ph[p, alp, bet, 2, 16]

PowerMod[alp, 55296, p] == bet

Clear[b, c, d, x]

第八章電腦習題

page 194

8.2.1. 令 p=53047。證明 L_3(8576)=1234。

p = 53047; alp = 3; bet = 8576; x = 1234;
PowerMod[alp, x, p] == bet
Clear[x]

8.2.2. 令p=3989。(a) 證明L_2(3925)=2000與L_2(1046)=3000。
(b) 計算L_2(3925\cdot 1046)=1012。

p = 3989; alp = 2; bet1 = 3925; x1 = 2000; bet2 = 1046; 
    x2 = 3000;
PowerMod[alp, {x1, x2}, p] == {bet1, bet2}

p = 3989; alp = 2; bet1 = 3925; bet2 = 1046; 
    bet = Mod[bet1*bet2, p];
{PrimeQ[p], PrimitiveRoot[p], FactorInteger[p - 1]}

ph[p, alp, bet, 2, 2]
Clear[b, c, d, x]
ph[p, alp, bet, 997, 1]
Clear[b, c, d, x]

L = 
      ChineseRemainderTheorem[{0, 15}, {4, 997}]
PowerMod[alp, L, p] == bet

8.2.3. p=31 離散對數L_3(24)=13

p = 31; alp = 3; bet = 24;
L = 
        Table[If[PowerMod[alp, k, p] == bet, 1, 0], {k, 
            p - 1}];
Position[L, Max[L]][[1]][[1]]

8.2.4. 令 p=1201。利用波立格-黑爾曼法來算L_{11}(2)。

p = 1201; alp = 11; bet = 2;
{PrimeQ[p], PrimitiveRoot[p], FactorInteger[p - 1]}

ph[p, alp, bet, 2, 4]
Clear[b, c, d, x]
ph[p, alp, bet, 3, 1]
Clear[b, c, d, x]
ph[p, alp, bet, 5, 2]
Clear[b, c, d, x]

L = 
      ChineseRemainderTheorem[{12, 1, 7}, {16, 3, 
          25}]
PowerMod[alp, L, p] == bet