[問題] 超級大數運算問題

[initial1635 (AmazingTWman)]

開發平台(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
→ EdisonX:google 「大數演算法」, 高效 library : GMP
→ suhorng:(a*b)%c = ((a%c)*(b%c))%c
→ suhorng:多個數字時類推
→ suhorng:你的 Zp 平方是還在 unsigned long long int 範圍內的
推 b98901056:同suhorng大大
→ EdisonX:疑！不過你的問題未必要用大數耶,要用 mod 的全式寫出來 ?
→ suhorng:Hint在講計算 a^b % c 時, 的 O(log b) 算法, 不用 O(b)
→ EdisonX:@@ 慢了
→ suhorng:他提到的就是反覆平方法 (有人叫他 bigmod...XD)
→ EdisonX:嗯，謝謝 shuorng 補充. @原 po: google 蒙格馬利快速取模
我用(((x*x)%p)*x)%p 算出來的結果是1424112743
自己用小算盤算64777729713265913381403751 % 2147483629 = 220886070
為什麼不一樣@@? 我哪裡錯了嗎@@?
還是真的要去用array的方式寫個大數運算啊@@?
→ EdisonX: ( (x%p) * (x%p) *(x%p) ) % p;
→ EdisonX:然後你的 p 如果超過 sqrt(max_unsigned long long) 會 ov
剛剛發現原來我宣告沒弄好所以ov了-.-
感謝<(_ _)>
推 EdisonX:更正， ( ( (x%p) * (x%p) ) %p) * (x%p) ) %p
→ EdisonX:還是用 loop 去搞吧 @@
→ EdisonX:假設 x%p = a , 如果 p > sqrt(ULL), 那 a * (a%p) 也 ov
input不會超過2^31 所已經該不會ov  o.o
※ 編輯: initial1635     來自: 1.169.162.109        (01/13 00:24)