[代數] 求神人指點 離散對數難問題證明

看板Math作者 (mildkoala)時間6年前 (2019/05/28 14:42), 6年前編輯推噓1(1推 0噓 13→)
留言14則, 4人參與, 6年前最新討論串1/1
基於離散對數難問題 Y = g^x mod N 可以公開的參數是 (Y,g,N) x為秘密是不可以公開的 試著用任何方法證明指數x為正數 請問有神人有解嗎 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.70.117 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1559025768.A.8E3.html
→
05/28 14:54, 6年前 , 1F
3 = 5^(-1) (mod 7) 這是你的記號允許的範圍嗎？
05/28 14:54, 1F
允許 因為是循環群 ※ 編輯: mildkoala (123.193.70.117), 05/28/2019 15:00:31
→
05/28 15:03, 6年前 , 2F
那就簡單多了，因為有費瑪小定理，所以 5^(-1) 也可
05/28 15:03, 2F
→
05/28 15:04, 6年前 , 3F
以寫成 5^5，所有的 -1 次方都是 5 次方，也是 11
05/28 15:04, 3F
→
05/28 15:04, 6年前 , 4F
次方、17 次方、……
05/28 15:04, 4F
→
05/28 15:06, 6年前 , 5F
選一個喜歡的正數就好。
05/28 15:06, 5F
→
05/28 15:34, 6年前 , 6F
既然是循環群 為什麼會有問題啊XD
05/28 15:34, 6F
我的問題是 給定一個固定x的值 但只公開給 (Y,g,N) 要讓驗證者相信證明者的x為正的 同時 g,N 不一定要是質數也不一定要互質 但看起來應該是無法證明的 因為是循環群關係的 只給(Y,g,N) 無法讓驗證者相信x必為正數 還是感謝各位 ※ 編輯: mildkoala (123.193.70.117), 05/28/2019 17:32:24
→
05/28 18:09, 6年前 , 7F
(Z_N)* 無論如何都有限，所以就算 x 是負的，多加幾
05/28 18:09, 7F
→
05/28 18:11, 6年前 , 8F
次 |(Z_N)*|=φ(N) 總是能得到正數。跟 N 不互質的
05/28 18:11, 8F
→
05/28 18:11, 6年前 , 9F
Y,g 作法也差不多，只是可能會比較繁瑣一點點。
05/28 18:11, 9F
推
05/28 18:12, 6年前 , 10F
這看起來像是在設計零知識證明?
05/28 18:12, 10F
→
05/28 18:13, 6年前 , 11F
我知道你的意思 不過沒必要 因為就算不是正的 也能
05/28 18:13, 11F
→
05/28 18:13, 6年前 , 12F
改選正的那個XD
05/28 18:13, 12F
→
05/28 18:13, 6年前 , 13F
零知識證明是什麼啊
05/28 18:13, 13F
→
05/30 20:00, 6年前 , 14F
好像連自己在問什麼都不知道 哈哈
05/30 20:00, 14F
‣ 更多 mildkoala 的文章
文章代碼(AID): #1SxDXeZZ (Math)