模 n 下的橢圓曲線的加法運算ecadd,ecmus,ecmlt

ecadd[p1_, p2_, a_, b_, n_] := 
        Module[{z, m, x3, y3, p3}, z = 0; z1 = 1; 
          If[p1 == {"infinity", "infinity"}, p3 = p2; 
            z = 1, " "]; 
If[z == 1, " ", 
            If[p2 == {"infinity", "infinity"}, p3 = p1; 
              z = 1, " "]]; 
If[z == 1, " ", 
            If[p1[[1]] == p2[[1]] && 
                p1[[2]] == p2[[2]] == 0, 
              p3 = {"infinity", "infinity"}; 
              z = 1, " "]]; 
If[z == 1, " ", 
            If[p1[[1]] == p2[[1]] && 
                p1[[2]] ≠ p2[[2]], 
              p3 = {"infinity", "infinity"}; 
              z = 1, " "]]; 
If[z == 1, " ", 
            If[p1 == p2 && GCD[p1[[2]], n] ≠ 1 && 
                GCD[p1[[2]], n] ≠ n, z = 1; 
              z1 = GCD[p1[[2]], n], " "]]; 
If[
            z == 1, " ", 
            If[p1 == p2, 
              m = Mod[(3*p1[[1]]^2 + a)*
                    PowerMod[2*p1[[2]], -1, n], 
                  n]; 
z = 1; 
              x3 = m^2 - p1[[1]] - p2[[1]]; 
y3 = 
                m*(p1[[1]] - x3) - p1[[2]]; 
              p3 = Mod[{x3, y3}, n], " "]]; 
If[
            z == 1, " ", 
            If[GCD[p2[[1]] - p1[[1]], n] ≠ 1, 
              z = 1; 
z1 = 
                GCD[p2[[1]] - p1[[1]], 
                  n], " "]]; 
If[z == 1, " ", 
            m = Mod[(p2[[2]] - p1[[2]])*
                  PowerMod[p2[[1]] - p1[[1]], -1, n], 
                n]; 
x3 = m^2 - p1[[1]] - p2[[1]]; 
            y3 = m*(p1[[1]] - x3) - 
                p1[[2]]; 
p3 = Mod[{x3, y3}, n]]; 
          If[z1 == 1, p3, {"factor=", z1}]];
ecmus[p1_, m_, a_, b_, n_] := 
      Module[{z}, 
        z = {p1}; 
For[i = 1, 
          i < m && z[[Length[
                      z]]][[1]] ≠ "factor=", i++, 
          z = Append[z, ecadd[p1, z[[Length[z]]], a, b, n]]]; 
        z]
ecmlt[p1_, m_, a_, b_, n_] := Last[ecmus[p1, m, a, b, n]]

第十章一般習題

page 233

10.1.2. (a) 列出橢圓曲線 E: (y^2)=(x^3)-2 mod 7 上所有的點。
(b) 求橢圓曲線 E 上之和 (3,2)+(6,5)。
(c) 求橢圓曲線 E 上之和 (3,2)+(3,2)。

Table[
        Solve[{y^2 == x^3 - 2, Modulus == 7}, 
          Mode -> Modular], {x, 0, 6}] // ColumnForm

ecadd[{3, 2}, {6, 5}, 0, -2, 7]

{ecadd[{3, 2}, {3, 2}, 0, -2, 7], 
      ecmlt[{3, 2}, 2, 0, -2, 7]}

10.1.3. 假設你要用橢圓曲線的方法來分解一個合成數 n。你從曲線 (y^2)=(x^3)-4x mod n 及其上的一點 (2,0) 開始。為什麼這無法得到 n 的分解式？

n = 711; ecmlt[{2, 0}, 2, -4, 0, n]

第十章電腦習題

page 234

10.2.1. 令 E 為橢圓曲線 (y^2)=(x^3)+2x+3 mod 19。 (a) 求和 (1,5)+(9, 3), (b) 求和 (9,3) + (9,-3), (c) 利用上面(b)部分的結果，求差 (1,5)-(9, 3)。(d) 求一整數 k 使得 k(1,5)=(9, 3)。
(e) 證明 (1,5) 剛剛好擁有20個相異的倍數(包含 ∞)。(f) 利用上面(e)的結果及一般習題 5, 證明 E 上之點的個數是 20 的倍數。用 Hasse 定理證明 E 上之點的個數剛剛好就是 20。

ecadd[{1, 5}, {9, 3}, 2, 3, 19]

ecadd[{9, 3}, {9, -3}, 2, 3, 19]

ecadd[{1, 5}, {9, -3}, 2, 3, 19]

L = 
        Table[If[ecmlt[{1, 5}, k, 2, 3, 19] == {9, 3}, 1, 0], {k, 
            10}];
Position[L, Max[L]][[1]][[1]]

ecmlt[{1, 5}, 5, 2, 3, 19] == {9, 3}

ecmus[{1, 5}, 20, 2, 3, 19]

M = 
        Table[If[Abs[20*k - 19 - 1] < 2*Sqrt[19], 1, 0], {k, 
            10}];
Position[M, Max[M]][[1]][[1]]

10.2.2. 你要將信息 12345 表示成橢圓曲線 (y^2)=(x^3)+7x+11 mod 593899 上的點 (x,y)。將 x 寫成 x=12345_ 並求出 x 的最後一個位數使得橢圓曲線上有一點的橫座標為 x。

p = 593899; K = 10; m = 12345;

Table[
        Solve[{y^2 == (m*K + j)^3 + 7 (m*K + j) + 11, 
            Modulus == p}, y, Mode -> Modular], {j, 0, 
          K - 1}] //  ColumnForm

y = 170809; x = m*K + 1
Mod[(m*K + 1)^3 + 7 (m*K + 1) + 11, p] == 
      PowerMod[y, 2, p]

10.2.3. 用橢圓曲線的方法，藉選取一隨機的橢圓曲線及其上隨機的一點來分解 n=11413

n = 11413;
ecmlt[{1, 1}, 32, 3, -3, n]

ecmlt[{1, 2}, 32, 17, -14, n]

10.2.4. (a) 利用橢圓曲線來分解 3900353。(b) 試試第三章的 p-1 法來分解 3900353。

n = 3900353;
FactorInteger[n - 1]

ecmlt[{1, 1}, 12!, 1, -1, n]

a = 259; b[1] = a; 
    b[j_] := PowerMod[b[j - 1], j, n];
Table[GCD[b[j] - 1, n], {j, 1, 7}]

10.2.5. 令 P=(2,3) 為橢圓曲線 (y^2)=(x^3)-10x+21 mod 557。(a) 證明 189P=∞, 但 63P\ne ∞ 且 27P\ne ∞。(b) 利用一般習題 6, 證明點 P 的週期是 189。
(c) 利用一般習題 6, 及哈攝(Hasse)定理證明 E 上之點個數為 567。

ecmlt[{2, 3}, 189, -10, 21, 557]

ecmlt[{2, 3}, 189/3, -10, 21, 557]

ecmlt[{2, 3}, 189/7, -10, 21, 557]

M = 
        Table[If[Abs[189*k - 557 - 1] < 2*Sqrt[557], 1, 0], {k, 
            10}];
Position[M, Max[M]][[1]][[1]]