La tarea es la siguiente: dado un entero positivo x
y un primo n > x
, genera el entero positivo más pequeño de y
tal manera (y * y) mod n = x
. Una parte importante de esta pregunta es el límite de tiempo especificado a continuación que excluye las soluciones de fuerza bruta.
Si no existe dicho valor y
, su código debería salir N
.
Casos de prueba
(2, 5, N),
(3, 5, N),
(4, 5, 2),
(524291, 1048583, N),
(529533, 1048583, N),
(534775, 1048583, 436853),
(540017, 1048583, 73675),
(536870913, 1073741827, 375394238),
(542239622, 1073741827, 267746399),
(547608331, 1073741827, N),
(552977040, 1073741827, 104595351),
(1099511627676, 1099511627791, N),
(1099511627677, 1099511627791, 269691261521),
(1099511627678, 1099511627791, 413834069585),
(1267650600228229401496703204376, 1267650600228229401496703205653, 5312823546347991512233563776),
(1267650600228229401496703204476, 1267650600228229401496703205653, N)
(1267650600228229401496703204576, 1267650600228229401496703205653, N)
(1267650600228229401496703204676, 1267650600228229401496703205653, 79905476259539917812907012931)
Entrada y salida
Puede tomar entrada y dar salida de cualquier manera que sea conveniente. Si no le gusta la salida N
, cualquier Falsey
valor lo hará.
Restricciones
Su código debe responder a todos los casos de prueba en menos de 1 minuto en un escritorio estándar. Este límite de tiempo es solo para evitar respuestas de fuerza bruta y espero que las buenas respuestas se ejecuten casi instantáneamente. No puede usar ninguna biblioteca o biblioteca que resuelva este problema o que pruebe si un número es un residuo cuadrático.
1267650600228229401496703205653
ti o si tienes soporte de 128 bits como__int128
en gcc. También hay una serie de bibliotecas int de 256 bits para varios idiomas. Por último, muchos idiomas tienen una biblioteca int de precisión arbitraria.Respuestas:
Pyth,
8382 bytesBanco de pruebas
Este programa implementa el algoritmo Tonelli-Shanks . Lo escribí siguiendo de cerca la página de Wikipedia. Se toma como entrada
(n, p)
.El siguiente error informa la ausencia de una raíz cuadrada:
Este es un código muy complejo, escrito en el estilo imperativo, en oposición al estilo funcional más común de Pyth.
El único aspecto sutil de Pyth que estoy usando es
=
que, si no es seguido inmediatamente por una variable, busca en el programa la siguiente variable, luego asigna el resultado de la siguiente expresión a esa variable, luego devuelve ese resultado. Me referiré a lo largo de la explicación a la página de Wikipedia: el algoritmo Tonelli-Shanks , ya que ese es el algoritmo que estoy implementando.Explicación:
A
toma una tupla de 2 como entrada, y asigna los valores aG
yH
respectivamente, y devuelve su entrada.Q
es la entrada iniciale
Devuelve el último elemento de una secuencia. Después de este fragmento,G
esn
yH
yQ
sonp
.M
define una función de 2 entradasg
, donde están las entradasG
yH
..^
es la función de exponenciación modular rápida de Pyth. Este fragmento se defineg
como mod de exponenciación mediaQ
.f
define una repetición hasta el bucle falso y devuelve el número de iteraciones para las que se ejecuta, dado1
como su entrada. Durante cada iteración del ciclo, dividimosH
por 2, establecemosH
ese valor y verificamos si el resultado es impar. Una vez que es, nos detenemos.K
almacena el número de iteraciones que esto tomó.Una cosa muy complicada es la
=2;
parte.=
busca la siguiente variable, que esT
, por lo queT
se establece en 2. Sin embargo,T
dentro de unf
ciclo está el contador de iteraciones, por lo que usamos;
para obtener el valor delT
entorno global. Esto se hace para guardar un par de bytes de espacios en blanco que de otra forma serían necesarios para separar los números.Después de este fragmento,
K
esS
del artículo de wikipedia (wiki), yH
esQ
del wiki, yT
es2
.Ahora, necesitamos encontrar un mod cuadrático no residual
p
. Fuerza bruta esto usando el criterio de Euler./Q2
es decir(p-1)/2
, dado que/
está dividida en pisos, entoncesftgT/Q;1
encuentra el primer número enteroT
dondeT ^ ((p-1)/2) != 1
, según lo deseado. Recordemos que;
nuevamente se extraeT
del entorno global, que todavía es 2. Este resultado esz
de la wiki.Luego, para crear
c
desde el wiki, necesitamosz^Q
, así que envolvemos lo anteriorg ... H
y le asignamos el resultadoT
. AhoraT
esc
de la wiki.Vamos a separar a cabo esto:
~gGH
.~
es como=
, pero devuelve el valor original de la variable, no su nuevo valor. Por lo tanto, regresaG
, que esn
de la wiki.Esto asigna
J
el valor den^((Q+1)/2)
, que esR
de la wiki.Ahora, surte efecto lo siguiente:
Esto asigna
G
el valorn^Q
, que est
de la wiki.Ahora, tenemos nuestras variables de bucle configuradas.
M, c, t, R
de la wiki sonK, T, G, J
.El cuerpo del bucle es complicado, así que lo presentaré con el espacio en blanco, tal como lo escribí:
Primero, verificamos si
G
es 1. Si es así, salimos del ciclo.El siguiente código que se ejecuta es:
Aquí, buscamos el primer valor de
i
tal queG^(2^i) mod Q = 1
, comenzando en 1. El resultado se guarda enK
.Aquí, tomamos el valor anterior de
K
, restamos el nuevo valor deK
, restamos 1, aumentamos 2 a ese poder, y luego aumentamosT
a ese mod de poderQ
, y luego asignamos el resultado aT
. Esto hace que seaT
igual ab
la wiki.Esta es también la línea que termina el ciclo y falla si no hay solución, porque en ese caso el nuevo valor de
K
será igual al valor anterior deK
2-1
, y la exponenciación modular generará un error.A continuación, multiplicamos
J
por el resultado anterior y lo almacenamos nuevamenteJ
, manteniéndonosR
actualizados.Luego cuadramos
T
y almacenamos el resultado nuevamenteT
,T
volviendo ac
la wiki.Luego multiplicamos
G
por ese resultado, tomamos modQ
y almacenamos el resultado nuevamenteG
.Y terminamos el ciclo.
Una vez finalizado el ciclo,
J
hay una raíz cuadrada den
modp
. Para encontrar el más pequeño, utilizamos el siguiente código:_BJ
crea la listaJ
y su negación,%
toma implícitamenteQ
su segundo argumento y usa el comportamiento predeterminado de Pyth para aplicar% ... Q
a cada miembro de la secuencia. LuegoS
ordena la lista yh
toma su primer miembro, el mínimo.fuente
Python 2, 166 bytes
fuente
%timeit Q(1267650600228229401496703204676,1267650600228229401496703205653) 100 loops, best of 3: 2.83 ms per loop
:)SageMath , 93 bytes
Al reducirse a un problema mucho más difícil para el que SageMath tiene builtins lo suficientemente rápidos.
Pruébalo en SageMathCell
fuente
Haskell , 326 bytes
Por lo general, me gustan las respuestas de fuerza bruta. Como el límite de tiempo no recomienda esto, esta es la forma más eficiente que conozco:
Pruébalo en línea!
Estoy seguro de que esto se puede reducir aún más, pero esto debería hacerlo por ahora.
fuente
testCases
con los del TIO original, apenas cabe en un comentario, incluso sin ellos.testCases
.