第八章        離散對數與公鑰密碼系統

pages 177 - 181

例題02 設p=2579, alp=2, a=765, 三毛傳信息x=1299給四郎。三毛選隨機數 k=882

p = 2579;  alp = 2;  a = 765; bet = PowerMod[alp, a, p]

x = 1299; SeedRandom[711]; 
    k = Random[Integer, {100, 999}]
z = PowerMod[{alp, bet}, k, p];
y = {z[[1]], Mod[x*z[[2]], p]}

Mod[y[[2]]*PowerMod[y[[1]], -a, p], p] == 
      x

例題04 用波立格-黑爾曼解 7^x=12 mod{41}

p = 41; alp = 7; bet = 12; FactorInteger[p - 1]

q = 2; r = 3; x = x0 + q*x1 + q^2*x2;
c0 = PowerMod[{alp, bet}, (p - 1)/q, p]

d0 = 
      Table[If[PowerMod[c0[[1]], k, p] == c0[[2]], 1, 0], {k, 
          0, q - 1}]

x0 = Position[d0, Max[d0]][[1]][[1]] - 1

bet1 = 
        Mod[bet*PowerMod[alp, -x0, p], p];
c1 = 
      PowerMod[{alp, bet1}, {(p - 1)/q, (p - 1)/q^2}, p]

d1 = 
      Table[If[PowerMod[c1[[1]], k, p] == c1[[2]], 1, 0], {k, 
          0, q - 1}]

x1 = Position[d1, Max[d1]][[1]][[1]] - 1

bet2 = 
        Mod[bet1*PowerMod[alp, -q*x1, p], 
          p];
c2 = 
      PowerMod[{alp, bet2}, {(p - 1)/q, (p - 1)/q^3}, p]

d2 = 
      Table[If[PowerMod[c2[[1]], k, p] == c2[[2]], 1, 0], {k, 
          0, q - 1}]

x2 = Position[d2, Max[d2]][[1]][[1]] - 1

Print["x=", x, " mod ", q^r]

Clear[x0, x1, x2]
q = 5; r = 1; x = x0; 
    c0 = PowerMod[{alp, bet}, (p - 1)/q, p]

d0 = 
      Table[If[PowerMod[c0[[1]], k, p] == c0[[2]], 1, 0], {k, 
          0, q - 1}]

x0 = Position[d0, Max[d0]][[1]][[1]] - 1

Print["x=", x, " mod ", q^r]

<< NumberTheory`NumberTheoryFunctions`
L = ChineseRemainderTheorem[{5, 3}, {8, 5}]

PowerMod[alp, L, p] == bet

Exit[]

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]]

ph[41, 7, 12, 2, 3]
Clear[b, c, d, x]

ph[41, 7, 12, 5, 1]
Clear[b, c, d, x]

例題04&用波立格-黑爾曼解 7^x\equiv 12 mod{41}

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]]

p = 41; alp = 7; bet = 12; FactorInteger[p - 1]

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

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

<< NumberTheory`NumberTheoryFunctions`
{L = ChineseRemainderTheorem[{5, 3}, {8, 5}], 
      PowerMod[alp, L, p] == bet}

ph[p,alp,bet,q,r]

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]]

例題05&用波立格-黑爾曼解 6^x\equiv 7531 mod{8101}

<< NumberTheory`NumberTheoryFunctions`
p = 8101; alp = 6; bet = 7531;
{PrimeQ[p], PrimitiveRoot[p], FactorInteger[p - 1]}

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

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

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

<< NumberTheory`NumberTheoryFunctions`
{L = ChineseRemainderTheorem[{1, 47, 14}, {4, 81, 25}], 
      PowerMod[alp, L, p] == bet}

例題06 用指數法解 7^x\equiv 12 mod{41}

p = 41; alp = 7; bet = 12; B = 10; Prime /@ Range[B/2]

Table[{k, FactorInteger[PowerMod[alp, k, p]]}, {k, 10}] // 
      ColumnForm

PolynomialMod[
      LinearSolve[{{0, 0, 0, 1}, {3, 0, 0, 0}, {0, 1, 1, 0}, {2, 0, 1, 
            0}}, {1, 2, 3, 6}], 40]

例題07 用指數法解 2^x\equiv 37 mod{131}

p = 131; alp = 2; bet = 37;
Table[{k, FactorInteger[PowerMod[alp, k, p]]}, {k, 8, 14}] // 
      ColumnForm

SeedRandom[512]
Random[Integer, {0, 50}]

Mod[bet*PowerMod[alp, %, p], p] // FactorInteger

{PowerMod[alp, 106, p] == bet, 
      PowerMod[alp, 41, p] == bet}

bet = 79; SeedRandom[48]
Random[Integer, {0, 50}]

Mod[bet*PowerMod[alp, 25, p], p] // FactorInteger