RSA演算 Euler定理搞定LeetCode 372 Super Pow--C,C++,Python實作

 

 RSA 演算 Euler 定理搞定#LeetCode 372 Super Pow--C,C++,Python實作。玩過數論、RSA演算的，解這個問題剛好，C++解答打敗94%，還沒有特別優化。

Python做好的車輪太多，練不到什麼功，純粹就減少存取時間，用C/C++包好的系統Python函式，儘量少用純Python的慢速車輪。C語言又幾乎沒車輪全部要自己來，C++還有些車輪。

LeetCode把隱藏版的測試數字弄得很大，自製車輪一不小心就會runtime error。

後來小心觀看，C++ 最後的一個for-loop控制變數i的初值12應該跟C版的一樣都要改成11，這個疏忽卻未造成IndexError，應該是跟bitset存取一次可要抓很多bits有關。

 [LeetCode清單]https://www.youtube.com/watch?v=bn2ZySAsbHA&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk&index=1 

[RSA簡介與python加密解密示範]https://youtu.be/72SU1B4M44M

C版的code在下方，全部自己造車輪

int superPow(int a, int* b, int bSize){
    const int n=1337;
    const int phi=1140;
    int exp=0;
    for(register int i=0; i<bSize; i++)
        exp=(b[i]+10*exp)%phi;
    bool e[12];
    int e2=exp;
    for(register int i=0; i<12; i++){
        e[i]=(e2%2==1);
        e2>>=1;
    }       
    int y=1;
    a%=n;
    for(register int i=11; i>=0; i--){
        y=y*y%n;
        if (e[i]) y=y*a%n;
    }
    return y;
}