정수가 모듈로 고려 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.
답변
답변
%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