Найти число, которое генерирует все целые числа mod q

9

Рассмотрим целые числа по модулю qгде qпростое число, генератор - это любое целое число, 1 < x < qтак что оно x^1, x^2, ..., x^(q-1)охватывает все q-1целые числа между 1и q-1. Например, рассмотрим целые числа по модулю 7 (которые мы записываем как Z_7). Затем 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охватывает все значения 3, 2, 6, 4, 5, 1охватывает все целые числа, 1..6как требуется.

Задача состоит в том, чтобы написать код, который принимает вход nи выводит генератор для Z_n. Вы не можете использовать любую встроенную функцию или библиотеку, которая делает это за вас, конечно.

Единственным ограничением производительности вашего кода является то, что вы должны его протестировать до завершения n = 4257452468389.

Обратите внимание, что 2^n означает 2власть n. Это ^представляет возведение в степень.


источник
Хм ... 1 < x < qнамного облегчает задачу.
Эрик Outgolfer
@EriktheOutgolfer Я не уверен, что знаю, что вы имеете в виду? Это просто отличные целые числа, которые не равны 0 или 1.
Я имею в виду, что это проще, чем многие думают ... или, может быть, какой-то неактивный момент в PPCG.
Эрик Аутгольфер,
3
Но я думаю, что не нужно требовать, чтобы люди тестировали его до большого количества ... в основном, это просто ошибка памяти.
Эрик Outgolfer
@Lembik Есть ли случай, когда нет генератора для определенного числа? Некоторые тесты были бы хорошими.
Мистер Кскодер

Ответы:

13

Pyth, 16 15 байт

f-1m.^T/tQdQPtQ

Тестирование

Если p является входным значением, мы знаем, что g ^ (p-1) = 1 mod p, поэтому нам просто нужно проверить, что g ^ a! = 1 mod p для любого меньшего a. Но a должно быть коэффициентом p-1, чтобы это было возможно, и любой кратный a с этим свойством также будет иметь это свойство, поэтому нам нужно только проверить, что g ^ ((p-1) / q)! = 1 mod p для всех простых факторов q в p-1. Итак, мы проверяем все целые числа g в возрастающем порядке, пока не найдем то, которое работает.

Объяснение:

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
источник
Довольно круто!
Ваш код выполняет факторизацию?
@Lembik Это делает ( PtQчасть).
Эрик 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
Джон Брукфилдс
источник
1
Это не решает правильную проблему. Ваш код должен, например, взять один вход и дать один выход.
1
Кроме того, этот код вообще не в гольфе. Гольф-код должен быть как можно короче, чтобы вы могли удалить вводимый текст и пробелы вокруг знаков равенства и тому подобного.
Товарищ SparklePony
3
@ComradeSparklePony Я думаю, что первая проблема, которая не решает правильную проблему, должна быть сначала решена :)