工作與大的數字，如陣列

Question

我有我使用數組來使用RSA大的數字：

$number1 = array(1234567, 7898765); 
$number2 = array(9876543, 2123456); 

我怎樣才能將它們相乘以快速算法和計算modular multiplicative inverse？

Answer 1

您可能需要爲使用gmp或bcmath。這些是爲處理大量數字和計算而設計的php庫。

Answer 2

算法

要說b是一個模塊化的逆模m是說

A * B = 1（mod M）表示

爲任何整數，有存在這樣的倒數b當且僅當a和b是相對的質數。使用擴展的歐幾里得算法，我們可以找到一個x和y，使得a * x + m * y = 1。從中可以明顯看出a * x = 1（mod m），因此x是a的模逆。

代碼

我知道你想要PHP內，但我有C++版本也許你可以把它轉換成PHP以後。

int x = px; 
int y = py; 

//Setup initial variables 
//Maintain throughout that ax * px + bx * py = x and that ay * px + by * py = y 
int ax = 1; 
int ay = 0; 
int bx = 0; 
int by = 1; 

//Perform extended gcd 
while(x) 
{ 
    if(x <= y) 
    { 
     int m = y/x; 
     y -= m * x; 
     ay -= ax * m; 
     by -= bx * m; 
    } 
    else 
    { 
     swap(x, y); 
     swap(ax, ay); 
     swap(bx, by); 
    } 
} 

//you can assert that ay * px + by * py = y = gcd(px, py) 
//you can assert that ax * px + bx * py = x = 0 

//If we're taking the modular inverse of px (mod py), then for it to exist gcd(px, py) = 1 
//If it does exist, it is given by ay (mod py) 
int inverse = ay % py; 
if(inverse < 0) inverse += py;