Arduino模塊化算術大數

我寫了一個代碼來繞過大數字：問題是，有一個輕微的問題，我似乎無法捕捉它。直到指數纔是準確的，或者b是2，然後是3-4，稍微偏離，然後5-6它剛剛開始偏離真實答案。Arduino模塊化算術大數

#include <iostream> 
#include <conio.h> 
using namespace std; 

unsigned long mul_mod(unsigned long b, unsigned long n, unsigned long m); 

unsigned long exponentV2(unsigned long a, unsigned long b, unsigned long m); 

int main() 
{ 
    cout << exponentV2(16807, 3, 2147483647); 
    getch(); 
} 

unsigned long exponentV2(unsigned long a, unsigned long b, unsigned long m) 
{ 
    unsigned long result = (unsigned long)1; 
    unsigned long mask = b; // masking 

    a = a % m; 
    b = b % m; 

    unsigned long pow = a; 

    // bits to exponent 
    while(mask) 
    { 
    //Serial.print("Binary: "); // If you want to see the binary representation,  uncomment this and the one below 
    //Serial.println(maskResult, BIN); 
     //delay(1000); // If you want to see this in slow motion 
    if(mask & 1) 
    { 
      result = (mul_mod(result%m, a%m, m))%m; 

      //Serial.println(result); // to see the step by step answer, uncomment this 
    } 
    a = (mul_mod((a%m), (a%m), m))%m; 
    //Serial.print("a is "); 
    //Serial.println(a); 
    mask = mask >> 1;   // shift 1 bit to the left 

    } 
    return result; 
} 

unsigned long add_mod(unsigned long a, unsigned long b, unsigned long m) 
{ 
    a = a%m; 
    b = b%m; 
    return (a+b)%m; 
}

來源

2012-10-06 Joey Arnold Andres

你什麼答案，你怎麼看它應該是什麼？ – Beta

我一直在比較它與沃爾夫拉姆阿爾法，並試圖追查非常狡猾的錯誤。我現在無法給出數字，因爲我處於這個過程中，逐步完成所有事情。 –

你確定無處不在的代碼應該運行的時候是'unsigned long'是64位嗎？（如果'mul_mod'類似於'exponentV2'，這可能不是必須的，但如果它基本上是'return（（％m）*（b％m））％m;'。 –

我只是看着你的代碼，發現幾件事情：

在功能

：

unsigned long exponentV2(unsigned long a, unsigned long b, unsigned long m);

據我所知，這個函數返回一個^ B模m
在初始化你銷燬指數（b = b％m）這會使結果無效!!!刪除該行

在功能：

unsigned long add_mod(unsigned long a, unsigned long b, unsigned long m);

你不處理溢出（如果A + B比長大？）在這種情況下（A + B）％
m是錯誤的，...
你應該在遇到溢出時從結果中減去m * x而不是模數。
x必須是一樣大，以便M * x是長消除溢出差不多大小...
所以（A + B） - （M * X）也適合於長可變

更多的有識之士看看這個：Modular arithmetics and NTT (finite field DFT) optimizations

希望它有助於

來源

2013-09-03 13:55:50 Spektre

Arduino模塊化算術大數

回答

相關問題