콘텐츠

• 단계
• 파트 1/3: 단순성 테스트
• 파트 2/3: 단순성 테스트의 작동 원리
• 3/3부: 중국 나머지 정리 사용
• 팁
• 뭐가 필요하세요

소수는 자기 자신과 1로만 나누어 떨어지는 숫자입니다. 다른 모든 숫자를 합성수라고 합니다. 숫자가 소수인지 확인하는 방법에는 여러 가지가 있으며 모두 고유한 장점과 단점이 있습니다. 한편으로 일부 방법은 매우 정확하지만 많은 수를 처리하는 경우 매우 복잡합니다. 반면에 훨씬 빠른 방법이 있지만 잘못된 결과를 초래할 수 있습니다. 적절한 방법의 선택은 작업 중인 숫자의 크기에 따라 다릅니다.

단계

파트 1/3: 단순성 테스트

메모: 모든 공식에서 NS 확인할 번호를 나타냅니다.

1. 1 제수의 열거. 나누기에 충분하다. NS 2에서 반올림된 값까지의 모든 소수(${ displaystyle { sqrt {n}}}$).
2. 2 페르마의 작은 정리. 경고: 때때로 테스트는 a의 모든 값에 대해서도 복합 숫자를 소수로 잘못 식별합니다.
   • 정수를 선택합시다 NS2 ≤ a ≤ n - 1이 되도록.
   • a(mod n) = a(mod n)이면 그 숫자는 아마도 소수일 것입니다. 평등이 만족되지 않으면 숫자 n은 합성수입니다.
   • 여러 값에 대해 주어진 같음 확인 NS테스트 중인 숫자가 실제로 소수일 가능성을 높입니다.
3. 3 밀러-라빈 테스트. 경고: 드물기는 하지만 a의 여러 값에 대해 테스트에서 합성 숫자를 소수로 잘못 식별하는 경우가 있습니다.
   • 다음과 같은 양 s와 d를 찾으십시오. ${ 디스플레이 스타일 n-1 = 2 ^ {s} * d}$.
   • 정수 선택 NS 범위 2 ≤ a ≤ n - 1.
   • a = +1(mod n) 또는 -1(mod n)이면 n은 아마도 소수일 것입니다. 이 경우 테스트 결과로 이동합니다. 평등이 유지되지 않으면 다음 단계로 이동합니다.
   • 답을 제곱하십시오(${ displaystyle a ^ {2d}}$). -1(mod n)을 얻으면 n은 아마도 소수일 것입니다. 이 경우 테스트 결과로 이동하십시오. 평등에 실패하면 (${ displaystyle a ^ {4d}}$ 등등) 까지 ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • 다른 숫자를 제곱한 후 어떤 단계에서 ${ 디스플레이 스타일 오후 1}$ (mod n), +1(mod n)을 얻었으므로 n은 합성수입니다. 만약에 ${ displaystyle a ^ {2 ^ {s-1} d} neq 오후 1}$ (mod n), n은 소수가 아닙니다.
   • 테스트 결과: n이 테스트를 통과하면 다른 값에 대해 반복합니다. NS자신감을 높이기 위해.

파트 2/3: 단순성 테스트의 작동 원리

1. 1 제수의 열거. 정의에 따르면 숫자 NS 2와 1과 자신을 제외한 다른 정수로 나눌 수 없는 경우에만 단순합니다. 위 공식을 사용하면 불필요한 단계를 제거하고 시간을 절약할 수 있습니다. 예를 들어 숫자가 3의 배수인지 확인한 후 9의 배수인지 확인할 필요가 없습니다.
   • floor(x) 함수는 x를 x보다 작거나 같은 가장 가까운 정수로 반올림합니다.
2. 2 모듈식 산술에 대해 알아봅니다. "x mod y" 연산(mod는 라틴어 "modulo", 즉 "module"의 약어)은 "x를 y로 나누고 나머지를 구한다"는 의미입니다. 즉, 모듈식 산술에서 특정 값에 도달하면 이를 기준 치수, 숫자는 다시 0으로 "돌아갑니다". 예를 들어 시계는 모듈 12로 카운트다운합니다. 시계는 10, 11 및 12시간을 표시한 다음 1로 돌아갑니다.
   • 많은 계산기에는 모드 키가 있습니다. 이 섹션의 끝 부분에서는 큰 숫자에 대해 이 함수를 수동으로 계산하는 방법을 보여줍니다.
