卒業研究

*
11.15 中村直子
目次
・修士論文の紹介
The ECM algorithm
・次回の予定
The ECM algorithm
INPUT: 𝑛, gcd 𝑛, 6 = 1, 𝑏𝑜𝑢𝑛𝑑𝑠 𝐵1 < 𝐵2 .
OUTPUT: 𝑎 𝑓𝑎𝑐𝑡𝑜𝑟 𝑝 𝑜𝑓 𝑛, 𝑜𝑟 𝐹𝐴𝐼𝐿.
[Choose curve]
𝑐ℎ𝑜𝑜𝑠𝑒 𝑝𝑎𝑟𝑎𝑚𝑒𝑡𝑒𝑟𝑠 𝑎, 𝑏 ∈(Z/nZ) defining the cur𝑣𝑒 𝐸𝑎,𝑏 (Z/nZ)
𝑎𝑛𝑑 𝑎 𝑝𝑜𝑖𝑛𝑡 𝑃0 = 𝑥0 , 𝑧0 ∈ 𝐸𝑎,𝑏 ;
• [Stage 1]
𝑐𝑜𝑚𝑝𝑢𝑡𝑒
𝑞(log 𝐵1)(log 𝑞) 𝑃0 ∈ 𝐸𝑎,𝑏
𝑅 = 𝑥1 , 𝑧1 ≔
𝑞≤𝐵1
𝑖𝑓 1 < 𝑔 = gcd 𝑧𝑞 , 𝑛 < 𝑛 𝑡ℎ𝑒𝑛 𝑟𝑒𝑡𝑢𝑟𝑛 𝑝 = 𝑔;
• [Stage 2]
𝐹𝑜𝑟 𝑒𝑎𝑐ℎ 𝑝𝑟𝑖𝑚𝑒 𝑞, 𝐵1 < 𝑞 < 𝐵2 , 𝑐𝑜𝑚𝑝𝑢𝑡𝑒
𝑥𝑞 , 𝑧𝑞 = 𝑞𝑅 ∈ 𝐸𝑎,𝑏 ;
𝑖𝑓 1 < 𝑔 = gcd 𝑧𝑞 , 𝑛 < 𝑛 𝑡ℎ𝑒𝑛 𝑟𝑒𝑡𝑢𝑟𝑛 𝑝 = 𝑔;
𝐶ℎ𝑜𝑜𝑠𝑒 𝑐𝑢𝑟𝑣𝑒 のところでジャニスさんはMontgomery’s curveを使っている。
その主な理由として4つ挙げている。
・曲線のパラメータが簡単に得ることができ曲線の生成にかかる計算時間も無視
できるほどであるため。
・与えられたパラメータに対して, 𝔽𝑝 に関わることなく初期値𝑃0 = 𝑥0 , 𝑧0 が求め
られる。また、 Montgomery’s curveの採用によって𝑦座標がなくなることもあり、こ
れはとても大きな利点である。
・与えられた𝑎, 𝑏, #𝐸𝑎,𝑏 𝔽𝑝 は素数冪で割ることができるかもしれない。
・曲線𝐸𝑎,𝑏 のパラメータ族はそれぞれ異なっている。
この条件はそれぞれの曲線の起点が異なることから充たされる。
次回の予定
・修士論文をもとにSuyama curve and Bernstein
curveについて調べる。
・ジャニスさんの論文で採用している
Montgomery’s curveについて調べる。

Download Report