Trouver un nombre qui génère tous les entiers mod q

9

Considérez les entiers modulo qqest premier, un générateur est n'importe quel entier de 1 < x < qsorte qu'il x^1, x^2, ..., x^(q-1)couvre tous q-1les entiers entre 1et q-1. Par exemple, considérons les entiers modulo 7 (que nous écrivons comme Z_7). Puis 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 = 1couvre toutes les valeurs 3, 2, 6, 4, 5, 1couvre tous les entiers 1..6comme requis.

La tâche consiste à écrire du code qui prend une entrée net génère un générateur pour Z_n. Bien entendu, vous ne pouvez pas utiliser de bibliothèque ou de bibliothèque intégrée qui le fasse pour vous.

La seule restriction sur les performances de votre code est que vous devez l'avoir testé jusqu'à son terme n = 4257452468389.

Notez que cela 2^n signifie 2la puissance de n. Cela ^représente l'exponentiation.


la source
Hmm ... 1 < x < qrend le défi beaucoup plus facile imo.
Erik the Outgolfer le
@EriktheOutgolfer Je ne suis pas sûr de savoir ce que tu veux dire? Ce ne sont que tous les entiers distincts qui ne sont ni 0 ni 1.
Je veux dire que c'est plus facile que ce que beaucoup pensent probablement ... ou peut-être un moment inactif sur PPCG.
Erik the Outgolfer le
3
Mais je pense qu'il n'est pas nécessaire d'obliger les gens à le tester jusqu'à son terme ... en gros, tio serait juste une erreur de mémoire.
Erik the Outgolfer le
@Lembik Y a-t-il des cas où il n'y a pas de générateur pour un certain nombre? Certains cas de test seraient bons.
M. Xcoder

Réponses:

13

Pyth, 16 15 octets

f-1m.^T/tQdQPtQ

Suite de tests

Si p est l'entrée, nous savons que g ^ (p-1) = 1 mod p, il nous suffit donc de vérifier que g ^ a! = 1 mod p pour tout plus petit a. Mais a doit être un facteur de p-1 pour que cela soit possible, et tout multiple d'un a avec cette propriété aura également cette propriété, nous n'avons donc qu'à vérifier que g ^ ((p-1) / q)! = 1 mod p pour tous les facteurs premiers q de p-1. Donc, nous vérifions tous les entiers g dans l'ordre croissant jusqu'à ce que nous trouvions celui qui fonctionne.

Explication:

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
la source
Plutot cool!
Votre code effectue-t-il la factorisation?
@Lembik C'est le cas (la PtQpartie).
Erik the Outgolfer
5

Mathematica, 52 octets

Inspiré par la réponse d' Isaacg .

1//.i_/;PowerMod[i,Divisors[#-1],#]~Count~1!=1:>i+1&
alephalpha
la source
-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
la source
1
Cela ne résout pas le bon problème. Votre code doit, par exemple, prendre une entrée et donner une sortie.
1
De plus, ce code n'est pas du tout joué au golf. Le code golfé doit être aussi court que possible, afin que vous puissiez supprimer le texte d'entrée et les espaces autour des signes égaux, etc.
Camarade SparklePony le
3
@ComradeSparklePony Je pense que le premier problème qui ne résout pas le bon problème devrait être abordé en premier :)