원시 뿌리를 계산하는 방법

콘텐츠

• 지침

원시 뿌리를 계산하는 것은 암호 기법과 수 이론에서 유용한 기술입니다. 숫자 "g"는 g mod p가 차수 계수 p-1을 갖는 경우 주어진 소수 p에 대한 원시 루트입니다. 즉, "g1 mod p", "g2 mod p"에서 "g (p-1) mod p"의 목록에는 1에서 (p-1)까지의 모든 정수가 포함됩니다. 원시 루트를 효율적으로 계산하는 알고리즘은 알려져 있지 않습니다. 가장 간단한 방법은 2에서 (p-1)까지 각 가능한 숫자를 시도하는 것입니다.

지침

모듈러 산술의 일반적인 사용법은 산술 계수 12를 사용하는 포인터 클럭입니다 (Hemera Technologies / PhotoObjects.net / Getty Images)

1. 5와 같이 소수 인 "p"를 선택하십시오. 소수는 자신과 1을 넘는 제수를 가지고 있지 않습니다. 예를 들어, "4/2 = 2"이기 때문에 4는 소수가 아니며 제수 중 하나는 2입니다.

2. 1에서 (p-1)까지의 각 정수 "n"에 대해 "2 ^ n mod p"를 계산하십시오. 예제를 사용하면 "p"는 5이고, "n ^ 2"는 "2 ^ n mod 5"이며 1에서 4까지입니다.

   2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1

3. 숫자 목록에 가능한 모든 5 개의 흔적이 있는지 확인하십시오. 목록 2, 4, 3 및 1은 한정적이므로 2는 나머지 5가있는 기본 루트입니다. 대신 목록이 2,1,4 및 1 (4에 대한 목록)이면 4가되지 않습니다 기본 루트는 번호 3이 목록에서 누락 되었기 때문에 발생합니다.

4. 5보다 작은 모든 정수에 대해 이전 단계를 반복하십시오. 3 번은 또한 나머지 5의 원시 뿌리이지만 4 가지가 아니다. 두 개와 다섯 개는 다섯 개를위한 근원적 인 뿌리입니다.