мы знаем, что
(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
Да, но это другое:
(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.
Правильный ответ:
(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) или модульный обратный.
Модульный обратный может быть вычислен с помощью расширенного евклидова алгоритма
Независимо от вашего алгоритма, если входы A и B, и если они переполняются, то вы не можете запустить алгоритм. Важно сообщить нам, откуда эти цифры. Являются ли они суммой или продуктом других чисел, которые у вас есть?
Для больших чисел вы должны использовать специальную математическую библиотеку для больших чисел. Как обрабатывать произвольно большие целые числа С такими библиотечными возможностями вы можете просто сделать (A/B)% P.