Encuentra un número que genera todos los enteros mod q

9

Considere el módulo de enteros qdonde qes primo, un generador es cualquier entero, de 1 < x < qmodo que x^1, x^2, ..., x^(q-1)cubre todos q-1los enteros entre 1y 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 = 1cubre todos los valores 3, 2, 6, 4, 5, 1cubre todos los enteros 1..6según sea necesario.

La tarea es escribir código que toma una entrada ny 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 2para el poder de n. Eso ^representa la exponenciación.


fuente
Hmm ... 1 < x < qhace el desafío mucho más fácil.
Erik the Outgolfer
@EriktheOutgolfer No estoy seguro de saber a qué te refieres. Esos son todos los enteros distintos que no son 0 o 1.
Quiero decir que es más fácil de lo que muchos probablemente piensan ... o tal vez algún momento inactivo en PPCG.
Erik the Outgolfer
3
Pero creo que es innecesario exigir a las personas que lo prueben hasta completar un gran número ... básicamente, solo sería un error de memoria.
Erik the Outgolfer
@Lembik ¿Hay algún caso en el que no haya un generador para cierto número? Algunos casos de prueba serían buenos.
Sr. Xcoder

Respuestas:

13

Pyth, 16 15 bytes

f-1m.^T/tQdQPtQ

Banco 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:

f-1m.^T/tQdQPtQ
f                  Return the first value T such that the following is truthy:
            PtQ    Take the prime factorization of the input - 1.
   m               Map those prime factors to
       /tQd        Take the input - 1 divided by the factor
    .^T    Q       Raise T to that exponent mod input,
                   performed as modular exponentiation, for performance.
 -1                Check that 1 is not found among the results.
isaacg
fuente
¡Bastante impresionante!
¿Su código realiza la factorización?
@Lembik Sí (la PtQparte).
Erik the Outgolfer
-3
%MATLAB CODE
%Program to generate Z_n for an integer n
n = input('Enter a number to find modulo')
q = input ('Enter a prime number greater than the number you wished to find modulo')
if n>=q 
   fprintf('Error')
   exit(1)
end
for R=1:q-1
    fprintf(rem(n.^R, q))
    fprintf('\n')
end
John Brookfields
fuente
1
Esto no está resolviendo el problema correcto. Su código debe, por ejemplo, tomar una entrada y dar una salida.
1
Además, este código no se juega en absoluto. El código de golf debe ser lo más corto posible, para que pueda eliminar el texto de entrada y los espacios alrededor de signos de igualdad y demás.
Camarada SparklePony
3
@ComradeSparklePony Creo que el primer problema que no está resolviendo el problema correcto debería abordarse primero :)