Модулю разделения двух чисел

мы знаем, что

(A + B) % P = (A % P + B % P) % P
(A * B) % P = (A % P * B % P) % P

где P - простое число.

Мне нужно вычислить (A / B) % P, где A,B может быть очень большим и может переполняться.

Соответствует ли такая формула для модульной арифметики для (A / B) % P и (A - B) % P.

Если нет, то, пожалуйста, объясните, что такое правильный ответ.

I. Это правда, что (A / B) % P = ((A % P) / (B % P)) % P?

Я ПЫТАЛСЯ К КАЛИГУЛИРОВАНИЮ (N * (N ^ 2 + 5)/6)% P, где N может достигать 10 ^ 15

здесь A = n * (n ^ 2 + 5), безусловно, может переполняться при n = 10 ^ 15

Ответ 1

Да, но это другое:

(a - b) mod p = ((a mod p - b mod p) + p) mod p

(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p

Где b^(-1) mod p является модульным обратным b mod p. Для p = prime, b^(-1) mod p = b^(p - 2) mod p.

Edit:

(N * (N ^ 2 + 5)/6)% Р

Вам не нужны модульные инверсии. Просто упростите фракцию: N or N^2+5 будет делиться на 2 и 3. Разделите их, а затем у вас есть (a*b) mod P.

Ответ 2

Правильный ответ:

(a - b) mod p = ((a mod p - b mod p) + p) mod p
(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p

Эти и некоторые другие операции описанные здесь в разделе "Эквиваленты".

Просто хочу сообщить, что это будет работать не только для простого числа p. Первый будет работать для любого p. Второй будет работать для любого p, где b^(-1) или модульный обратный.

Модульный обратный может быть вычислен с помощью расширенного евклидова алгоритма

Ответ 3

Независимо от вашего алгоритма, если входы A и B, и если они переполняются, то вы не можете запустить алгоритм. Важно сообщить нам, откуда эти цифры. Являются ли они суммой или продуктом других чисел, которые у вас есть?

Для больших чисел вы должны использовать специальную математическую библиотеку для больших чисел. Как обрабатывать произвольно большие целые числа С такими библиотечными возможностями вы можете просто сделать (A/B)% P.