Dado $a$, $b$, y una de las principales $p$, ¿qué tan rápido puedo solucionar $(a \cdot c) - (b \cdot d) \equiv 1 \bmod p$?

Question

Si estamos dados dos naturales, $a$$b$, y una de las principales $p$, ¿qué tan rápido puedo encontrar dos más de los naturales tal que $(a \cdot c) - (b \cdot d) \equiv 1 \bmod p$?

Además, se le permite precompute cualquier cosa que te gusta, pero el espacio de memoria se le da puede ser mayor que el tiempo que se tarda en resolver este problema. En otras palabras, ¿qué tan rápido puedo resolver para estas dos variables en el mismo tiempo y el espacio?

Answer 1

Primero de todo, no siempre será capaz de encontrar tales enteros $c$$d$: es posible que tanto $a$ $b$ son divisibles por $p$.

Supongamos entonces que $p$ no divide $a$ (intercambio de $a$ $b$ si es necesario). A continuación,$\gcd(a,p)=1$, por lo que el algoritmo de Euclides extendido calcula los números de $c$ $y$ tal que $ac+py=1$; usted puede simplemente tomar esta $c$$d=0$. El algoritmo de Euclides extendido se ejecuta muy rápidamente - lineal en el tamaño de la entrada de $(a,p)$.

Es concebible que el grado adicional de libertad que tiene en el problema inicial (puede variar tanto en$c$$d$) daría lugar a un algoritmo más rápido, pero lo dudo - el algoritmo de Euclides es rápido como un rayo en la práctica.

Finalmente, usted realmente no necesita $p$ principal: tales enteros $c$ $d$ existe si y sólo si $\gcd(a,b,p)=1$. (Si $a,b,p$ no son disjuntos a pares, entonces usted necesita para ejecutar el algoritmo de Euclides más de una vez, decir en $a$ $b$ primero y luego en $\gcd(a,b)$$p$.)

Answer 2

Como Greg Martin puntos fuera, usted no puede hacer esto, si $a$ $b$ son ambos divisibles por $p$. Así que asumir que al menos uno de ellos, decir $a$, no es divisible por $p$. En ese caso, usted puede seleccionar $d$ cualquier forma que desee (IOW el sistema es indeterminado). He aquí cómo:

1) de (Pre)calcular el inverso modular de $a$. Este es un entero con la propiedad $aa'\equiv1\pmod p$. Se puede encontrar una única ejecución de un algoritmo de Euclides extendido. Si el mismo $a,p$ son usados muchas veces, entonces es evidente que se puede almacenar el resultado para su futura reutilización.

2) Calcular el entero $c=a'(1+bd) \pmod p$, y lean el contenido. Aquí es la razón por la que funciona $$ a\cdot c=a\cdot a'(1+bd)\equiv 1+bd\pmod p, $$ debido a $a\cdot a'\equiv 1\pmod p$. Que la congruencia es claramente equivalente a la deseada congruencia (mover el plazo $bd$ para el otro lado y de intercambio de su signo).

===============================

IOW, si $(a,p)=1$ (o $(b,p)=1$), entonces, lo que tienes es esencialmente una sola ecuación lineal en dos variables con los parámetros que van por el campo $\mathbf{Z}_p.$ Bajo tales circunstancias, puede elegir una de las incógnitas de manera arbitraria y resolver para el otro. No será exactamente $p$ pares no congruentes soluciones.

Answer 3

Recientemente me respondió esencialmente la misma pregunta: Calcular el Modular Inverso Multiplicativo sin todos los símbolos de extraño aspecto

Se fue formulada de manera diferente: Se preguntó cómo encontrar el mod-$p$ inverso multiplicativo de un número que no es múltiplo de $p$ (es decir, no es lo mismo que $0$ mod $p$).

Exactamente el mismo algoritmo funciona para un non-prime, con la única condición de que el módulo y el número de cuya inversa se solicita no tienen factores primos comunes.