algorithm - tutorial - divisiones para niños
Módulo de división de dos números (3)
lo sabemos
(A + B) % P = (A % P + B % P) % P
(A * B) % P = (A % P * B % P) % P
donde P es un primo.
Necesito calcular (A / B) % P donde A,B puede ser muy grande y puede desbordarse.
Este tipo de fórmula para aritmética modular se mantiene para (A / B) % P y (A - B) % P
Si no, explique cuál es la respuesta correcta.
Es decir, es cierto que (A / B) % P = ((A % P) / (B % P)) % P ?
Estaba tratando de calcular (N * (N ^ 2 + 5) / 6)% P donde N puede ser tan grande como 10 ^ 15
aquí A = n * (n ^ 2 + 5) seguramente puede desbordarse para n = 10 ^ 15
Cualquiera que sea su algoritmo, si las entradas son A y B y si se desbordan, entonces no puede iniciar el algoritmo. Es importante que nos digas de dónde vienen esos números. ¿Son la suma o el producto de otros números que tienes?
Para números grandes debes usar una biblioteca de matemáticas especial para números grandes. Cómo manejar enteros arbitrariamente grandes Con esta biblioteca, es probable que pueda hacer (A / B)% P.
La respuesta de Vlad es correcta:
(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
Estas y algunas otras operaciones se describen aquí en la sección de equivalencias .
Solo quiero hacerle saber que esto funcionará no solo para el número primo p . El primero funcionará para cualquier p . El segundo funcionará para cualquier p , donde se define b^(-1) o inverso modular .
El inverso modular se puede calcular con el algoritmo euclidiano extendido
Sí, pero es diferente:
(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
Donde b^(-1) mod p es el inverso modular de b mod p . Para p = prime , b^(-1) mod p = b^(p - 2) mod p .
Editar:
(N * (N ^ 2 + 5) / 6)% P
No necesitas ningún inverso modular de esto. Simplemente simplifica la fracción: N or N^2+5 serán divisibles entre 2 y 3 . Entonces divídelos y entonces tienes (a*b) mod P