14 12

# 用Maxima學密碼學－橢圓曲線

## 用Maxima學密碼學－橢圓曲線

https://math.pro/db/attachment.p ... 04&t=1565140250

y^2=x^3+ax+b (mod p)
y^2=x^3+16x+10 (mod 23)的橢圓曲線

(%i1)　[p,a,b]:[23,16,10];
(%o1)　$$\left[ 23,16,10 \right]$$

(%i2)
([lambda,num,denom,inv_denom,x3,y3],
if P=Q then
(print("λ=(3*",x_1^2,"+a)/(2*",y_1,")=",
"(3*",P[1],"^2+",a,")/(2*",P[2],")=",
lambda: (3*P[1]^2+a)/(2*Q[2]))
)
else if P[1]=Q[1] and P[2]#Q[2] then
(print(" P,Q兩點x座標相同,相加結果為無窮遠點"),
return([inf,inf])
)
else
(print("λ=(",y_2,"-",y_1,")/(",x_2,"-",x_1,")=",
"(",Q[2],"-",P[2],")/(",Q[1],"-",P[1],")=",
lambda: (P[2]-Q[2])/(P[1]-Q[1]))
),
num:num(lambda),/*分子*/
denom:denom(lambda),/*分母*/
print(1/denom,"=",inv_denom:inv_mod(denom,p),"(mod",p,")"),
print("λ=",lambda,"=",num,"*",inv_denom,"=",lambda:mod(num*inv_denom,p),"(mod",p,")"),
print(x_3,"=",λ^2,"-",x_1,"-",x_2,"=",lambda^2,"-",P[1],"-",Q[1],"=",
x3:lambda^2-P[1]-Q[1],"=",x3:mod(x3,p),"(mod",p,")"),
print(y_3,"=",λ,"(",x_1,"-",x_3,")-",y_1,"=",lambda,"(",P[1],"-",x3,")-",P[2],"=",
y3:lambda*(P[1]-x3)-P[2],"=",y3:mod(y3,p),"(mod",p,")"),
print("[",x_3,",",y_3,"]=",[x3,y3]),
return([x3,y3])
)$P=(x1,y1)=(18,14) Q=(x2,y2)=(5,10) (%i4) P:[18,14]; Q:[5,10]; (P) $$\left[18,14\right]$$ (Q) $$\left[5,14\right]$$ 計算P+Q=R=(x3,y3) (%i5) PointAdd(P,Q); $$\displaystyle \lambda=(y_2-y_1)/(x_2-x_1)=(10-14)/(5-18)=\frac{4}{13}$$ $$\displaystyle \frac{1}{13}=16\pmod{23}$$ $$\displaystyle \lambda=\frac{4}{13}=4 \cdot 16=18\pmod{23}$$ $$x_3=\lambda^2-x_1-x_2=324-18-5=301=2\pmod{23}$$ $$y_3=\lambda(x_1-x_3)-y_1=18(18-2)-14=274=21\pmod{23}$$ $$\left[x_3,y_3\right]=\left[2,21\right]$$ (%o5) $$\left[2,21\right]$$ 計算P+P=2P=R=(x3,y3) (%i6) PointAdd(P,P); $$\displaystyle \lambda=(3*x_1^2+a)/(2*y_1)=(3*18^2+16)/(2*14)=\frac{247}{7}$$ $$\displaystyle \frac{1}{7}=10\pmod{23}$$ $$\displaystyle \lambda=\frac{247}{7}=247 \cdot 10=9\pmod{23}$$ $$x_3=\lambda^2-x_1-x_2=81-18-18=45=22\pmod{23}$$ $$y_3=\lambda(x_1-x_3)-y_1=9(18-22)-14=-50=19\pmod{23}$$ $$\left[x_3,y_3\right]=\left[22,19\right]$$ (%o6) $$\left[22,19 \right]$$ TOP 例子1：有限體$$F_{23}$$之下，點$$P=(0,1)$$是橢圓曲線$$E$$：$$y^2=x^3+12x+1$$的生成數。  P=(0, 1) 2P = (13, 13) 3P = (5, 5) 4P = (3, 15) 5P = (6, 17) 6P = (19, 2) 7P = (17, 9) 8P = (18, 0) 9P = (17, 14) 10P = (19, 21) 11P = (6, 6) 12P = (3, 8) 13P = (5, 18) 14P = (13, 10) 15P = (0, 22) y^2=x^3+ax+b (mod p) y^2=x^3+12x+1 (mod 23)的橢圓曲線 (%i1) [p,a,b]:[23,12,1]; (%o1) $$\left[ 23,12,1 \right]$$ 橢圓曲線點相加 (%i2) PointAdd(P,Q):=block ([lambda,num,denom,inv_denom,x3,y3], if P=Q then (lambda: (3*P[1]^2+a)/(2*Q[2]) ) else if P[1]=Q[1] and P[2]#Q[2] then (print(" P,Q兩點x座標相同,相加結果為無窮遠點"), return([inf,inf]) ) else (lambda: (P[2]-Q[2])/(P[1]-Q[1]) ), lambda:num(lambda)*inv_mod(denom(lambda),p), x3:mod(lambda^2-P[1]-Q[1],p), y3:mod(lambda*(P[1]-x3)-P[2],p), return([x3,y3]) )$

(%i3)　P:[0,1];
(P)　$$\left[0,1 \right]$$

(%i6)
L:[P]$for k:2 thru 15 do (L:append(L,[PointAdd(last(L),P)]) )$
L;

(%o6)　$$[[0,1],[13,13],[5,5],[3,15],[6,17],[19,2],[17,9],[18,0],[17,14],[19,21],[6,6],[3,8],[5,18],[13,10],[0,22]]$$

P,2P,...,15P位置再加上標籤
(%i7)　Label:create_list(append([concat(i,"P")],(L[ i ]+[1,0])),i,1,length(L));
(Label)　$$\matrix{[[1P,1,1],[2P,14,13],[3P,6,5],[4P,4,15],[5P,7,17],[6P,20,2],[7P,18,9],[8P,19,0],\cr [9P,18,14],[10P,20,21],[11P,7,6],[12P,4,8],[13P,6,18],[14P,14,10],[15P,1,22]]}$$

(%i8)
draw2d(user_preamble="set size square; set grid; set xtics 1; set ytics 1;",
grid=true,
point_type=filled_circle,
points(L),
apply(label,Label));

(%o8)　$$[gr2d(points,label)]$$

TOP

 bugmens 發短消息 加為好友 當前離線 3# 大 中 小 發表於 2019-9-1 17:59  顯示全部帖子 前面兩篇文章利用$$maxima$$程式示範橢圓曲線加法($$P+Q$$)和兩倍($$P+P$$)的運算過程，以及藉由$$\pmod{p}$$將橢圓曲線上的每個點全部打散，讓橢圓曲線離散對數問題($$ECDLP$$)變得難以計算。 其實$$maxima$$已有內建的橢圓曲線程式庫，本篇文章將前面兩篇重新用內建橢圓曲線指令計算。 要先載入elliptic_curves.mac才能呼叫ec_set_curve,ec_point_p,ec_add (%i1)　load("elliptic_curves.mac"); (%o1)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac y^2=x^3+ax+b (mod p) y^2=x^3+16x+10 (mod 23)的橢圓曲線 (%i3) [p,a,b] : [23,16,10]; ec_set_curve(p,a,b); (%o2)　$$[23,16,10]$$ (%o3)　$$true$$ P,Q兩點座標 (%i5) P:[18,14]; Q:[5,10]; (P)　$$[18,14]$$ (Q)　$$[5,10]$$ 檢查P,Q有沒有在橢圓曲線上 (%i7) ec_point_p(P); ec_point_p(Q); (%o6)　$$true$$ (%o7)　$$true$$ 計算P+Q (%i8)　ec_add(P,Q); (%o8)　$$[2,21]$$ 計算P+P (%i9)　ec_add(P,P); (%o9)　$$[22,19]$$ －－－－－－－－－－－－－－－－－－－－－－ 要先載入elliptic_curves.mac才能呼叫ec_set_curve,ec_mult (%i1)　load("elliptic_curves.mac"); (%o1)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac y^2=x^3+ax+b (mod p) y^2=x^3+12x+1 (mod 23)的橢圓曲線 (%i3) [p,a,b]:[23,12,1]; ec_set_curve(p,a,b); (%o2)　$$[23,12,1]$$ (%o3)　$$true$$ 生成數P=[0,1] (%i4)　P:[0,1]; (P)　$$[0,1]$$ 用ec_mult(k,P)計算P,2P,3P,...,15P，結果放在L (%i5)　L:makelist(ec_mult(k,P),k,1,15); (L)　$$[[0,1],[13,13],[5,5],[3,15],[6,17],[19,2],[17,9],[18,0],[17,14],[19,21],[6,6],[3,8],[5,18],[13,10],[0,22]]$$ P,2P,...,15P位置再加上標籤 (%i6)　Label:create_list(append([concat(i,"P")],(L[ i ]+[1,0])),i,1,length(L)); (Label)　$$\matrix{[[1P,1,1],[2P,14,13],[3P,6,5],[4P,4,15],[5P,7,17],[6P,20,2],[7P,18,9],[8P,19,0],\cr [9P,18,14],[10P,20,21],[11P,7,6],[12P,4,8],[13P,6,18],[14P,14,10],[15P,1,22]]}$$ 將P,2P,...,15P各點坐標畫出來 (%i7) draw2d(user_preamble="set size square; set grid; set xtics 1; set ytics 1;",               grid=true,               point_type=filled_circle,               points(L),               apply(label,Label)); (%o7)　$$[gr2d(points,label)]$$ UID210 帖子909 閱讀權限200 在線時間4995 小時 註冊時間2008-12-16 最後登錄2020-6-5  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 4# 大 中 小 發表於 2019-9-7 19:39  顯示全部帖子 上一篇文章以$$y^2=x^3+12x+1 \pmod{23}$$，$$P=[0,1]$$為生成數計算$$1P,2P,\ldots,15P$$，再加上無窮遠點總共16個點。 想要知道有限體上橢圓曲線的點個數，直觀的方法是將$$x=0,1,\ldots,p-1$$代入橢圓曲線方程式$$y^2=x^3+ax+b \pmod{p}$$，以$$jacobi$$符號判斷同餘方程式是否有$$y$$的解，將有$$y$$的解個數加起來就是答案。 關於$$jacobi$$符號請看$$wiki$$介紹 https://zh.wikipedia.org/wiki/%E ... 4%E7%AC%A6%E5%8F%B7 但橢圓曲線點個數計算不需要將各個$$(x,y)$$點坐標算出來，是利用$$jacobi$$符號判斷是否為二次剩餘。 #$$\displaystyle E(F_{p})=p+1+\sum_{x=0}^{p-1} \left(\frac{x^3+ax+b}{p}\right)$$，其中#$$E(F_p)$$為橢圓曲線點個數，$$\displaystyle \left( \frac{}{}\right)$$為$$jacobi$$符號 但這個方法很沒效率，更有效率的方法請看$$wiki$$介紹。 https://en.wikipedia.org/wiki/Counting_points_on_elliptic_curves 另外#$$E(F_p)=p+1-t$$，$$t$$定義為$$Frobenius$$ $$trace$$，elliptic_curves.mac套件中指令為ec_trace() 要先載入elliptic_curves.mac才能呼叫ec_set_curve和ec_trace指令 (%i1)　load("elliptic_curves.mac"); (%o1)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac 要先載入gf.mac才能呼叫msqrt指令(計算二次剩餘的根) (%i2)　load("gf.mac"); (%o2)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/gf/gf.mac y^2=x^3+ax+b (mod p) y^2=x^3+12x+1 (mod 23)的橢圓曲線 (%i4) [p,a,b]:[23,12,1]; ec_set_curve(p,a,b); (%o3)　$$[23,12,1]$$ (%o4)　true 以x=0,1,...,p-1計算橢圓曲線點個數 (%i5) EllipticCurveOrder(p,a,b):=block ([count:0,yy,JacobiSymobl], for x:0 thru p-1 do   (print("當x=",x,"時,y"^2,"=",x,""^3,"+",a,"*",x,"+",b,"=",             yy:x^3+a*x+b,"=",yy:mod(yy,p),"(mod ",p,")"),    JacobiSymbol:jacobi(yy,p),/*判斷y^2=yy(mod p)是否有解*/    if JacobiSymbol=0 then/*yy整除p時,有一解*/      (count:count+1,       print("(x,y)=(",x,",",0,")")      )    else if JacobiSymbol=1 then/*用msqrt()計算兩解的值*/       (count:count+2,         Msqrt:msqrt(yy,p),         print("(x,y)=(",x,",",Msqrt[1],"),(",x,",",Msqrt[2],")")        )    else if JacobiSymbol=-1 then       (print("無解"))   ), return(count+1)/*無窮遠點也算進來再+1*/ )$計算橢圓曲線點個數 (%i6) EllipticCurveOrder(p,a,b); 當$$x=0$$時,$$y^2=0^3+12*0+1=1=1\pmod{23}$$ $$(x,y)=(0,1),(0,22)$$ 當$$x=1$$時,$$y^2=1^3+12*1+1=14=14\pmod{23}$$ 無解 當$$x=2$$時,$$y^2=2^3+12*2+1=33=10\pmod{23}$$ 無解 當$$x=3$$時,$$y^2=3^3+12*3+1=64=18\pmod{23}$$ $$(x,y)=(3,15),(3,8)$$ 當$$x=4$$時,$$y^2=4^3+12*4+1=113=21\pmod{23}$$ 無解 當$$x=5$$時,$$y^2=5^3+12*5+1=186=2\pmod{23}$$ $$(x,y)=(5,5),(5,18)$$ 當$$x=6$$時,$$y^2=6^3+12*6+1=289=13\pmod{23}$$ $$(x,y)=(6,17),(6,6)$$ 當$$x=7$$時,$$y^2=7^3+12*7+1=428=14\pmod{23}$$ 無解 當$$x=8$$時,$$y^2=8^3+12*8+1=609=11\pmod{23}$$ 無解 當$$x=9$$時,$$y^2=9^3+12*9+1=838=10\pmod{23}$$ 無解 當$$x=10$$時,$$y^2=10^3+12*10+1=1121=17\pmod{23}$$ 無解 當$$x=11$$時,$$y^2=11^3+12*11+1=1464=15\pmod{23}$$ 無解 當$$x=12$$時,$$y^2=12^3+12*12+1=1873=10\pmod{23}$$ 無解 當$$x=13$$時,$$y^2=13^3+12*13+1=2354=8\pmod{23}$$ $$(x,y)=(13,13),(13,10)$$ 當$$x=14$$時,$$y^2=14^3+12*14+1=2913=15\pmod{23}$$ 無解 當$$x=15$$時,$$y^2=15^3+12*15+1=3556=14\pmod{23}$$ 無解 當$$x=16$$時,$$y^2=16^3+12*16+1=4289=11\pmod{23}$$ 無解 當$$x=17$$時,$$y^2=17^3+12*17+1=5118=12\pmod{23}$$ $$(x,y)=(17,14),(17,9)$$ 當$$x=18$$時,$$y^2=18^3+12*18+1=6049=0\pmod{23}$$ $$(x,y)=(18,0)$$ 當$$x=19$$時,$$y^2=19^3+12*19+1=7088=4\pmod{23}$$ $$(x,y)=(19,2),(19,21)$$ 當$$x=20$$時,$$y^2=20^3+12*20+1=8241=7\pmod{23}$$ 無解 當$$x=21$$時,$$y^2=21^3+12*21+1=9514=15\pmod{23}$$ 無解 當$$x=22$$時,$$y^2=22^3+12*22+1=10913=11\pmod{23}$$ 無解 (%o6) $$16$$ 改用jacobi符號計算橢圓曲線點個數 (%i7) JacobiList:create_list(jacobi(x^3+a*x+b,p),x,0,p-1); (JacobiList) $$\left[1,-1,-1,1,-1,1,1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,1,0,1,-1,-1,-1 \right]$$ jacobi結果全部相加 (%i8) apply("+",JacobiList); (%o8) $$-8$$ 橢圓曲線點個數 (%i9) p+1+%; (%o9) $$16$$ 利用ec_trace()指令直接得到trace值 (%i10) t:ec_trace(); (t) $$8$$ 橢圓曲線點個數 (%i11) p+1-t; (%o11) $$16$$ UID210 帖子909 閱讀權限200 在線時間4995 小時 註冊時間2008-12-16 最後登錄2020-6-5 查看詳細資料 TOP  bugmens 發短消息 加為好友 當前離線 5# 大 中 小 發表於 2019-9-21 10:08 顯示全部帖子 橢圓曲線加密的安全性倚賴橢圓曲線離散對數問題($$Elliptic$$ $$Curve$$ $$Discrete$$ $$Logarithm$$ $$Problem$$，$$ECDLP$$)的困難度上，橢圓曲線離散對數問題敘述如下： 令$$E$$為基於有限體$$F_p$$的橢圓曲線，$$P,Q$$為橢圓曲線上的點坐標($$P,Q \in E(F_p)$$)且$$Q=kP,k \in N$$，當$$p$$很大時，計算$$k$$值非常困難。 解決橢圓曲線離散對數問題的方法會在另一篇文章討論，這裡僅示範暴力搜尋法找出$$k$$值。 elliptic_curves.mac套件中解橢圓曲線離散對數問題的指令為k:ec_log(P,Q); 要先載入elliptic_curves.mac才能呼叫ec_set_curve,ec_add,ec_point_order,ec_log (%i1) load("elliptic_curves.mac"); (%o1) C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac y^2=x^3+ax+b (mod p) y^2=x^3+12x+1 (mod 23)的橢圓曲線 (%i3) [p,a,b]:[23,12,1]; ec_set_curve(p,a,b); (%o2) $$[23,12,1]$$ (%o3) ture 計算橢圓曲線點個數 (%i4) order:p+1-ec_trace(); (order) 16 生成數P=[0,1] (%i5) P:[0,1]; (P) $$[0,1]$$ 計算P的階數n，每個點坐標有不同的階數,但都是橢圓曲線點個數的因數 例如： P=[0,1],階數16,16P=無窮遠點 P=[13,13],階數8,8P=無窮遠點 P=[5,5],階數16,16P=無窮遠點 P=[3,15],階數4,4P=無窮遠點 (%i6) n:ec_point_order(P,order); (n) 16 (%i7) Q:[17,14]; (Q) $$[17,14]$$ 計算2P,3P,...,kP，看何時等於Q (%i9) kP: P$ for k:2 thru n do   (print(k," P=",kP:ec_add(P,kP)),    if kP=Q then       (return(k))   ); $$2P=[13,13]$$ $$3P=[5,5]$$ $$4P=[3,15]$$ $$5P=[6,17]$$ $$6P=[19,2]$$ $$7P=[17,9]$$ $$8P=[18,0]$$ $$9P=[17,14]$$ (%o9)　9 直接呼叫ec_log計算k (%i10)　k:ec_log(P,Q); (k)　9 UID210 帖子909 閱讀權限200 在線時間4995 小時 註冊時間2008-12-16 最後登錄2020-6-5  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 6# 大 中 小 發表於 2019-10-4 09:25  顯示全部帖子 關於maxima的Galois體指令可以參考以下pdf檔 C:\maxima-5.43.0\share\maxima\5.43.0\share\contrib\gf\gf_manual.pdf $$F[2]/(x^4+x+1)$$的Galois體 (%i1)　gf_set_data(2,4); (%o1)　Structure [GF-DATA] $$F[2]/(x^4+x+1)$$的Galois體相關訊息 (%i2)　gf_info(); characteristic = 2 reduction polynomial = x^4+x+1 primitive element = x nr of elements = 16 nr of units = 15 nr of primitive elements = 8 (%o2)　false $$F[2]/(x^4+x+1)$$不可約多項式為$$x^4+x+1$$，元素個數16個 (%i3)　[p,ReductionPoly,g,n,m]:gf_infolist(); (%o3)　$$[2,x^4+x+1,x,16,15]$$ $$F[2]/(x^4+x+1)$$各元素運算過程 (%i5) gpower:1$for i:1 thru n-1 do (printList:["g"^i,"=(",gpower,")*(",g,")=",gpower:expand(gpower*g)], for j:1 thru hipow(gpower,x) do (if coeff(gpower,x^j)>=2 then/*係數超過2，取2同餘*/ (printList:append(printList,["=",gpower:polymod(gpower,2)]), return() ) ), /*次方超過4次方，取x^4+x+1同餘*/ if hipow(gpower,x)>=hipow(ReductionPoly,x) then (printList:append(printList,["=",gpower:gf_exp(g,i)])), apply(print,printList) )$ $$g=(1)*(x)=x$$ $$g^2=(x)*(x)=x^2$$ $$g^3=(x^2)*(x)=x^3$$ $$g^4=(x^3)*(x)=x^4=x+1$$ $$g^5=(x+1)*(x)=x^2+x$$ $$g^6=(x^2+x)*(x)=x^3+x^2$$ $$g^7=(x^3+x^2)*(x)=x^4+x^3=x^3+x+1$$ $$g^8=(x^3+x+1)*(x)=x^4+x^2+x=x^2+1$$ $$g^9=(x^2+1)*(x)=x^3+x$$ $$g^{10}=(x^3+x)*(x)=x^4+x^2=x^2+x+1$$ $$g^{11}=(x^2+x+1)*(x)=x^3+x^2+x$$ $$g^{12}=(x^3+x^2+x)*(x)=x^4+x^3+x^2=x^3+x^2+x+1$$ $$g^{13}=(x^3+x^2+x+1)*(x)=x^4+x^3+x^2+x=x^3+x^2+1$$ $$g^{14}=(x^3+x^2+1)*(x)=x^4+x^3+x=x^3+1$$ $$g^{15}=(x^3+1)*(x)=x^4+x=1$$ 轉二進位副程式 (%i6) bits(n) := block ([l :""], while n # 0 do   (l : concat(mod(n, 2),l),    n : floor(n / 2)),    return(l)   )$16個元素的多項式、二進位、十進位表示法 (%i7) addrow(matrix(["次方","多項式","二進位","十進位"]), matrix(["g"^"0","0","0","0"]), genmatrix(lambda([i,j],base10:gf_p2n(gf_exp(g,i)), if j=1 then "g"^i else if j=2 then gf_exp(g,i) else if j=3 then bits(base10) else if j=4 then base10),n-1,4)); (%o7) $$\left[\matrix{次方&多項式&二進位&十進位\cr g^0&0&0&0\cr g&x&10&2\cr g^2&x^2&100&4\cr g^3&x^3&1000&8\cr g^4&x+1&11&3\cr g^5&x^2+x&110&6\cr g^6&x^3+x^2&1100&12\cr g^7&x^3+x+1&1011&11\cr g^8&x^2+1&101&5\cr g^9&x^3+x&1010&10\cr g^{10}&x^2+x+1&111&7\cr g^{11}&x^3+x^2+x&1110&14\cr g^{12}&x^3+x^2+x+1&1111&15\cr g^{13}&x^3+x^2+1&1101&13\cr g^{14}&x^3+1&1001&9\cr g^{15}&1&1&1}\right]$$ 兩元素a,b (%i9) a:x^3+x; b:x^3+x^2+1; (a) $$x^3+x$$ (b) $$x^3+x^2+1$$ 相加 (%i10) print("g"^gf_index(a),"+g"^gf_index(b),"=(",a,")+(",b,")=",a+b,"=",add:polymod(a+b,2),"=g"^gf_index(add))$ $$g^9+g^{13}=(x^3+x)+(x^3+x^2+1)=2x^3+x^2+x+1=x^2+x+1=g^{10}$$ 相加指令為gf_add() (%i11)　gf_add(a,b); (%o11)　$$x^2+x+1$$ 相減 (%i12)　print("g"^gf_index(a),"-g"^gf_index(b),"=(",a,")-(",b,")=",a-b,"=",sub:polymod(a-b,2),"=g"^gf_index(sub))$$$g^9-g^{13}=(x^3+x)-(x^3+x^2+1)=-x^2+x-1=x^2+x+1=g^{10}$$ 相減指令為gf_sub() (%i13) gf_sub(a,b); (%o13) $$x^2+x+1$$ 相乘 (%i14) print("g"^gf_index(a),"*g"^gf_index(b),"=(",a,")*(",b,")=",expand(a*b),"=", mult:polymod(remainder(a*b,ReductionPoly),2),"=g"^gf_index(mult))$ $$g^9*g^{13}=(x^3+x)*(x^3+x^2+1)=x^6+x^5+x^4+2x^3+x=x^3+x+1=g^7$$ 相乘指令為gf_mult() (%i15)　gf_mult(a,b); (%o15)　$$x^3+x+1$$ 反元素 (%i16)　print("1/g"^gf_index(b),"=",1/b,"=",inv_b:gf_inv(b),"=g"^gf_index(inv_b))$$$\displaystyle 1/g^{13}=\frac{1}{x^3+x^2+1}=x^2=g^2$$ 反元素指令為gf_inv() (%i17) gf_inv(b); (%o17) $$x^2$$ 相除 (%i18) print("g"^gf_index(a),"/g"^gf_index(b),"=",a/b,"=(",a,")*(",inv_b:gf_inv(b),")=", expand(a*inv_b),"=",div:polymod(remainder(a*inv_b,ReductionPoly),2),"=g"^gf_index(div))$ $$\displaystyle g^9/g^{13}=\frac{x^3+x}{x^3+x^2+1}=(x^3+x)*(x^2)=x^5+x^3=x^3+x^2+x=g^{11}$$ 相除指令為gf_div() (%i19)　gf_div(a,b); (%o19)　$$x^3+x^2+x$$ UID210 帖子909 閱讀權限200 在線時間4995 小時 註冊時間2008-12-16 最後登錄2020-6-5  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 7# 大 中 小 發表於 2019-10-11 12:44  顯示全部帖子 二元橢圓曲線加密請見連結介紹，本文僅就例4、例5以$$maxima$$示範計算過程。 https://math.pro/db/attachment.p ... 04&t=1565140250 ※橢圓曲線在$$F_{2^n}$$下的運算規則 例子4：在有限體$$F_{2^4}$$之下，取橢圓曲線$$y^2+xy=x^3+g^8x^2+g^2$$上的兩點$$P=(g^3,g^9)$$及$$Q=(g,g^5)$$，其中$$g=(0010)$$為$$F_{2^4}$$的生成數，且不可約多項式為$$f(x)=x^4+x+1$$。若$$P+Q=R=(x_3,y_3)$$，則$$R=$$? 例子5：承例子4，若$$P+P=2P=R=(x_3,y_3)$$，則$$R=$$? F[2]/(x^4+x+1) 的Galois體 (%i1)　gf_set_data(2,4); (%o1)　Structure [GF-DATA] F[2]/(x^4+x+1) 不可約多項式為x^4+x+1，元素個數16個 (%i2)　[p,ReductionPoly,g,n,m]:gf_infolist(); (%o2)　$$\left[2,x^4+x+1,x,16,15 \right]$$ 產生g^1,g^2,...,g^15 (%i3)　g:create_list(gf_exp(g,i),i,1,n-1); (g)　$$\left[x,x^2,x^3,x+1,x^2+x,x^3+x^2,x^3+x+1,x^2+1,x^3+x,x^2+x+1,x^3+x^2+x,x^3+x^2+x+1,x^3+x^2+1,x^3+1,1\right]$$ y^2+xy=x^3+ax^2+b (mod 2)(mod x^4+x+1)的橢圓曲線 (%i5) a:g[8]; b:g[2]; (a)　$$x^2+1$$ (b)　$$x^2$$ 分式的分子和分母係數超過2以(mod 2)化簡 (%i6) PolyMod2(poly,PrintList):=block ([numpoly:num(poly),denompoly:denom(poly),numpolymod2,denompolymod2], numpolymod2:polymod(numpoly,2),/*分子多項式對2同餘*/ denompolymod2:polymod(denompoly,2),/*分母多項式對2同餘*/ if denompoly=1 then/*分母為1,是多項式*/     (if numpoly#numpolymod2 then         (PrintList:append(PrintList,["=",poly:numpolymod2]))     ) else     (if numpoly#numpolymod2 or denompoly#denompolymod2 then        (PrintList:append(PrintList,["=",poly:numpolymod2/denompolymod2]))     ), return([poly,PrintList]) )$分式的分子和分母超過4次方以(mod x^4+x+1)化簡 (%i7) PolyModGF(poly,PrintList):=block ([numpoly:num(poly),denompoly:denom(poly),numpolymodGF,denompolymodGF], numpolymodGF:polymod(remainder(numpoly,ReductionPoly),2),/*分子多項式對x^4+x+1同餘*/ denompolymodGF:polymod(remainder(denompoly,ReductionPoly),2),/*分母多項式對x^4+x+1同餘*/ if denompoly=1 then/*分母為1,是多項式*/ (if numpoly#numpolymodGF then (PrintList:append(PrintList,["=",poly:numpolymodGF])) ) else/*分母不為1是分式,針對分子和分母分開對x^4+x+1同餘*/ (if numpoly#numpolymodGF or denompoly#denompolymodGF then (PrintList:append(PrintList,["=",poly:numpolymodGF/denompolymodGF])) ), return([poly,PrintList]) )$ 針對分式的分母求反元素 (%i8) Inverse(poly,PrintList):=block ([numpoly:num(poly),denompoly:denom(poly)], if denompoly#1 then/*分母不為1才需要計算反元素*/   (PrintList:append(PrintList,["=(",numpoly,")(",gf_inv(denompoly),")"]),    PrintList:append(PrintList,["=",poly:expand(numpoly*gf_inv(denompoly))]),    [poly,PrintList]:PolyMod2(poly,PrintList),    [poly,PrintList]:PolyModGF(poly,PrintList)   ), return([poly,PrintList]) )$橢圓曲線點相加 注意： 多項式係數超過2以(mod 2)化簡 超過4次方以(mod x^4+x+1)化簡 (%i9) PointAdd(P,Q):=block ([R:[0,0],lambda,inv_P1,PrintList], if P=[inf,inf] then (return(Q)) else if Q=[inf,inf] then (return(P)) else if P=Q then (if P[1]=0 then (print(" P,Q兩點x座標為0,相加結果為無窮遠點"), return([inf,inf]) ), /*計算λ=(P1^2+P2)/P1*/ PrintList:["λ=",(x_1^2+y_1)/x_1,"=",lambda:(P[1]^2+P[2])/P[1]], if P[1]^2#expand(P[1]^2) then/*若P[1]超過1項,將平方展開過程列出來*/ (PrintList:append(PrintList,["=",lambda:expand(P[1]^2+P[2])/P[1]])), [lambda,PrintList]:PolyMod2(lambda,PrintList),/*若係數大於2,同餘2*/ [lambda,PrintList]:PolyModGF(lambda,PrintList),/*若超過4次方,同餘x^4+x+1*/ [lambda,PrintList]:Inverse(lambda,PrintList),/*若λ為分式,將分母取反元素後和分子相乘*/ apply(print,PrintList),/*將λ計算過程印出來*/ /*計算R1=λ^2+λ+a*/ print(x_3,"=λ"^2,"+λ+a=(",lambda,")"^2,"+(",lambda,")+(",a,")"), PrintList:[x_3,"=(",expand(lambda^2),")+",lambda+a, "=",R[1]:expand(lambda^2)+lambda+a], [R[1],PrintList]:PolyMod2(R[1],PrintList),/*若係數大於2,同餘2*/ [R[1],PrintList]:PolyModGF(R[1],PrintList),/*若超過4次方,同餘x^4+x+1*/ apply(print,PrintList),/*將R1計算過程印出來*/ /*計算R2=P1^2+λR1+R1*/ print(y_3,"=",x_1^2,"+λ",x_3,"+",x_3,"=(",P[1],")"^2,"+(",lambda,")(",R[1],")+(",R[1],")"), PrintList:[y_3,"=(",expand(P[1]^2),")+(",expand(lambda*R[1]),")+",R[1], "=",R[2]:expand(P[1]^2+lambda*R[1])+R[1]], [R[2],PrintList]:PolyMod2(R[2],PrintList),/*若係數大於2,同餘2*/ [R[2],PrintList]:PolyModGF(R[2],PrintList),/*若超過4次方,同餘x^4+x+1*/ apply(print,PrintList)/*將R2計算過程印出來*/ ) else (if gf_add(P[1],Q[1])=0 then (print(" P,Q兩點x座標相同,相加結果為無窮遠點"), return([inf,inf]) ), /*計算λ=(P2+Q2)/(P1+Q1)*/ PrintList:["λ=",(y_1+y_2)/(x_1+x_2),"=",lambda:(P[2]+Q[2])/(P[1]+Q[1])], [lambda,PrintList]:PolyMod2(lambda,PrintList),/*若係數大於2,同餘2*/ [lambda,PrintList]:PolyModGF(lambda,PrintList),/*若超過4次方,同餘x^4+x+1*/ [lambda,PrintList]:Inverse(lambda,PrintList),/*若λ為分式,將分母取反元素後和分子相乘*/ apply(print,PrintList),/*將λ計算過程印出來*/ /*計算R1=λ^2+λ+P1+Q1+a*/ print(x_3,"=λ"^2,"+λ+",x_1,"+",x_2,"+a=(",lambda,")"^2,"+(",lambda,")+(",P[1],")+(",Q[1],")+(",a,")"), PrintList:[x_3,"=(",expand(lambda^2),")+",lambda+P[1]+Q[1]+a, "=",R[1]:expand(lambda^2)+lambda+P[1]+Q[1]+a], [R[1],PrintList]:PolyMod2(R[1],PrintList),/*若係數大於2,同餘2*/ [R[1],PrintList]:PolyModGF(R[1],PrintList),/*若超過4次方,同餘x^4+x+1*/ apply(print,PrintList),/*將R1計算過程印出來*/ /*計算R2=λ(P1+R1)+R1+P2*/ print(y_3,"=λ(",x_1,"+",x_3,")+",x_3,"+",y_1,"=(",lambda,")(",P[1]+R[1],")+(",R[1],")+(",P[2],")"), PrintList:[y_3,"=(",expand(lambda*(P[1]+R[1])),")+",R[1]+P[2], "=",R[2]:expand(lambda*(P[1]+R[1]))+R[1]+P[2]], [R[2],PrintList]:PolyMod2(R[2],PrintList),/*若係數大於2,同餘2*/ [R[2],PrintList]:PolyModGF(R[2],PrintList),/*若超過4次方,同餘x^4+x+1*/ apply(print,PrintList)/*將R2計算過程印出來*/ ), print("(",x_3,",",y_3,")=(",R[1],",",R[2],")=(",if R[1]=0 then 0 else "g"^gf_index(R[1]),",", if R[2]=0 then 0 else "g"^gf_index(R[2]),")"), return(R) )$ P=(x1,y1)=(g^3,g^9) Q=(x2,y2)=(g^1,g^5) (%i11) P:[g[3],g[9]]; Q:[g[1],g[5]]; (P)　$$\left[x^3,x^3+x \right]$$ (Q)　$$\left[x,x^2+x \right]$$ 計算P+Q=R=(x3,y3) (%i12)　R:PointAdd(P,Q); $$\displaystyle \lambda=\frac{y_2+y_1}{x_2+x_1}=\frac{x^3+x^2+2x}{x^3+x}=\frac{x^3+x^2}{x^3+x}=(x^3+x^2)(x^3+x^2)=x^6+2x^5+x^4=x^6+x^4=x^3+x^2+x+1$$ $$x_3=\lambda^2+\lambda+x_1+x_2+a=(x^3+x^2+x+1)^2+(x^3+x^2+x+1)+(x^3)+(x)+(x^2+1)$$ $$x_3=(x^6+2x^5+3x^4+4x^3+3x^2+2x+1)+2x^3+2x^2+2x+2=x^6+2x^5+3x^4+6x^3+5x^2+4x+3=x^6+x^4+x^2+1=x^3+x$$ $$y_3=\lambda(x_1+x_3)+x_3+y_1=(x^3+x^2+x+1)(2x^3+x)+(x^3+x)+(x^3+x)$$ $$y_3=(2x^6+2x^5+3x^4+3x^3+x^2+x)+2x^3+2x=2x^6+2x^5+3x^4+5x^3+x^2+3x=x^4+x^3+x^2+x=x^3+x^2+1$$ $$(x_3,y_3)=(x^3+x,x^3+x^2+1)=(g^9,g^{13})$$ (R)　$$\left[x^3+x,x^3+x^2+1 \right]$$ 計算P+P=2P=R=(x3,y3) (%i13)　R:PointAdd(P,P); $$\displaystyle λ=\frac{y_1+x_1^2}{x_1}=\frac{x^6+x^3+x}{x^3}=\frac{x^2+x}{x^3}=(x^2+x)(x^3+x^2+x+1)=x^5+2x^4+2x^3+2x^2+x=x^5+x=x^2$$ $$x_3=λ^2+λ+a=(x^2)^2+(x^2)+(x^2+1)$$ $$x_3=(x^4)+2x^2+1=x^4+2x^2+1=x^4+1=x$$ $$y_3=x_1^2+λx_3+x_3=(x^3)^2+(x^2)(x)+(x)$$ $$y_3=(x^6)+(x^3)+x=x^6+x^3+x=x^2+x$$ $$(x_3,y_3)=(x,x^2+x)=(g,g^5)$$ (R)　$$\left[x,x^2+x \right]$$ UID210 帖子909 閱讀權限200 在線時間4995 小時 註冊時間2008-12-16 最後登錄2020-6-5  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 8# 大 中 小 發表於 2020-1-29 07:17  顯示全部帖子 在$$F[2]/(x^4+x+1)$$Galois體之下，點$$P=(g^3,g^9)=(x^3,x^3+x)$$是橢圓曲線$$E$$：$$y^2+xy=x^3+g^8x^2+g^2$$的生成數。 $$1P=(g^3,g^9)=(x^3,x^3+x)$$ $$2P=(g^1,g^5)=(x,x^2+x)$$ $$3P=(g^9,g^{13})=(x^3+x,x^3+x^2+1)$$ $$4P=(g^8,g^2)=(x^2+1,x^2)$$ $$5P=(g^7,g^8)=(x^3+x+1,x^2+1)$$ $$6P=(1,0)=(1,0)$$ $$7P=(g^{13},g^{12})=(x^3+x^2+1,x^3+x^2+x+1)$$ $$8P=(0,g^1)=(0,x)$$ $$9P=(g^{13},g^1)=(x^3+x^2+1,x)$$ $$10P=(1,1)=(1,1)$$ $$11P=(g^7,g^{11})=(x^3+x+1,x^3+x^2+x)$$ $$12P=(g^8,1)=(x^2+1,1)$$ $$13P=(g^9,g^{10})=(x^3+x,x^2+x+1)$$ $$14P=(g^1,g^2)=(x,x^2)$$ $$15P=(g^3,g^1)=(x^3,x)$$ $$F[2]/(x^4+x+1)$$的Galois體 (%i1)　gf_set_data(2,4); (%o1)　Structure [GF-DATA] $$F[2]/(x^4+x+1)$$不可約多項式為$$x^4+x+1$$，元素個數16個 (%i2)　[p,ReductionPoly,g,n,m]:gf_infolist(); (%o2)　$$[2,x^4+x+1,x,16,15]$$ 產生$$g^1,g^2,\ldots,g^{15}$$ (%i3)　g:create_list(gf_exp(g,i),i,1,n-1); (g)　$$[x,x^2,x^3,x+1,x^2+x,x^3+x^2,x^3+x+1,x^2+1,x^3+x,x^2+x+1,x^3+x^2+x,x^3+x^2+x+1,x^3+x^2+1,x^3+1,1]$$ $$y^2+xy=x^3+ax^2+b \pmod{2}\pmod{x^4+x+1}$$的橢圓曲線 (%i5) a:g[8]; b:g[2]; (a)　$$x^2+1$$ (b)　$$x^2$$ 橢圓曲線點相加 (%i6) PointAdd(P,Q):=block ([R:[0,0],lambda], if P=[inf,inf] then (return(Q)) else if Q=[inf,inf] then (return(P)) else if P=Q then   (if P[1]=0 then      (print(" P,Q兩點x座標為0,相加結果為無窮遠點"),        return([inf,inf])      ),   lambda:gf_add(P[1],gf_div(P[2],P[1])),   R[1]:gf_add(gf_add(gf_add(gf_mult(lambda,lambda)),lambda),a),   R[2]:gf_add(gf_add(gf_mult(P[1],P[1]),gf_mult(lambda,R[1])),R[1])   ) else   (if gf_add(P[1],Q[1])=0 then       (print(" P,Q兩點x座標相同,相加結果為無窮遠點"),        return([inf,inf])       ),    lambda:gf_div(gf_add(P[2],Q[2]),gf_add(P[1],Q[1])),    R[1]:gf_add(gf_add(gf_add(gf_add(gf_mult(lambda,lambda),lambda),P[1]),Q[1]),a),    R[2]:gf_add(gf_add(gf_mult(lambda,gf_add(P[1],R[1])),R[1]),P[2])   ), return(R) )$生成數$$P=(g^3,g^9)$$ (%i7) P:[g[3],g[9]]; (P) $$[x^3,x^3+x]$$ 計算$$P,2P,3P,\ldots,15P$$，結果放在$$L$$ (%i10) L:[P]$ for k:2 thru 15 do   (L:append(L,[PointAdd(last(L),P)])   )\$ L; (%o10)　$$\matrix{[[x^3,x^3+x],[x,x^2+x],[x^3+x,x^3+x^2+1],[x^2+1,x^2],[x^3+x+1,x^2+1],[1,0],[x^3+x^2+1,x^3+x^2+x+1], \cr [0,x],[x^3+x^2+1,x],[1,1],[x^3+x+1,x^3+x^2+x],[x^2+1,1],[x^3+x,x^2+x+1],[x,x^2],[x^3,x]]}$$ $$P,2P,\ldots,15P$$轉換成g次方坐標 (%i11)　Position:create_list(append([gf_index(L[ i ][1]),gf_index(L[ i ][2])]),i,1,length(L)); (Position)　$$[[3,9],[1,5],[9,13],[8,2],[7,8],[0,false],[13,12],[false,1],[13,1],[0,0],[7,11],[8,0],[9,10],[1,2],[3,1]]$$ gf_index(0)回傳false,以-1替換 (%i12)　Position:subst(-1,false,Position); (Position)　$$[[3,9],[1,5],[9,13],[8,2],[7,8],[0,-1],[13,12],[-1,1],[13,1],[0,0],[7,11],[8,0],[9,10],[1,2],[3,1]]$$ $$P,2P,\ldots,15P$$位置再加上標籤 (%i13)　Label:create_list(append([concat(i,"P")],(Position[ i ]+[1,0])),i,1,length(Position)); (Label)　$$\matrix{[[1P,4,9],[2P,2,5],[3P,10,13],[4P,9,2],[5P,8,8],[6P,1,-1],[7P,14,12],[8P,0,1],\cr [9P,14,1],[10P,1,0],[11P,8,11],[12P,9,0],[13P,10,10],[14P,2,2],[15P,4,1]]}$$ 將$$P,2P,\dots,15P$$各點坐標畫出來 (%i14) draw2d(user_preamble="set size square; set grid;                                set xtics ('0' -1,'1' 0,'g^1' 1,'g^2' 2,'g^3' 3,'g^4' 4,'g^5' 5,'g^6' 6,'g^7' 7,'g^8' 8,'g^9' 9,'g^{10}' 10,'g^{11}' 11,'g^{12}' 12,'g^{13}' 13,'g^{14}' 14);                                set ytics ('0' -1,'1' 0,'g^1' 1,'g^2' 2,'g^3' 3,'g^4' 4,'g^5' 5,'g^6' 6,'g^7' 7,'g^8' 8,'g^9' 9,'g^{10}' 10,'g^{11}' 11,'g^{12}' 12,'g^{13}' 13,'g^{14}' 14);",               grid=true,               point_type=filled_circle,               points(Position),               apply(label,Label)); (%o14)　[gr2d(points,label)] UID210 帖子909 閱讀權限200 在線時間4995 小時 註冊時間2008-12-16 最後登錄2020-6-5  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 9# 大 中 小 發表於 2020-2-9 22:16  顯示全部帖子 要先載入elliptic_curves.mac才能呼叫ec2_set_curve,ec2_add (%i1)　load("elliptic_curves.mac"); (%o1)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac $$y^2+xy=x^3+ax^2+b\pmod{2}\pmod{x^4+x+1}$$的橢圓曲線 $$a=g^8=x^2+1=101_2=5_{10}$$，$$b=g^2=x^2=100_2=4_{10}$$ (%i3) [ReductionPoly,a,b]:[x^4+x+1,5,4]; ec2_set_curve(ReductionPoly,a,b); (%o2)　$$[x^4+x+1,5,4]$$ (%o3)　true $$4P=[g^8,g^2]=[x^2+1,x^2]=[101_2,100_2]=[5_{10},4_{10}]$$ 正確答案應為$$8P=4P+4P=[0,g^1]=[0,x]=[0_2,10_2]=[0_{10},2_{10}]$$ 卻得到錯誤答案$$[0,5]$$ (%i4)　ec2_add([5,4],[5,4]); (%o4)　$$[0,5]$$ －－－－－－－－－－－－－－－－－－－－－ $$8P=4P+4P=[0,x]=[0_2,10_2]=[0_{10},2_{10}]$$計算過程為 $$\displaystyle \lambda= \frac{y_1+x_1^2}{x_1}= \frac{(x^2+1)^2+x^2}{x^2+1}=\frac{x^4+3x^2+1}{x^2+1}=\frac{x^4+x^2+1}{x^2+1}=\frac{x^2+x}{x^2+1}=( x^2+x )( x^3+x+1 ) = x^5+x^4+x^3+2x^2+x = x^5+x^4+x^3+x = x^3+x^2+x+1$$ $$x_3 =\lambda^2 +\lambda+a=( x^3+x^2+x+1 )^2 +( x^3+x^2+x+1 )+( x^2+1 )$$ $$x_3 =( x^6+2x^5+3x^4+4x^3+3x^2+2x+1 )+ x^3+2x^2+x+2 = x^6+2x^5+3x^4+5x^3+5x^2+3x+3 = x^6+x^4+x^3+x^2+x+1 = 0$$ $$y_3 = x_1^2 +\lambda x_3 + x_3 =( x^2+1 )^2 +( x^3+x^2+x+1 )( 0 )+( 0 )$$ $$y_3 =( x^4+2x^2+1 )+( 0 )+ 0 = x^4+2x^2+1 = x^4+1 = x$$ $$( x_3 , y_3 )=( 0 , x )=( 0 , g )$$ －－－－－－－－－－－－－－－－－－－－－ 開啟ec2_add副程式原始碼 檔案路徑C:\maxima-5.43.0\share\maxima\5.43.0\share\contrib\elliptic_curves\ec2.lisp (defun ec2-add (pt qt)   (cond     ((null pt) qt)     ((null qt) pt)     ((equal pt qt) (ec2-double pt))因為pt和qt相等，由ec2-double副程式計算     ((equal pt (ec2-neg qt)) nil)     (t (let* ((*f2-red* *ec2-red*)               (xp (car pt))               (yp (cadr pt))               (xq (car qt))               (yq (cadr qt))               (xpq (logxor xp xq))               (m (f2-times (logxor yp yq) (f2-inv xpq)))               (xx (logxor (f2-times m m) m xpq *ec2-a*))               (yy (logxor (f2-times m (logxor xp xx)) xx yp)) )         (list xx yy) )))) ;; (defun ec2-double (pt)   (cond     ((null pt) nil)     ((= 0 (car pt)) nil)     (t (let* ((*f2-red* *ec2-red*)               (x (car pt))               (y (cadr pt))               (x2 (f2-times x x))               (xi (f2-inv x))               (xx (logxor x2 (f2-times *ec2-b* (f2-times xi xi))))$$\displaystyle xx=x^2+\frac{b}{x^2}=x^2+b\cdot xi^2=0_2=0_{10}$$               (tt (logxor x (f2-times y xi)))$$\displaystyle tt=x+\frac{y}{x}=x+y\cdot xi=1111_2=15_{10}$$               (yy (logxor x2 (f2-times tt xx) xx)) )但計算$$tt\cdot xx=15_{10} \cdot 0_{10}=7_{10}$$不為0         (list xx yy) )))) －－－－－－－－－－－－－－－－－－－－－ 開啟f2-times副程式原始碼 檔案路徑在C:\maxima-5.43.0\share\maxima\5.43.0\src\numth.lisp (defun f2-times (a b)   (declare (optimize (speed 3) (safety 0)))   (if (zerop b) (return-from f2-times 0))多加這行，當$$b=0$$時直接回傳0   (let* ((ilen (integer-length b))          (a1 (ash a (1- ilen)))          (ab a1) )     (do ((i (- ilen 2) (1- i)) (k 0))         ((< i 0) (f2-red ab))         (declare (fixnum i k))       (decf k)       (when (logbitp i b)         (setq a1 (ash a1 k)               ab (logxor ab a1)               k 0 ))))) －－－－－－－－－－－－－－－－－－－－－ 重新執行範例程式 要先載入elliptic_curves.mac才能呼叫ec2_set_curve,ec2_add (%i1)　load("elliptic_curves.mac"); (%o1)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac 讓更正的程式碼能重新載入 (%i2)　load("numth.lisp"); (%o2)　C:/maxima-5.43.0/share/maxima/5.43.0/src/numth.lisp $$y^2+xy=x^3+ax^2+b\pmod{2}\pmod{x^4+x+1}$$的橢圓曲線 $$a=g^8=x^2+1=101_2=5_{10}$$，$$b=g^2=x^2=100_2=4_{10}$$ (%i4) [ReductionPoly,a,b]:[x^4+x+1,5,4]; ec2_set_curve(ReductionPoly,a,b); (%o3)　$$[x^4+x+1,5,4]$$ (%o4)　true $$4P=[g^8,g^2]=[x^2+1,x^2]=[101_2,100_2]=[5_{10},4_{10}]$$ 得到正確答案$$8P=4P+4P=[0,g^1]=[0,x]=[0_2,10_2]=[0_{10},2_{10}]$$ (%i5)　ec2_add([5,4],[5,4]); (%o5)　$$[0,2]$$ －－－－－－－－－－－－－－－－－－－－－ 結論：將numth.lisp取代原本的檔案C:\maxima-5.43.0\share\maxima\5.43.0\src\numth.lisp UID210 帖子909 閱讀權限200 在線時間4995 小時 註冊時間2008-12-16 最後登錄2020-6-5  查看詳細資料 TOP
 bugmens 發短消息 加為好友 當前離線 10# 大 中 小 發表於 2020-2-10 20:55  顯示全部帖子 以$$maxima$$內建程式庫計算橢圓曲線加法($$P+Q$$)、兩倍($$P+P=2P$$)、畫出$$1P,2P,\ldots,15P$$散佈圖。 要注意的是$$maxima$$程式庫以十進位表示有限體$$F_{2^n}$$元素，以下列出有限體$$F_{2^4}$$各元素。 $$\left[\matrix{次方&多項式&二進位&十進位\cr g^0&0&0&0\cr g&x&10&2\cr g^2&x^2&100&4\cr g^3&x^3&1000&8\cr g^4&x+1&11&3\cr g^5&x^2+x&110&6\cr g^6&x^3+x^2&1100&12\cr g^7&x^3+x+1&1011&11\cr g^8&x^2+1&101&5\cr g^9&x^3+x&1010&10\cr g^{10}&x^2+x+1&111&7\cr g^{11}&x^3+x^2+x&1110&14\cr g^{12}&x^3+x^2+x+1&1111&15\cr g^{13}&x^3+x^2+1&1101&13\cr g^{14}&x^3+1&1001&9\cr g^{15}&1&1&1}\right]$$ ※橢圓曲線在$$F_{2^n}$$下的運算規則 例子4：在有限體$$F_{2^4}$$之下，取橢圓曲線$$y^2+xy=x^3+g^8x^2+g^2$$上的兩點$$P=(g^3,g^9)$$及$$Q=(g,g^5)$$，其中$$g=(0010)$$為$$F_{2^4}$$的生成數，且不可約多項式為$$f(x)=x^4+x+1$$。若$$P+Q=R=(x_3,y_3)$$，則$$R=$$? 例子5：承例子4，若$$P+P=2P=R=(x_3,y_3)$$，則$$R=$$? 要先載入elliptic_curves.mac才能呼叫ec2_set_curve,ec2_point_p,ec2_add (%i1)　load("elliptic_curves.mac"); (%o1)　C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac 將numth.lisp取代原本的檔案C:\maxima-5.43.0\share\maxima\5.43.0\src\numth.lisp 讓更正的程式碼能重新載入 (%i2)　load("numth.lisp"); (%o2)　C:/maxima-5.43.0/share/maxima/5.43.0/src/numth.lisp $$y^2+xy=x^3+ax^2+b\pmod{2}\pmod{x^4+x+1}$$的橢圓曲線 $$a=g^8=x^2+1=101_2=5_{10}$$，$$b=g^2=x^2=100_2=4_{10}$$ (%i4) [ReductionPoly,a,b]:[x^4+x+1,5,4]; ec2_set_curve(ReductionPoly,a,b); (%o3)　$$[x^4+x+1,5,4]$$ (%o4)　true P,Q兩點座標 $$P=[g^3,g^9]=[x^3,x^3+x]=[1000_2,1010_2]=[8_{10},10_{10}]$$ $$Q=[g^1,g^5]=[x,x^2+x]=[10_2,110_2]=[2_{10},6_{10}]$$ (%i6) P:[8,10]; Q:[2,6]; (P)　$$[8,10]$$ (Q)　$$[2,6]$$ 檢查$$P,Q$$有沒有在橢圓曲線上 (%i8) ec2_point_p(P); ec2_point_p(Q); (%o7)　true (%o8)　true 計算$$P+Q$$ $$P+Q=[x^3+x,x^3+x^2+1]=[1010_2,1101_2]=[10_{10},13_{10}]$$ (%i9)　ec2_add(P,Q); (%o9)　$$[10,13]$$ 計算$$P+P=2P$$ $$P+P=2P=[x,x^2+x]=[10_2,110_2]=[2_{10},6_{10}]$$ (%i10)　ec2_add(P,P); (%o10)　$$[2,6]$$ －－－－－－－－－－－－－－－－－－－－－－ 在$$F[2]/(x^4+x+1)$$Galois體之下，點$$P=(g^3,g^9)=(x^3,x^3+x)$$是橢圓曲線$$E$$：$$y^2+xy=x^3+g^8x^2+g^2$$的生成數。 $$1P=(g^3,g^9)=(x^3,x^3+x)=(1000_2,1010_2)=(8_{10},10_{10})$$ $$2P=(g^1,g^5)=(x,x^2+x)=(10_2,110_2)=(2_{10},6_{10})$$ $$3P=(g^9,g^{13})=(x^3+x,x^3+x^2+1)=(1010_2,1101_2)=(10_{10},13_{10})$$ $$4P=(g^8,g^2)=(x^2+1,x^2)=(101_2,100_2)=(5_{10},4_{10})$$ $$5P=(g^7,g^8)=(x^3+x+1,x^2+1)=(1011_2,101_2)=(11_{10},5_{10})$$ $$6P=(1,0)=(1,0)=(1_2,0_2)=(1_{10},0_{10})$$ $$7P=(g^{13},g^{12})=(x^3+x^2+1,x^3+x^2+x+1)=(1101_2,1111_2)=(13_{10},15_{10})$$ $$8P=(0,g^1)=(0,x)=(0_2,10_2)=(0_{10},2_{10})$$ $$9P=(g^{13},g^1)=(x^3+x^2+1,x)=(1101_2,10_2)=(13_{10},2_{10})$$ $$10P=(1,1)=(1,1)=(1_2,1_2)=(1_{10},1_{10})$$ $$11P=(g^7,g^{11})=(x^3+x+1,x^3+x^2+x)=(1011_2,1110_2)=(11_{10},14_{10})$$ $$12P=(g^8,1)=(x^2+1,1)=(101_2,1_2)=(5_{10},1_{10})$$ $$13P=(g^9,g^{10})=(x^3+x,x^2+x+1)=(1010_2,111_2)=(10_{10},7_{10})$$ $$14P=(g^1,g^2)=(x,x^2)=(10_2,100_2)=(2_{10},4_{10})$$ $$15P=(g^3,g^1)=(x^3,x)=(1000_2,10_2)=(8_{10},2_{10})$$ 要先載入elliptic_curves.mac才能呼叫ec2_set_curve,ec2_mult (%i1)　load("elliptic_curves.mac"); (%o1)　"C:/maxima-5.43.0/share/maxima/5.43.0/share/contrib/elliptic_curves/elliptic_curves.mac" 將numth.lisp取代原本的檔案C:\maxima-5.43.0\share\maxima\5.43.0\src\numth.lisp 讓更正的程式碼能重新載入 (%i2)　load("numth.lisp"); (%o2)　C:/maxima-5.43.0/share/maxima/5.43.0/src/numth.lisp $$F[2](x^4+x+1)$$的Galois體 (%i3)　gf_set_data(2,4); (%o3)　Structure [GF-DATA] $$y^2+xy=x^3+ax^2+b\pmod{2}\pmod{x^4+x+1}$$的橢圓曲線 $$a=g^8=x^2+1=101_2=5_{10}$$，$$b=g^2=x^2=100_2=4_{10}$$ (%i5) [ReductionPoly,a,b]:[x^4+x+1,5,4]; ec2_set_curve(ReductionPoly,a,b); (%o4)　$$[x^4+x+1,5,4]$$ (%o5)　true $$P=[g^3,g^9]=[x^3,x^3+x]=[1000_2,1010_2]=[8_{10},10_{10}]$$ (%i6)　P:[8,10]; (P)　$$[8,10]$$ 用ec2_mult(k,P)計算$$P,2P,3P,\ldots,15P$$，結果放在L (%i7)　L:makelist(ec2_mult(k,P),k,1,15); (L)　$$[[8,10],[2,6],[10,13],[5,4],[11,5],[1,0],[13,15],[0,2],[13,2],[1,1],[11,14],[5,1],[10,7],[2,4],[8,2]]$$ )$$P,2P,\ldots,15P$$轉換成g次方坐標 (%i8)　Position:create_list(append([gf_index(gf_n2p(L[ i ][1])),gf_index(gf_n2p(L[ i ][2]))]),i,1,length(L)); (Position)　$$[[3,9],[1,5],[9,13],[8,2],[7,8],[0,false],[13,12],[false,1],[13,1],[0,0],[7,11],[8,0],[9,10],[1,2],[3,1]]$$ gf_index(0)回傳false,以-1替換 (%i9)　Position:subst(-1,false,Position); (Position)　 $$P,2P,\ldots,15P$$位置再加上標籤 (%i10)　Label:create_list(append([concat(i,"P")],(Position[ i ]+[1,0])),i,1,length(Position)); (Label)　$$\matrix{[[1P,4,9],[2P,2,5],[3P,10,13],[4P,9,2],[5P,8,8],[6P,1,-1],[7P,14,12],[8P,0,1],\cr [9P,14,1],[10P,1,0],[11P,8,11],[12P,9,0],[13P,10,10],[14P,2,2],[15P,4,1]]}$$ (%i12) draw2d(user_preamble="set size square; set grid;                                set xtics ('0' -1,'1' 0,'g^1' 1,'g^2' 2,'g^3' 3,'g^4' 4,'g^5' 5,'g^6' 6,'g^7' 7,'g^8' 8,'g^9' 9,'g^{10}' 10,'g^{11}' 11,'g^{12}' 12,'g^{13}' 13,'g^{14}' 14);                                set ytics ('0' -1,'1' 0,'g^1' 1,'g^2' 2,'g^3' 3,'g^4' 4,'g^5' 5,'g^6' 6,'g^7' 7,'g^8' 8,'g^9' 9,'g^{10}' 10,'g^{11}' 11,'g^{12}' 12,'g^{13}' 13,'g^{14}' 14);",               grid=true,               point_type=filled_circle,               points(Position),               apply(label,Label)); (%o12)　[gr2d(points,label)] UID210 帖子909 閱讀權限200 在線時間4995 小時 註冊時間2008-12-16 最後登錄2020-6-5  查看詳細資料 TOP
14 12
﻿