一種計(jì)算橢圓曲線(xiàn)群的階的確定型多項(xiàng)式時(shí)間算法，確定型是因?yàn)樗惴▋?nèi)部沒(méi)有隨機(jī)選擇/概率拋幣操作，多項(xiàng)式時(shí)間是因?yàn)橛?em>k的乘法與求逆總次數(shù)是O((logq)^6)
（
q為
k的大小，乘法與求逆相對(duì)加減運(yùn)算顯著耗時(shí)）。具體原理及流程詳見(jiàn)參考文獻(xiàn)[1]中5.2節(jié)。這里給出筆者的一些思考
1. Hasse定理（Frobenius自同態(tài)方程式）在扭點(diǎn)群上的限制亦成立，這決定了t模l的一個(gè)同余方程成立，且在模l的最小非負(fù)剩余系下解是唯一的
2. 孫子定理保證了某取值范圍內(nèi)的一個(gè)t模L（L為各素因子l的乘積）的唯一解，即由t模L各個(gè)素因子l的同余方程構(gòu)成的同余方程組的解是唯一的
3. L必須大于t取值上限的2倍。這是為了算法求得的解滿(mǎn)足上述2（否則在更小的L內(nèi)得到的解不唯一，因L與t上限或下限間的某數(shù)可以與t模L同余）
4. 素因子l的選擇排除2與橢圓曲線(xiàn)特征p。這是因?yàn)樗惴?gòu)造所依賴(lài)的一個(gè)引理之前提條件：為奇素?cái)?shù)保證l次除子多項(xiàng)式屬于k[X]，即引理論斷有意義；
不等于p保證檢測(cè)一個(gè)多項(xiàng)式f是否零多項(xiàng)式的充要條件成立，即可以用l次除子多項(xiàng)式去整除f來(lái)判斷。另l為素?cái)?shù)保證了與其它除子多項(xiàng)式（及其冪次）互素
另外發(fā)現(xiàn)了算法的一處瑕疵，即第4步預(yù)計(jì)算除子多項(xiàng)式與Frobenius自同態(tài)的復(fù)合少了兩個(gè)值，這導(dǎo)致第5步可能崩潰，當(dāng)依賴(lài)的后續(xù)兩個(gè)復(fù)合多項(xiàng)式?jīng)]被計(jì)算時(shí)。
這個(gè)糾正可通過(guò)修改第4步擴(kuò)大2個(gè)值，或第5步通過(guò)除子多項(xiàng)式的遞推公式按需計(jì)算
扭點(diǎn)的階計(jì)算正確性根本
在密碼學(xué)中的應(yīng)用
選取原則
1. 排除超奇異橢圓曲線(xiàn)。這是為避免MOV等約化攻擊，約化攻擊時(shí)間復(fù)雜度是亞指數(shù)
2. 有限域的選擇要使E(Fq)的群階足夠大。這是為了緩解Shanks及Pollard ρ攻擊
3. E(Fq)存在階為大素?cái)?shù)的子群。這是為了抵抗Pohlig-Hellman攻擊
對(duì)于第1點(diǎn)，就排除了char(K)=2或3且j(E)=0對(duì)應(yīng)的如下標(biāo)準(zhǔn)形式曲線(xiàn)
Y2+α3Y=X3+α4X+α6（α3≠0） 與 Y2=X3+α4X+α6
一種典型方案
橢圓曲線(xiàn)及有限域的選擇使得|E(Fq)|=cm，且char(Fq) ∤ q+1-cm。其中m是一個(gè)大素?cái)?shù)（通常不低于256位二進(jìn)制長(zhǎng)度，提供中長(zhǎng)期安全性），c小于m。
m階子群的生成元可通過(guò)以下方法確定：隨機(jī)選擇E上的一個(gè)有理點(diǎn)P，如果Q=cP為零元（即無(wú)窮遠(yuǎn)點(diǎn)），則重復(fù)選擇，直到其不等于零元。
一旦找到了生成元，那么子群就可以構(gòu)造出來(lái)了。下面分析正確性
參考文獻(xiàn)
[1] 橢圓曲線(xiàn)及其在密碼學(xué)中的應(yīng)用—導(dǎo)引 Andreas Enge
[2] 算法數(shù)論 裴定一、祝躍飛
[3] The Arithmetic of Elliptic Curves Joseph H. Silverman
[4] 標(biāo)識(shí)密碼學(xué) 程朝輝
[5] 代數(shù)學(xué)基礎(chǔ)與有限域 林東岱
[6] 抽象代數(shù)I 趙春來(lái) 徐明曜
[7] 代數(shù)與數(shù)論 李超 周悅