Re: [其他] 離散 橢圓曲線

[thr3ee (亞澤蛙 妮可)]

※ 引述《okpk3k (登登)》之銘言：
: 最近在認識比特幣時，了解到比特幣的公鑰,私鑰是利用數學的橢圓曲線來做加密。
: 過程會對特定的橢圓曲線取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是很多資安系統採
: 用的加密方式。

我在這邊整理一下推文的資訊
以供其他版友參考

1. 橢圓曲線的定義為y^2=x^3+ax+b
   其中a和b是常數

2. 我們一般講的橢圓曲線
   其實可以寫成"{(x,y) in R*R| y^2=x^3+ax+b, a,b is constant in R}"
   也就是方程式"y^2=x^3+ax+b"定義在xy平面上面的解
   所以定義橢圓曲線是需要一個空間的
   而一般我們規定的空間是R
   或者稱之為實數的空間

3. 如果你想要讓橢圓曲線定義的好
   也就是元素們可以做加法減法
   或者更準確的說是橢圓曲線的集合要是一個"群(group)"
   那麼我們會定義(a,b)+(p,q)的值為
   "兩點連成直線 恰交橢圓曲線於一點 此點對x軸做對稱 所得的點就是所求值"

4. 在這個定義之下
   有學習過數學系抽象代數的同學(通常是大二必修課)
   可以證明必須要把橢圓曲線定義在"體(field)"的空間內才可以達成要求
   否則有一些元素相加後可能就不在曲線上
   或者是出現一些奇怪的狀況等等

5. "體(field)"就是一個具有兩種運算方式的群
   比方說有理數就有加法和乘法
   比方說實數就有加法和乘法
   比方說實數矩陣就有矩陣加法和矩陣乘法

6. 如果是有限大小的體
   則大小(表示為t)必定是某個質數的次方
   而且這個體正好就是x^t-x=0的根
   所以每個一樣大的有限體都有相同的結構(isomorphic)

7. 如果是無限大小的體
   例如有理數/實數/實數的2*2矩陣/...
   那就沒有上述那麼好康的性質了
   大概要學習過"伽羅瓦定理(galois theory)"以後會比較了解無限體的關係

8. 定義在有限體上面的橢圓曲線
   可以證明是一個群
   而且他們具備加法的運算
   至於集合大小就不一定是某個質數的次方囉!

9. 數學系的橢圓曲線課程是非常恐怖的課程
   主要就是在討論一些用積分定義出來的符號以及數論的內容
   這也會在數學系的複分析課學到(通常是大三必修)
   然而卻沒有提到半點有限體相關的知識

大概就是這樣
由於我已經兩年沒碰代數
所以如果有意見請提出討論
謝謝


--
http://imgur.com/QTIXoZQ
取自萌娘百科-Niconiconi*20.gif( zh.moegirl.org/zh-tw/File:Niconiconi*20.gif )

http://imgur.com/WiJ9BQl
取自萌娘百科-妮可顏藝.jpg( zh.moegirl.org/zh-tw/File:妮可顏藝.jpg )

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.217.172
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1534434895.A.C9A.html
推 clambering  : 印象中我在我學校書架上看過橢圓曲線的書 裡面有提`
→ clambering  : 有限體的狀況跟基本加密方法 要有不錯的群論先備知`
→ clambering  :  網路上其實也蠻多相關資料的 只是是法文 你想要的`
→ clambering  : 我九月可以幫你找找有沒有英文的相關資料
推 okpk3k      : 謝謝 我也看了很多網頁介紹 阿貝爾群 跟基本的加密
→ okpk3k      : 原理 但應該都是些基本介紹
→ okpk3k      : 只是一直沒找到 討論連續跟離散下的對應關係 才來這
→ okpk3k      : 發問
現在直接回答你"離散的橢圓曲線對應到連續的橢圓曲線"這個問題

質數體:就是一個體 他的元素只有{1,1+1,1+1+1,1+1+1+1,...}
可以證明質數體的元素個數只能是質數或是無限大
所以質數體只會是F[q](即Z mod q, q質數)或者是Q(有理數)
而且每一個體裡面都藏著一個質數體
因為每個體都有單位元1 也自然有1+1, 1+1+1, ...(加法封閉性)

因為密碼學的離散橢圓曲線其實是定義在F[p](即Z mod p)之上
所以現在問題可以轉化成"F[p]對應到無限大體"的這個問題
然後橢圓曲線只是定義在這些體之上的方程式"y^2=x^3+ax+b"的解

如果要把F[p]送到內藏Q的無限大體
那絕對是不可能的
比方說當p=5
那麼我們選擇計算7個1相加
在F[p]內的值為2
在內藏Q的無限體的值為7(而且不等於2)
因此產生矛盾

如果要把F[p]送到內藏F[q]的無限大體
(a)p=q 那就把F[p]送到F[q]就好
(b)p!=q 那就不可能送進去 因為會產生1+1+...+1的矛盾

那麼如果給定一個F[p]的體
可不可以製造出一些內藏F[p]的無限體呢?
比方說: F[p](x)={ a[0]+a[1]x+a[2]x^2+...+a[n]x^n | a[i] in F[p] for all i}
還有其他更多的例子
但這些要牽涉到"體擴張(field extension)"以及更複雜的結構
我也已經忘的差不多
所以就講到這邊
大概就這樣
※ 編輯: thr3ee (140.112.217.172), 08/17/2018 11:40:10
※ 編輯: thr3ee (140.112.217.172), 08/17/2018 11:40:59
推 okpk3k      : 謝謝回覆 我需要些時間google來消化