모든 정수 mod q를 생성하는 숫자 찾기 5, 3^6 = 729 mod 7 =

정수가 모듈로 고려 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. 그것은 ^지수를 나타냅니다.

답변

Pyth, 16 15 바이트

f-1m.^T/tQdQPtQ

테스트 스위트

p가 입력이면 g ^ (p-1) = 1 mod p임을 알 수 있으므로 더 작은 a에 대해 g ^ a! = 1 mod p인지 확인하면됩니다. 그러나 a는 p-1의 요소이어야하며, 그 속성을 가진 a의 배수도 그 속성을 가지므로 g ^ ((p-1) / q) 만 확인하면됩니다! p-1의 모든 소인수 q에 대해 1 mod p 그래서 우리는 모든 정수 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.

답변

매스 매 티카, 52 바이트

isaacg의 답변에서 영감을 얻었습니다 .

1//.i_/;PowerMod[i,Divisors[#-1],#]~Count~1!=1:>i+1&

답변

%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

답변