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

[mildkoala (mildkoala)]

基於離散對數難問題

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
→ Vulpix      : 3 = 5^(-1) (mod 7)  這是你的記號允許的範圍嗎？
允許 因為是循環群

※ 編輯: mildkoala (123.193.70.117), 05/28/2019 15:00:31
→ Vulpix      : 那就簡單多了，因為有費瑪小定理，所以 5^(-1) 也可
→ Vulpix      : 以寫成 5^5，所有的 -1 次方都是 5 次方，也是 11
→ Vulpix      : 次方、17 次方、……
→ Vulpix      : 選一個喜歡的正數就好。
→ Desperato   : 既然是循環群 為什麼會有問題啊XD
我的問題是 給定一個固定x的值

但只公開給 (Y,g,N) 要讓驗證者相信證明者的x為正的

同時 g,N 不一定要是質數也不一定要互質

但看起來應該是無法證明的 因為是循環群關係的

只給(Y,g,N) 無法讓驗證者相信x必為正數

還是感謝各位
※ 編輯: mildkoala (123.193.70.117), 05/28/2019 17:32:24
→ Vulpix      : (Z_N)* 無論如何都有限，所以就算 x 是負的，多加幾
→ Vulpix      : 次 |(Z_N)*|=φ(N) 總是能得到正數。跟 N 不互質的
→ Vulpix      : Y,g 作法也差不多，只是可能會比較繁瑣一點點。
推 LPH66       : 這看起來像是在設計零知識證明?
→ Desperato   : 我知道你的意思 不過沒必要 因為就算不是正的 也能
→ Desperato   : 改選正的那個XD
→ Desperato   : 零知識證明是什麼啊
→ ma4wanderer : 好像連自己在問什麼都不知道  哈哈