Considere el módulo de enteros q
donde q
es primo, un generador es cualquier entero, de 1 < x < q
modo que x^1, x^2, ..., x^(q-1)
cubre todos q-1
los enteros entre 1
y q-1
. Por ejemplo, considere los números enteros módulo 7 (que escribimos como Z_7
). Luego 3, 3^2 mod 7 = 2, 3^3 = 27 mod 7 = 6, 3^4 = 81 mod 7 = 4, 3^5 = 243 mod 7 = 5, 3^6 = 729 mod 7 = 1
cubre todos los valores 3, 2, 6, 4, 5, 1
cubre todos los enteros 1..6
según sea necesario.
La tarea es escribir código que toma una entrada n
y genera un generador Z_n
. Por supuesto, no puede usar ninguna biblioteca integrada o biblioteca que haga esto por usted.
La única restricción en el rendimiento de su código es que debe haberlo probado hasta su finalización n = 4257452468389
.
Tenga en cuenta que 2^n
significa 2
para el poder de n
. Eso ^
representa la exponenciación.
1 < x < q
hace el desafío mucho más fácil.Respuestas:
Pyth,
1615 bytesBanco de pruebas
Si p es la entrada, sabemos que g ^ (p-1) = 1 mod p, por lo que solo necesitamos verificar que g ^ a! = 1 mod p para cualquier a menor. ¡Pero a debe ser un factor de p-1 para que eso sea posible, y cualquier múltiplo de a con esa propiedad también tendrá esa propiedad, por lo que solo tenemos que comprobar que g ^ ((p-1) / q)! = 1 mod p para todos los factores primos q de p-1. Entonces, verificamos todos los enteros g en orden creciente hasta que encontremos uno que funcione.
Explicación:
fuente
PtQ
parte).Mathematica, 52 bytes
Inspirado por la respuesta de Isaac .
fuente
fuente