Encontre um número que gere todos os números inteiros mod q

9

Considere o módulo de números inteiros qonde qé primo, um gerador é qualquer número inteiro, de 1 < x < qmodo que x^1, x^2, ..., x^(q-1)cubra todos q-1os números inteiros entre 1e q-1. Por exemplo, considere o número inteiro do módulo 7 (que escrevemos como Z_7). Em seguida, 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 = 1abrange todos os valores, 3, 2, 6, 4, 5, 1abrange todos os números inteiros, 1..6conforme necessário.

A tarefa é escrever o código que recebe uma entrada ne gera um gerador Z_n. Você não pode usar nenhuma biblioteca ou biblioteca interna que faça isso para você, é claro.

A única restrição ao desempenho do seu código é que você deve testá-lo até o fim n = 4257452468389.

Note que isso 2^n significa 2o poder de n. Isso ^representa exponenciação.


fonte
Hmm ... 1 < x < qfacilita muito o desafio.
Erik the Outgolfer
@EriktheOutgolfer Não sei ao certo o que você quer dizer? Essas são apenas todos os inteiros distintos que não são 0 ou 1.
Quero dizer que é mais fácil do que muitos provavelmente pensam ... ou talvez algum momento inativo no PPCG.
Erik the Outgolfer
3
Mas acho que não é necessário exigir que as pessoas testem até um grande número de finalizações ... basicamente tio seria apenas erro de memória.
Erik the Outgolfer
@Lembik Existe algum caso em que não há gerador para um determinado número? Alguns casos de teste seriam bons.
Mr. Xcoder

Respostas:

13

Pitão, 16 15 bytes

f-1m.^T/tQdQPtQ

Suíte de teste

Se p é a entrada, sabemos que g ^ (p-1) = 1 mod p, portanto, basta verificar se g ^ a! = 1 mod p para qualquer menor a. Mas a deve ser um fator de p-1 para que isso seja possível, e qualquer múltiplo de a com essa propriedade também terá essa propriedade, portanto, precisamos verificar apenas que g ^ ((p-1) / q)! = 1 mod p para todos os fatores primos q de p-1. Então, verificamos todos os números g em ordem crescente até encontrarmos um que funcione.

Explicação:

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
fonte
Pretty awesome!
Seu código executa a fatoração?
@Lembik Sim (a PtQparte).
Erik the Outgolfer
5

Mathematica, 52 bytes

Inspirado pela resposta de isaacg .

1//.i_/;PowerMod[i,Divisors[#-1],#]~Count~1!=1:>i+1&
alefalpha
fonte
-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
fonte
11
Isso não está resolvendo o problema certo. Seu código deve, por exemplo, receber uma entrada e fornecer uma saída.
11
Além disso, esse código não é um jogo de golfe. O código de golfe precisa ser o mais curto possível, para que você possa remover o texto de entrada e os espaços ao redor de sinais de igual e assim por diante.
precisa saber é o seguinte
3
@ComradeSparklePony Eu acho que o primeiro problema que não está resolvendo o problema direito deve ser abordados em primeiro lugar :)