Work with big numbers as array [closed]

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 6 years ago.

Impr开发者_Python百科ove this question

I have to use big numbers for RSA so I use arrays:

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

How can I multiply them with a fast algorithm and calculate modular multiplicative inverse?

---

You'll probably want to use either gmp or bcmath. These are php libraries designed for dealing with large numbers and computations.

---

Algorithm

To say that b is the modular inverse mod m of a is to say that

a * b = 1 (mod m)

for any integer a, there exist such an inverse b if and only if a and b are relatively prime. Using the extended euclidean algorithm we can find an x and y such that a * x + m * y = 1. From that is is apparent that a * x = 1 (mod m), therefore x is the modular inverse of a.

Code

I know you want it within PHP but I have C++ version maybe you can convert it into PHP later on.

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;