如何计算c中的逆模幂？

Question

我想取整数的模逆(k≥1)然后将结果乘以另一个整数，如下面的表达式解释：

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

我如何实现这个表达式，其中 k≥1？

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

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()是普通整数求幂。

由于此类计算中的系数会很快变得非常大，因此最好使用 ready-made 库（例如 gmp）。

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，我认为我们没有多少计算可以执行 modulo 0.

The modular multiplicative inverse of an integer N modulo m is an integer n such as the inverse of N modulo m equals n, if a modular inverse exists then it is unique. To calculate the value of the modulo inverse, use the extended euclidean algorithm which finds solutions to the Bezout identity.

用法示例：

#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
*/

Source

如何计算c中的逆模幂？

How to calculate inverse modular exponentation in c?

c

inverse

mod