[問題] 超級大數運算問題
看板C_and_CPP (C/C++)作者initial1635 (AmazingTWman)時間13年前 (2013/01/12 23:30)推噓2(2推 0噓 13→)留言15則, 3人參與討論串1/2 (看更多)
開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
VC
問題(Question)：
我正在寫一個跟密碼學有關的程式Elliptic Curve
超過20位數的運算 我用unsigned long long int都不行 不知道該怎麼辦O_Q
y^2 = x^3 +3x +12
Zp=2147483629
x=401613751
內建函式pow沒辦法算那麼大的數 所以我用x*x*x硬算-.-
但是x^3是64777729713265913381403751 @@"
因為如果存不到變數裡連mod都沒有辦法
不知道該怎麼繼續下去...
有一個Hint是
The “double and add” strategy helps you come out a linear time
implementation of scalar multiplication instead of exponential time
但是我看不懂這是要幹嘛= =
把變數宣告改成double連算都沒法算 然後沒有在C++裡面看過add 所以不知道是幹嘛的@@
這種20位數以上的運算有辦法算嗎@@?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.169.162.109
→
01/12 23:32, , 1F
01/12 23:32, 1F
→
01/12 23:32, , 2F
01/12 23:32, 2F
→
01/12 23:32, , 3F
01/12 23:32, 3F
→
01/12 23:33, , 4F
01/12 23:33, 4F
推
01/12 23:33, , 5F
01/12 23:33, 5F
→
01/12 23:33, , 6F
01/12 23:33, 6F
→
01/12 23:33, , 7F
01/12 23:33, 7F
→
01/12 23:33, , 8F
01/12 23:33, 8F
→
01/12 23:34, , 9F
01/12 23:34, 9F
→
01/12 23:36, , 10F
01/12 23:36, 10F
我用(((x*x)%p)*x)%p 算出來的結果是1424112743
自己用小算盤算64777729713265913381403751 % 2147483629 = 220886070
為什麼不一樣@@? 我哪裡錯了嗎@@?
還是真的要去用array的方式寫個大數運算啊@@?
→
01/13 00:12, , 11F
01/13 00:12, 11F
→
01/13 00:13, , 12F
01/13 00:13, 12F
剛剛發現原來我宣告沒弄好所以ov了-.-
感謝<(_ _)>
推
01/13 00:19, , 13F
01/13 00:19, 13F
→
01/13 00:20, , 14F
01/13 00:20, 14F
→
01/13 00:21, , 15F
01/13 00:21, 15F
input不會超過2^31 所已經該不會ov o.o
※ 編輯: initial1635 來自: 1.169.162.109 (01/13 00:24)
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章