Rozważ liczbę całkowitą modulo, q
gdzie q
jest liczbą pierwszą, generator jest dowolną liczbą całkowitą 1 < x < q
, która x^1, x^2, ..., x^(q-1)
obejmuje wszystkie q-1
liczby całkowite między 1
i 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 = 1
obejmuje wszystkie wartości 3, 2, 6, 4, 5, 1
obejmuje wszystkie liczby całkowite 1..6
zgodnie z wymaganiami.
Zadanie polega na napisaniu kodu, który pobiera dane wejściowe n
i 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 2
to moc n
. To ^
reprezentuje potęgowanie.
1 < x < q
sprawia, że wyzwanie jest o wiele łatwiejsze imo.Odpowiedzi:
Pyth,
1615 bajtówZestaw 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:
źródło
PtQ
część).Mathematica, 52 bajty
Zainspirowany odpowiedzią Isaacga .
źródło
źródło