如何在C语言中计算逆模幂？

Question

我想对一个整数取模反元素(k≥1)，并将结果乘以另一个整数，如下式所示：

result=((x^(-k)))*y mod z

怎样实现这个表达式，其中k≥1？

- AR.5

Answer 1

您需要定义四个函数：

uint64_t modular_exponentiation(uint64_t x, uint64_t y, uint64_t z) 
{ 
    uint64_t res = 1;      
    x = x % z;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; // y = y/2 
        x = (x*x) % z;   
    } 
    return res; 
} 

uint64_t moduloMultiplication(uint64_t a, uint64_t b,uint64_t z) 
{ 
  uint64_t res = 0;  
  a %= z; 

  while (b) 
  {  
     if (b & 1) 
        res = (res + a) % z; 

     a = (2 * a) % p; 
     b >>= 1;  // b = b / 2 
   } 
  return res; 
}


void extendedEuclid(uint64_t A, uint64_t B)
{
uint64_t temp;                           
    if(B == 0)
    {
        d = A;
        x = 1;
        y = 0;
    }
    else
    {
        extendedEuclid(B,A%B);
        temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
}

int modInverse(uint64_t A, uint64_t M)
{
    extendedEuclid(A,M);
    if (x < 0)                      
        x += M;                     
    return (x);                     
}

在main()函数中：

uint64_t result=0x00;
result=modular_exponentiation(x,k,z);   // (x^k) mod z 
result=modInverse(result,z);            // ((x^k)^-1) mod z == x^(-k) mod z    
result=moduloMultiplication(result,y,z);// x^(-k) * y mod z

- abbasi_ahsan

---

你的 modInverse 函数可能非常慢，特别是当 a 的逆元接近于 z 时。 - clemens

当然它能工作。但是它的运行时间取决于逆的大小。如果OP想要用它构建一个简单的RSA加密，通常需要数小时甚至更长时间进行加密或解密。 - clemens

因此需要使用扩展欧几里得算法。 - abbasi_ahsan

现在Edit1已经完美地工作并且是优化的解决方案。 - abbasi_ahsan

Answer 2

您需要扩展的最大公约数来计算模数z下x的逆。当x和z互质时，您有a * x + b * z = 1 = gcd(x, z)。因此，a * x = 1 - b * z或a * x = 1 mod z，并且a是模数z下x的逆。
现在您可以使用x^-1 = a mod z计算result：

result = power(a, k) * y % z

使用C中的普通整数算术，其中power()是普通整数幂。

由于这种计算中的系数可以非常快地变得非常大，因此最好使用现成的库（例如gmp）。

- clemens

Answer 3

你可以尝试使用 mod_inv C 函数：

// return a modular multiplicative inverse of n with respect to the modulus.
// return 0 if the linear congruence has no solutions.
unsigned mod_inv(unsigned ra, unsigned rb) {
    unsigned rc, sa = 1, sb = 0, sc, i = 0;
    if (rb > 1) do {
            rc = ra % rb;
            sc = sa - (ra / rb) * sb;
            sa = sb, sb = sc;
            ra = rb, rb = rc;
        } while (++i, rc);
    sa *= (i *= ra == 1) != 0;
    sa += (i & 1) * sb;
    return sa;
}

这基本上是标准算法，当n = 1且mod = 0时，输出为0而非1，我认为我们没有太多计算要执行模0。

整数N模m的模乘逆元是一个整数n，使得N模m的逆元等于n，如果模逆元存在，则它是唯一的。要计算模反元素的值，请使用扩展欧几里得算法，该算法找到了Bezout恒等式的解。

用法示例：

#include <assert.h>

int main(void) {
    unsigned n, mod, res;

    n = 52, mod = 107;
    res = mod_inv(n, mod);
    assert(res == 35); //  35 is a solution of the linear congruence.

    n = 66, mod = 123;
    res = mod_inv(n, mod);
    assert(res == 0); // 66 does note have an inverse modulo 123.
}

/*
    n =     7 and mod = 45    then res = 13    so 1 == (   13 * 7    ) % 45   
    n =    52 and mod = 107   then res = 35    so 1 == (   35 * 52   ) % 107  
    n =   213 and mod = 155   then res = 147   so 1 == (  147 * 213  ) % 155  
    n =   392 and mod = 45    then res = 38    so 1 == (   38 * 392  ) % 45   
    n =   687 and mod = 662   then res = 53    so 1 == (   53 * 687  ) % 662  
    n =   451 and mod = 799   then res = 512   so 1 == (  512 * 451  ) % 799  
    n =  1630 and mod = 259   then res = 167   so 1 == (  167 * 1630 ) % 259  
    n =  4277 and mod = 4722  then res = 191   so 1 == (  191 * 4277 ) % 4722
*/

源代码

- Michel