作者bugmens (2013新年快樂)
看板Math
標題Re: [其他] Elliptic Curve問題
時間Sat Jan 19 08:17:48 2013
※ 引述《initial1635 (AmazingTWman)》之銘言:
: 請問 給定 P(x, y)
: y^2=x^3+ax+b
: 當我在算Q=nP時
: n是一個大數 我用NAF的方式將大數拆開
: 然後用P=P或P=\=P的方式往上加
: 其中的計算過程中出現infinity 這個候該怎麼做?
: 拿infinity的值繼續往下算?
當你算到kP=∞時,會遇到在模n下沒有乘法反元素的錯誤
這時候答案不存在,我們只是借用∞這個符號來表示而已
不存在的答案你無法再計算(k+1)P,(k+2)P,(k+3)P...
例子可以看這裡(出自沈淵源,密碼學之旅與MATHEMATIC同行)
http://i.imgur.com/f3bAZBu.jpg
http://i.imgur.com/1e0ELC2.jpg
2 3
y =x +4x+4 (mod 2773)
取 P=(1,3)
計算2P=(1771,705)
計算3P時,1770在模2773下的乘法反元素不存在
所以無法計算出3P答案,於是就設3P=∞
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.164.219.183
推 initial1635 :那3P infinity的時候還有辦法算出4P嗎? 01/19 09:16
推 initial1635 :而且2773也不是prime 我想問的是假設我要算4P 01/19 09:19
→ initial1635 :但算到3P的時候infinity那4P還有辦法算出來嗎? 01/19 09:19
→ bugmens :算不出來,你自己可以從2P=(1771,705)去算4P 01/19 09:53
→ bugmens :一樣會遇到1410在模2773下無乘法反元素的錯誤 01/19 09:54
→ bugmens :所以3P,4P,5P,6P...都是不存在的 01/19 09:55