[其他] 離散 橢圓曲線

看板Math作者 (登登)時間7年前 (2018/08/14 17:40), 編輯推噓6(6推 0噓 73→)
留言79則, 3人參與, 7年前最新討論串1/2 (看更多)
最近在認識比特幣時，了解到比特幣的公鑰,私鑰是利用數學的橢圓曲線來做加密。 過程會對特定的橢圓曲線取mod 來得到整數的座標點，變成離散數學。 想問的問題是"取mod 後的座標有辦法對映到原本連續的橢圓曲線上的點嗎？" 例如比特幣使用的曲線 y^2=x^3+7 在取mod 31時只會有20個座標點，加上"無窮遠"，階數就是21 而連續的橢圓曲線在選擇特定的點使得階數也是21時，也是有固定的20個座標點+"無窮遠 "(沒有其他可能的點使得階數也是21) 所以我覺得離散後的20個點應該可以對映到連續曲線上的20個點。 例如在我這例子裡，離散後的(0,10)、(0,21)可以對映到連續曲線上的(0,2.6458),(0,-2 .6458), 會容易得到這結論是因為N=21不是質數，所以在這些點，階數會變3，扣除"無窮 遠"後，就剩下這兩個點，所以我覺得這兩對是對映的關係,但不知道一對一是哪兩個點。 不知道有沒有相關分析來尋找離散跟連續間的對映關係？ google了很多相關網頁，沒找到任何相關分析，有看到"橢圓曲線的數學是屬於研究所的 課程"才來這邊發問，不知道有修習過的高手能分享嗎？或是有相關文獻可以推薦？ 還是說本來就不可能找到所有點在連續曲線上的對映關係？畢竟ECDSA是很多資安系統採 用的加密方式。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.94.110 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1534239613.A.E91.html
→
08/16 10:02, 7年前 , 1F
雖然我也對這個不太熟 但因為都沒人回 就來獻醜
08/16 10:02, 1F
→
08/16 10:03, 7年前 , 2F
橢圓曲線原本的是定義在R上的連續曲線
08/16 10:03, 2F
→
08/16 10:03, 7年前 , 3F
如果你想把它定義在Z上 考慮到y^2=f(x)=xxx+ax+b
08/16 10:03, 3F
→
08/16 10:07, 7年前 , 4F
並不是每個f(x)的值都是平方數
08/16 10:07, 4F
→
08/16 10:08, 7年前 , 5F
總之 直接定義在Z上會失敗 尤其是考慮到反元素定義
08/16 10:08, 5F
→
08/16 10:09, 7年前 , 6F
所以取而代之 我們把它定義在mod N上
08/16 10:09, 6F
→
08/16 10:09, 7年前 , 7F
然後可以證明他well defined 而且反元素也存在之類
08/16 10:09, 7F
→
08/16 10:12, 7年前 , 8F
假設直接把mod N的點搬到Z上 則無法定義反元素之類
08/16 10:12, 8F
→
08/16 10:12, 7年前 , 9F
大概就是這樣
08/16 10:12, 9F
→
08/16 10:13, 7年前 , 10F
PS:數學系的橢圓曲線不考慮mod N 只談積分性質
08/16 10:13, 10F
→
08/16 10:13, 7年前 , 11F
還有一些數論公式等等 應該不會是你想要的東西
08/16 10:13, 11F
→
08/16 12:36, 7年前 , 12F
謝謝回覆！有幾個問題想問
08/16 12:36, 12F
→
08/16 12:37, 7年前 , 13F
R是實數 Z是複數的意思嗎？
08/16 12:37, 13F
→
08/16 12:41, 7年前 , 14F
可能我哪裡理解錯誤，f(x)的值不都是實數嗎？那應
08/16 12:41, 14F
→
08/16 12:41, 7年前 , 15F
該都可以開平分根，就都是平方數，為什麼不能直接定
08/16 12:41, 15F
→
08/16 12:41, 7年前 , 16F
義在Z上？
08/16 12:41, 16F
→
08/16 12:43, 7年前 , 17F
還是你的意思是取完mod的f(x) 並不是所有值都能開
08/16 12:43, 17F
→
08/16 12:43, 7年前 , 18F
根號？
08/16 12:43, 18F
→
08/16 12:45, 7年前 , 19F
例如在我舉例的曲線中f(3)或f(6)的值就不能開根號，
08/16 12:45, 19F
→
08/16 12:45, 7年前 , 20F
不是平方數？
08/16 12:45, 20F
→
08/16 12:50, 7年前 , 21F
但有沒有可能 雖然不是所有的f(x)都能當平方數，但
08/16 12:50, 21F
→
08/16 12:50, 7年前 , 22F
一旦f(x1)能當平方數 就能在Z裡找到對映的值？ 在
08/16 12:50, 22F
→
08/16 12:50, 7年前 , 23F
我的例子裡就是 必須在連續曲線上先找到特定的點，
08/16 12:50, 23F
→
08/16 12:50, 7年前 , 24F
這些點使得階數為21，才能對映到mod 31下的點？
08/16 12:50, 24F
→
08/16 12:52, 7年前 , 25F
另外好奇一問，橢圓曲線的積分性質或其他數論分析，
08/16 12:52, 25F
→
08/16 12:52, 7年前 , 26F
有沒有可能在取mod N 後仍然成立！？
08/16 12:52, 26F
→
08/16 12:55, 7年前 , 27F
數學系不考慮mod N 來分析應該是正常的，偏偏取mod
08/16 12:55, 27F
→
08/16 12:55, 7年前 , 28F
N 是能用來加密的關鍵...總覺得很神奇，為何取完mo
08/16 12:55, 28F
→
08/16 12:55, 7年前 , 29F
d N, 定義的加法公式仍然成立...
08/16 12:55, 29F
推
08/16 13:22, 7年前 , 30F
Z 是整數, 不是複數喔
08/16 13:22, 30F
→
08/16 13:28, 7年前 , 31F
喔喔喔 謝謝告知
08/16 13:28, 31F
推
08/16 20:50, 7年前 , 32F
先不要管我那個平方的說法
08/16 20:50, 32F
→
08/16 20:51, 7年前 , 33F
如果有兩個整數點 連成直線交橢圓曲線於第三點
08/16 20:51, 33F
→
08/16 20:51, 7年前 , 34F
則該點對稱y軸後的點仍在曲線上 定義成兩點總和
08/16 20:51, 34F
→
08/16 20:51, 7年前 , 35F
如果你把橢圓曲線定義在整數上 辦不到以上這件事情
08/16 20:51, 35F
→
08/16 20:52, 7年前 , 36F
光是直線的斜率就不是整數 更別說和曲線交點要整數
08/16 20:52, 36F
→
08/16 20:52, 7年前 , 37F
但如果你取mod N 那麼不管是斜率還是交點都是整數
08/16 20:52, 37F
→
08/16 20:53, 7年前 , 38F
*更正 對稱x軸
08/16 20:53, 38F
推
08/16 20:59, 7年前 , 39F
然後橢圓曲線在R和ZmodN上可定義 是因為他們是體喔
08/16 20:59, 39F
→
08/16 20:59, 7年前 , 40F
反之 Z(整數)不是體 所以就不可以定義
08/16 20:59, 40F
→
08/16 21:00, 7年前 , 41F
這是抽象代數的內容
08/16 21:00, 41F
→
08/16 21:57, 7年前 , 42F
橢圓曲線能定義在R跟Z mod N 上是因為他們是體(我再
08/16 21:57, 42F
→
08/16 21:57, 7年前 , 43F
自行去了解 體 的定義) 所以我的問題應該要問 當曲
08/16 21:57, 43F
→
08/16 21:57, 7年前 , 44F
線定義在這兩個體且階數相同時，有辦法找出對映關係
08/16 21:57, 44F
→
08/16 21:57, 7年前 , 45F
嗎？
08/16 21:57, 45F
→
08/16 22:00, 7年前 , 46F
阿阿阿 不過在R這個體時，曲線上有連續的無限多個點
08/16 22:00, 46F
→
08/16 22:00, 7年前 , 47F
，但在Z mod N 上只會固定數量的點
08/16 22:00, 47F
→
08/16 22:06, 7年前 , 48F
曲線的"加法"能在R以及Z mod N 兩個體上都成立，是
08/16 22:06, 48F
→
08/16 22:06, 7年前 , 49F
不是表示也有可能有其他"運算"在這兩個體也成立，就
08/16 22:06, 49F
→
08/16 22:06, 7年前 , 50F
可能利用這"運算"找出對應的點？
08/16 22:06, 50F
→
08/16 22:09, 7年前 , 51F
抽象代數(第一次聽到...)有類似的數論嗎？嘗試在兩
08/16 22:09, 51F
→
08/16 22:09, 7年前 , 52F
個不同的體找出的對應的關係，或是認為無法有對應
08/16 22:09, 52F
→
08/16 22:09, 7年前 , 53F
關係？
08/16 22:09, 53F
推
08/16 22:28, 7年前 , 54F
如果兩個體一樣大 他們會一樣(isomorphic)
08/16 22:28, 54F
→
08/16 22:29, 7年前 , 55F
就好比有一群學生 他們的中文名是一個體 英文名也是
08/16 22:29, 55F
→
08/16 22:29, 7年前 , 56F
這兩個名字的集合關係就是那種同構的感覺
08/16 22:29, 56F
→
08/16 22:30, 7年前 , 57F
或者說 假設兩個體大小為t 則他們元素為x^t-x=0的根
08/16 22:30, 57F
→
08/16 22:31, 7年前 , 58F
而且還可以證明t一定是某個質數的次方
08/16 22:31, 58F
→
08/16 23:07, 7年前 , 59F
謝謝回答，好專業數學的感覺！
08/16 23:07, 59F
→
08/16 23:09, 7年前 , 60F
但橢圓曲線在R這個 體 上，大小應該是無窮大！？因
08/16 23:09, 60F
→
08/16 23:09, 7年前 , 61F
為是連續且沒上限的曲線
08/16 23:09, 61F
→
08/16 23:11, 7年前 , 62F
還是要 看成 橢圓曲線 在階數為N時 在R上 的體？ 這
08/16 23:11, 62F
→
08/16 23:11, 7年前 , 63F
樣在我例子裡，大小就是固定的21個
08/16 23:11, 63F
推
08/16 23:12, 7年前 , 64F
但是無限大還分很多 有Q(有理數) R(實數)等等的體
08/16 23:12, 64F
→
08/16 23:13, 7年前 , 65F
然後在mod 31時的 Z mod N 這個 體 上 階數也是21
08/16 23:13, 65F
→
08/16 23:13, 7年前 , 66F
兩個體的大小 會相同
08/16 23:13, 66F
→
08/16 23:15, 7年前 , 67F
但21不是某個質數的次方
08/16 23:15, 67F
→
08/16 23:17, 7年前 , 68F
Zmod31是一個體 元素為x^31-x=0的根
08/16 23:17, 68F
→
08/16 23:17, 7年前 , 69F
但是在這個體定義出來的橢圓曲線就不受限制了
08/16 23:17, 69F
→
08/16 23:18, 7年前 , 70F
你定義出來的橢圓曲線 頂多只有加法 只是個"群"而已
08/16 23:18, 70F
→
08/16 23:19, 7年前 , 71F
說到有理數還是 實數 老實說我不知道 在連續曲線上
08/16 23:19, 71F
→
08/16 23:19, 7年前 , 72F
取出特定點 使得階數為21時，這20個點 座標是有理
08/16 23:19, 72F
→
08/16 23:19, 7年前 , 73F
數還是無理數...因為我只是用excel 計算，用逼近法
08/16 23:19, 73F
→
08/16 23:19, 7年前 , 74F
得到這20個點座標，小數位到9、10位 但是有理數還
08/16 23:19, 74F
→
08/16 23:19, 7年前 , 75F
無理數...無從得知
08/16 23:19, 75F
→
08/16 23:22, 7年前 , 76F
喔喔喔 我以為t是體的大小(個數？)
08/16 23:22, 76F
→
08/16 23:23, 7年前 , 77F
橢圓曲線在取 mod P 時 個數常常不等於P
08/16 23:23, 77F
→
08/16 23:25, 7年前 , 78F
喔喔喔 懂了 我說的個數 是群的大小 不是體的大小
08/16 23:25, 78F
推
08/16 23:55, 7年前 , 79F
我有把以上討論的內容整理一篇回文了 你可以去看看
08/16 23:55, 79F
‣ 更多 okpk3k 的文章
文章代碼(AID): #1RSgDzwH (Math)
‣ 更多 okpk3k 的文章
文章代碼(AID): #1RSgDzwH (Math)