Znajdź liczbę, która generuje wszystkie liczby całkowite mod q

9

Rozważ liczbę całkowitą modulo, qgdzie qjest liczbą pierwszą, generator jest dowolną liczbą całkowitą 1 < x < q, która x^1, x^2, ..., x^(q-1)obejmuje wszystkie q-1liczby całkowite między 1i q-1. Weźmy na przykład liczby całkowite modulo 7 (które piszemy jako Z_7). Następnie 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 = 1obejmuje wszystkie wartości 3, 2, 6, 4, 5, 1obejmuje wszystkie liczby całkowite 1..6zgodnie z wymaganiami.

Zadanie polega na napisaniu kodu, który pobiera dane wejściowe ni generuje generator Z_n. Oczywiście nie możesz użyć żadnej wbudowanej biblioteki ani biblioteki, która to zrobi.

Jedynym ograniczeniem wydajności kodu jest to, że musisz go przetestować do końca n = 4257452468389.

Zauważ, że 2^n oznacza 2to moc n. To ^reprezentuje potęgowanie.


źródło
Hmm ... 1 < x < qsprawia, że ​​wyzwanie jest o wiele łatwiejsze imo.
Erik the Outgolfer
@EriktheOutgolfer Nie jestem pewien, czy wiem, co masz na myśli? To tylko wszystkie różne liczby całkowite, które nie są 0 ani 1.
Mam na myśli, że jest to łatwiejsze niż to, co wielu myśli, a może jakiś nieaktywny moment na PPCG.
Erik the Outgolfer
3
Ale myślę, że wymaganie od ludzi przetestowania go do ukończenia na dużą liczbę jest niepotrzebne ... w zasadzie tio spowodowałoby tylko błąd pamięci.
Erik the Outgolfer
@Lembik Czy istnieje przypadek, w którym nie ma generatora dla określonej liczby? Niektóre przypadki testowe byłyby dobre.
Pan Xcoder,

Odpowiedzi:

13

Pyth, 16 15 bajtów

f-1m.^T/tQdQPtQ

Zestaw testowy

Jeśli p jest wejściem, wiemy, że g ^ (p-1) = 1 mod p, więc musimy tylko sprawdzić, czy g ^ a! = 1 mod p dla każdego mniejszego a. Ale a musi być współczynnikiem p-1, aby było to możliwe, a każda wielokrotność a z tą właściwością również będzie miała tę właściwość, więc musimy tylko sprawdzić, czy g ^ ((p-1) / q)! = 1 mod p dla wszystkich czynników pierwszych q p-1. Tak więc sprawdzamy wszystkie liczby całkowite g w kolejności rosnącej, aż znajdziemy taką, która działa.

Wyjaśnienie:

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
źródło
Dość niesamowite!
Czy Twój kod dokonuje faktoryzacji?
@Lembik To robi ( PtQczęść).
Erik the Outgolfer
5

Mathematica, 52 bajty

Zainspirowany odpowiedzią Isaacga .

1//.i_/;PowerMod[i,Divisors[#-1],#]~Count~1!=1:>i+1&
alephalpha
źródło
-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
źródło
1
To nie rozwiązuje właściwego problemu. Twój kod powinien na przykład przyjąć jedno wejście i dać jedno wyjście.
1
Ponadto ten kod nie jest w ogóle golfem. Kod w golfa musi być możliwie jak najkrótszy, aby można było usunąć tekst wejściowy i spacje wokół znaków równości i tym podobne.
Towarzysz SparklePony,
3
@ComradeSparklePony Myślę, że pierwszy problem, który nie rozwiązuje właściwego problemu, powinien zostać rozwiązany w pierwszej kolejności :)