Как рассчитать обратную модульную экспоненту в c?

Я хочу взять модульную инверсию (k≥1) целого числа, а затем умножить результат на другое целое число, как показано в следующем выражении:

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

Как я могу реализовать это выражение, где k≥1?


c mod inverse
person AR.5    schedule 28.05.2019    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Вам нужно определить четыре функции:

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
person abbasi_ahsan    schedule 28.05.2019
comment
Ваша функция modInverse может работать очень медленно, особенно если функция, обратная a, близка к z. - person clemens; 28.05.2019
comment
Конечно, это работает. Но время его выполнения зависит от размера инверсии. Если OP хочет создать с ним простое шифрование RSA, обычно для шифрования или дешифрования требуется несколько часов или больше. - person clemens; 28.05.2019
comment
Так что нужно использовать, может быть расширенный евклид - person abbasi_ahsan; 28.05.2019
comment
Теперь Edit1 работает отлично, а также оптимизированное решение. - person abbasi_ahsan; 28.05.2019

arrow_upward
1
arrow_downward

Вам понадобится расширенный наибольший общий делитель, чтобы вычислить значение, обратное x для модуля z. Когда x и z взаимно просты, у вас есть a * x + b * z = 1 = gcd(x, z). Таким образом, a * x = 1 - b * z или a * x = 1 mod z, а a является обратным к x по модулю z.

Теперь вы можете вычислить result с помощью x^-1 = a mod z:

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

с обычной целочисленной арифметикой в ​​C, где power() — обычное целочисленное возведение в степень.

Так как коэффициенты в таких расчетах могут очень быстро стать очень большими, то лучше использовать готовые библиотеки (например, gmp).

person clemens    schedule 28.05.2019