3. 3 페르마의 작은 정리의 함정에 대해 알아보십시오. 테스트 조건이 충족되지 않은 모든 숫자는 합성이지만 나머지 숫자는 아마 간단합니다. 잘못된 결과를 피하려면 검색 NS "Carmichael number"(이 테스트를 만족하는 합성 수) 및 "Fermat pseudoprime number"(이 숫자는 일부 값에 대해서만 테스트 조건을 충족함) 목록에서 NS).
4. 4 편리한 경우 Miller-Rabin 검정을 사용합니다. 이 방법은 수동 계산에 다소 번거롭지만 컴퓨터 프로그램에서 자주 사용됩니다. Fermat의 방법보다 허용 가능한 속도와 적은 오류를 제공합니다. ¼ 이상의 값에 대해 계산이 수행되면 합성 수는 소수로 간주되지 않습니다. NS... 무작위로 다른 값을 선택하는 경우 NS 그리고 그들 모두에 대해 테스트가 긍정적인 결과를 줄 것이므로 상당히 높은 수준의 확신을 가지고 다음을 가정할 수 있습니다. NS 소수입니다.
5. 5 큰 수의 경우 모듈식 산술을 사용합니다. 편리한 모드 계산기가 없거나 계산기가 그렇게 큰 숫자를 처리하도록 설계되지 않은 경우 전력 속성과 모듈식 산술을 사용하여 계산을 더 쉽게 만드십시오. 아래는 에 대한 예입니다 ${ 디스플레이 스타일 3 ^ {50}}$ 모드 50:
   • 보다 편리한 형식으로 표현식을 다시 작성하십시오. ${ 표시 스타일(3 ^ {25} * 3 ^ {25})}$ mod 50. 수동 계산에는 추가 단순화가 필요할 수 있습니다.
   • ${ 표시 스타일(3 ^ {25} * 3 ^ {25})}$ 모드 50 = ${ 표시 스타일(3 ^ {25}}$ 모드 50 ${ 표시 스타일 * 3 ^ {25}}$ mod 50) mod 50. 여기에서 우리는 모듈러 곱셈의 속성을 고려했습니다.
   • ${ 디스플레이 스타일 3 ^ {25}}$ 모드 50 = 43.
   • ${ 표시 스타일(3 ^ {25}}$ 모드 50 ${ 표시 스타일 * 3 ^ {25}}$ 모드 50) 모드 50 = ${ 표시 스타일 (43 * 43)}$ 모드 50.
   • ${ 표시 스타일 = 1849}$ 모드 50.
   • ${ 표시 스타일 = 49}$.

3/3부: 중국 나머지 정리 사용

1. 1 두 개의 숫자를 선택하십시오. 숫자 중 하나는 합성이어야 하고 다른 하나는 단순성을 위해 테스트하려는 숫자여야 합니다.
   • 번호1 = 35
   • 숫자2 = 97
2. 2 0보다 크고 각각 숫자 Number1 및 Number2보다 작은 두 값을 선택하십시오. 이러한 값은 동일하지 않아야 합니다.
   • 값1 = 1
   • 값2 = 2
