Модульная мультипликативная обратная функция не работает для отрицательных чисел

Question

Модульная мультипликативная обратная функция не работает для отрицательных чисел

У меня есть функция ниже, чтобы вычислить модульную мультипликативную инверсию числа n, данного по модулю числа p.

int modInverse(int n, int p) {
n %= p;
for(int x = 1; x < p; x++) {
if((n*x) % p == 1) return x;
}
}

Если n положительно, это нормально, но если n отрицательно, оно всегда дает 0.
Как я могу это исправить?

Умножение, обратное к x mod n: x ^ -1 mod n, это число, которое нужно умножить на x, чтобы получить 1 mod n
например 3 ^ -1 мод 7 = 5, так как 3 * 5 = 1 мод 7

0

c++inverse modulo

Решение

Другие решения

Помимо ненужных итераций, метод, который вы используете, имеет O(p) сложность. Вы можете использовать расширенный евклидов алгоритм с O(log(p)) сложность. В любом случае, отвечая на ваш вопрос и то, как вы это делаете, я бы посоветовал вам попробовать этот подход, который уменьшает количество итераций: (Java)

int calculateInverse2(int a, int zp) {
for (int i = (int) Math.ceil((zp-1)/a); i < zp; i++) {
if (Math.floorMod(a*i,zp) == 1) return i;
}
return -1;
}

Относится к отрицательным значениям в модуле операции, зависит от языка. Попробуйте реализовать метод, который суммирует определенное время p установить номер в кольце целых чисел.

Пример:

(-7)mod(2) => (-7+2)mod(2) => (-7+2+2)mod(2) => (-7+2+2+2)mod(6) => (-7+2+2+2+2)mod(6) => (1)mod(7)=1

Легко вычислить.

0

Источник

Accepted Answer

пример кода:

int modulo(int n, int p)
{
int r = n%p;
if(((p > 0) && (r < 0)) || ((p < 0) && (r > 0)))
r += p;
return r;
}

int modInverse(int n, int p) {
n = modulo(n, p);
for(int x = 1; x < p; x++) {
if(modulo(n*x, p) == 1) return x;
}
return 0;
}

int main(void)
{
int r;
r = modInverse(-25, 7);
return 0;
}

если вы хотели частное и остаток:

void divmod(int n, int p, int &q, int &r)
{
q = n/p;
r = n%p;
if(((p > 0) && (r < 0)) || ((p < 0) && (r > 0))){
q -= 1;
r += p;
}
}

2