3. 3 Number1 및 Number2에 대한 MMI(수학적 승법 역수)를 계산합니다.
   • MMI 계산
     • MMI1 = 번호2 ^ -1 모드 번호1
     • MMI2 = 번호1 ^ -1 모드 번호2
   • 소수의 경우에만(이것은 합성수에 대한 숫자를 제공하지만 그의 MMI는 아님):
     • MMI1 = (번호2 ^ (번호1-2))% 번호1
     • MMI2 = (번호1 ^ (번호2-2))% 번호2
   • 예를 들어:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 log2 모듈까지 각 MMI에 대한 테이블을 만듭니다.
   • MMI1의 경우
     • F(1) = 숫자2% 숫자1 = 97% 35 = 27
     • F(2) = F(1) * F(1)% 숫자1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% 숫자1 = 29 * 29% 35 = 1
     • F(8) = F(4) * F(4)% 숫자1 = 1 * 1% 35 = 1
     • F(16) = F(8) * F(8)% 숫자1 = 1 * 1% 35 = 1
     • F(32) = F(16) * F(16)% 숫자1 = 1 * 1% 35 = 1
   • 짝수 1 - 2 계산
     • 35 -2 = 33(10001) 밑수 2
     • MMI1 = F(33) = F(32) * F(1) 모드 35
     • MMI1 = F (33) = 1 * 27 모드 35
     • MMI1 = 27
   • MMI2의 경우
     • F (1) = 숫자1% 숫자2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Number2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Number2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Number2 = 35 * 35 mod 97 = 61
     • F(16) = F(8) * F(8)% Number2 = 61 * 61 mod 97 = 35
     • F(32) = F(16) * F(16)% 숫자2 = 35 * 35 mod 97 = 61
     • F(64) = F(32) * F(32)% 숫자2 = 61 * 61 mod 97 = 35
     • F(128) = F(64) * F(64)% 숫자2 = 35 * 35 mod 97 = 61
   • 짝수 계산 2 - 2
     • 97 - 2 = 95 = (1011111) 밑수 2
     • MMI2 = (((((F(64) * F(16)% 97) * F(8)% 97) * F(4)% 97) * F(2)% 97) * F (1)% 97)
     • MMI2 = (((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 계산 (값1 * 숫자2 * MMI1 + 값2 * 숫자1 * MMI2)% (숫자1 * 숫자2)
   • 답 = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • 답 = (2619 + 4270)% 3395
   • 답 = 99
6. 6 Number1이 소수가 아닌지 확인
   • 계산(답변 - 값1)% 숫자1
   • 99 – 1 % 35 = 28
   • 28은 0보다 크므로 35는 소수가 아닙니다.
7. 7 Number2가 소수인지 확인하십시오.
   • 계산(답변 - 값2)% 숫자2
   • 99 – 2 % 97 = 0
   • 0은 0이므로 97은 소수일 가능성이 높습니다.
8. 8 1~7단계를 두 번 이상 반복합니다.
   • 7단계에서 0이 나오면:
     • Number1이 소수가 아니면 다른 Number1을 사용하십시오.
     • Number1이 소수이면 다른 Number1을 사용하십시오. 이 경우 6단계와 7단계에서 0을 얻어야 합니다.
     • 다른 의미 1과 의미 2를 사용합니다.
   • 7단계에서 지속적으로 0을 얻으면 2번이 소수일 가능성이 매우 높습니다.
   • Number1이 소수가 아니고 Number2가 Number1의 제수이면 1~7단계에서 오류가 발생할 수 있습니다. 설명된 방법은 두 숫자가 모두 소수인 모든 경우에 작동합니다.
   • 1단계부터 7단계까지를 반복해야 하는 이유는 1번과 2번이 소수가 아닌 경우에도 7단계에서 0이 되기 때문입니다(하나 또는 둘 다에 대해). 이것은 거의 발생하지 않습니다.다른 Number1(복합)을 선택하고 Number2가 소수가 아니면 7단계에서 Number2가 0과 같지 않습니다(Number1이 Number2의 제수인 경우를 제외하고 - 여기에서 소수는 7단계에서 항상 0과 같습니다).

팁

• 168에서 1000까지의 소수: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 1918 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 5, 293, 307, 311, 313, 3117, 313, 3117, , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 7, 467, 9, 4, 463, 7967, 4 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 6, 613, 617, 619, 631, 4 3641, 6 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 321,8 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 9183, 979, 9183,
• 무차별 대입 테스트는 큰 숫자로 작업할 때 지루한 테스트이지만 작은 숫자에는 매우 효율적입니다. 큰 수의 경우에도 작은 제수를 테스트한 다음 숫자의 단순성을 확인하는 보다 정교한 방법으로 이동합니다(작은 제수를 찾을 수 없는 경우).

뭐가 필요하세요

• 종이, 펜 또는 컴퓨터