cyphen156
알고리듬#2 소수판정법(primarity Test) 본문
소수(Prime Number)를 찾는 방법은 단순하지만 시간이 오래걸린다.
우선 소수란 1을 제외한 어떤 양의 정수가 약수를 1과 자기 자신만을 갖는 수를 말한다.
2, 3, 5, 7, 11, 13 ... 등이 소수다. 보통 제곱근 판정법이나 가장 효율적이라고 알려진 에라토스테네스의 체를 알고리즘으로사용한다.
본 글에서는 아래로 갈수록 효율적인 방법들을 소개한다.
결정론적 방법
확실하게 소수인지 아닌지를 판단하는 방법 결과가 명확하지만 연산 시간이 길어진다.
일반적인 소수판정법
가장 통상적인 방법은 2부터 시작해서 입력값의 전 까지 모두 나눠보고, 나머지가 존재하는지를 확인하는 방법이다.
이것은 이전글에서 소개한 방법과 동일하게 절반까지만 확인하는 방법 또한 존재한다.
소수판정법_native.C
// 일반적인 소수판정법(Naive Method)
void naiveMethod(int input)
{
for (int i = 2; i < input; ++i) {
if (input % i == 0) // 나머지가 0이면 약분된다.
{
printf("소수가 아닙니다.");
return;
}
}
printf("소수입니다.");
}
// 절반까지만 확인하기
void halfNativeMethod(int input)
{
for (int i = 2; i <= input/2; ++i) { // i check조건이 1/2배
if (input % i == 0) // 나머지가 0이면 약분된다.
{
printf("소수가 아닙니다.");
return;
}
}
printf("소수입니다.");
}제곱근 판정법
약수구하는 것과 마찬가지로 소수판정 또한 제곱근까지만 연산을 수행해보면 된다.
이는 input이 소수가 아닌 경우, 즉 input이 어떤 수 a와 b의 곱으로 표현될 때, a와 b 중 적어도 하나는 input의 제곱근 이하라는 수학적 성질에 기반합니다.
소수판정법_sqrt.C
// 제곱근 판정법
#include <math.h>
void sqrtMethod(int input)
{
for (int i = 2; i <= sqrt(input); ++i) {
if (input % i == 0) // 나머지가 0이면 약분된다.
{
printf("소수가 아닙니다.");
return;
}
}
printf("소수입니다.");
}AKS 소수 판정법 (AKS Primality Test)
소수 판별이 다항시간(N, N**2, N**3 ... )내에 이루어진다는 것을 보장하는 것을 인정받은 최초의 알고리즘이다.
다항식의 합동식과 페르마의 소정리 확장이라는 수학적 원리에 근거하고 있으며, 소수 판별의 이론적 토대를 마련한 중요한 알고리즘이지만 식이 복잡하고, 코드로의 구현이 매우 어렵다. 주어진 수가 소수인지 아닌지를 판정할 때 사용한다.
검증과정은 다음과 같다
- 이 형태인지 검사하여 거듭제곱 수를 걸러냅니다.
- 과 관련하여 적절한 을 찾아 충분히 큰 주기를 가지도록 합니다.
- 모든 1≤ a ≤ root[ ϕ(r) ]logn에 대해, 와 가 에 대한 의 모듈로 합동인지 검사합니다.
에라토스테네스의 체 (Sieve of Eratosthenes)
입력값 N이하의 모든 자연수 중 소수가 몇개 존재하는지 판별하는 알고리즘
낮은 수부터 검증하여 이미 검사한 수의 배수에 대해서는 소수 판별을 건너뛰는 알고리즘이다.
초기값을 모두 소수로 판정하고, 낮은 수부터 순서대로 합성수 마스킹을 하기 때문에 반복 횟수는 N * loglogN이다
에라토스테네스의 체.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
// 에라토스테네스의 체
// 시간복잡도 = O(N*log*logN)
void sieveOfEratosthenes(int N)
{
// 기본 배열 초기화 할당생성, 0은 소수, 1은 합성수
bool* bzIsPrime = (bool*)calloc(N+1, sizeof(bool));
int cnt = 0;
// 초기값 설정 (0과 1은 소수가 아님)
bzIsPrime[0] = bzIsPrime[1] = true;
for (int i = 2; i <= N; ++i)
{
if(!bzIsPrime[i])
{
for (int j = i * 2; j <= N; j += i)
{
bzIsPrime[j] = true;
}
++cnt;
}
}
free(bzIsPrime);
}확률론적 방법
수가 커질수록 소수인지 아닌지를 판단하는데 걸리는 시간이 엄청나게 오래걸리기 때문에 고안된 방법
연산시간을 획기적으로 단축시킬 수 있지만 항상 올바른 결과를 보여준다는 보장을 받을 수 없는 통계 추정에 근거한 방법
오류의 가능성을 허용한 대신 단축된 시간이 존재하기 때문에 여러번의 반복 시행을 통해 결과를 검증하여 오류를 최소화한다. 이것은 큰 소수를 사용해 암호를 생성-해독하는 현대암호학에 있어서 핵심이된다.
페르마의 소수 판정법 (Fermat's Primality Test)
페르마의 소정리와 확장
- p가 소수이면, 모든 정수 a에 대해 a**p ≡ p로 나눈 나머지는 a이다.(합성수 판정의 원리의 역)
- 또는 p가 소수이고 a가 p의 배수가 아니라면(서로소), a**(p-1) ≡ p로 나눈 나머지는 1이다.
※ mod (modulo) : 나머지
페르마의 소정리는 판정 수가 소수일 때 항상 참이지만, 합성수라고 반드시 거짓은 아니다. -> 합성수도 소정리를 통해 소수판정받는 경우가 존재한다.
이에 대한 증명은 다음과 같다.
a = 2, p = 341일 때 a**341 = 341%2 = 1이다.
그렇다면 341은 소수인가? 답은 X이다. 341은 11의 배수 또는 31의 배수이다. 이와 같은 합성수를 유사 소수라고 한다.
밀러-라빈 소수 판정법 (Miller-Rabin Primality Test)
밀러-라빈 소수 판정법은 페르마 소수판정법에서의 유사소수문제를 해결해보고자 고안된 방법이다.
소수 p가 2가 아닌 소수일 때(홀수일 때) p-1 = d * 2 **r의 형태로 표현 할 수 있다.
ex) p == 11: 10 = 5*2**1, p == 17: 16 = 1 * 2**4
페르마의 소정리에서 a**p-1 ≡ 1(mod p)라 했었다.
이 식을 페르마의 소정리에 대입하면 a**(d*2**r) ≡ 1(mod d*2**r == p)가 된다.
그런데 0으로 나누는 연산은 식이 성립하지 않으므로 d != 0이 된다.
또한 d는 사실 반드시 홀수이다. 그 이유는 2**r에 있는데, 만약 d가 짝수라면 2로 나누어 r+1로 표현할 수 있기 때문이다.
밀러 라빈 판정법에서 다음 단계를 모두 만족하지 못한다면 해당 수는 반드시 합성수이다.
1. 주어진 수 p-1을 d * 2**r의 형태로 분해
2. Test T를 2 이상 p-2중 하나의 임의의 정수를 선택
3. 검증
- a**d ≡ 1(mod p)
- a**(d * 2**r) ≡ p-1(mod p)인 r이 0 이상 r-1이하의 어떤 정수에 의해 존재하는 경우, n은 소수일 수 있다.
+++
사실 갑자기 a**(d * 2**r) ≡ 1(mod p)가 갑자기 a**d ≡ 1(mod p)로 바뀌는 이유를 제대로 이해하지 못하고 있다가 이 방법이 모듈러 연산과 확률적 방법론이라는것을 깨달았다.
내 생각에 a**d % p == a**(d*2**r) = 1이 성립하려면 a**(2**r) = 1이 성립해야 하므로 반드시 r이 0이 되야 한다는 조건이 성립해야 밀러-라빈 판정법이 반드시 성립하게 된다. 하지만 이 수식이 반드시 성립하지 않아도 된다는 이론적 근거는 이 소수판정법이 결정론적 방법이 아닌 확률론적 방법론이라는 것에 있다.
특정 조건을 만족하는 경우 결론으로 도출될 가능성이 있다는 것이지, 반드시 결론으로 도출된다 가 아닌 판정식이기 때문이다.
다음은 chatGPT의 답변내용이다.
밀러-라빈 소수판정법.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
// 밀러-라빈 소수판정법
// 시간복잡도 모듈러 거듭제곱연산 = O(log d * 2**r) + 시행횟수O(k)
// 총 시간복잡도 = O(k * log d * 2**r)
// 모듈러 거듭제곱 함수
// gpt의 도움을 받았습니다
long long moduloPower(long long base, long long exponent, long long modulus) {
long long result = 1;
base %= modulus; // 최종 나머지 구해놓고
while (exponent > 0) {
if (exponent & 1) {
result = (result * base) % modulus;
}
exponent >>= 1; // 비트시프트 1/2 연산동작
base = (base * base) % modulus;
}
return result;
}
// 밀러 라빈 input == P, T = Test 횟수
void miller_RabinPrimarity(int input, int T) {
srand(time(NULL));
if (input <= 1 || input == 4) {
printf("%d는 소수가 아닙니다.\n", input);
return;
}
if (input <= 3) {
printf("%d는 소수입니다.\n", input);
return;
}
int r = 0;
long long d = input - 1;
while (d % 2 == 0) // input-1 => d * 2**r변환
{
d /= 2;
++r;
}
for (int i = 0; i < T; i++) {
int a = 2 + rand() % (input - 4); // 2와 input-4 사이의 랜덤 수 생성
long long x = moduloPower(a, d, input);
if (x == 1 || x == input - 1)
continue;
for (int r = 1; r < s; r++) {
x = moduloPower(x, 2, input);
if (x == input - 1)
break;
}
if (x != input - 1) {
printf("%d는 소수가 아닙니다.\n", input);
return;
}
}
printf("%d는 소수일 수 있습니다.\n");
}이에 대해서는 좀 더 쉬운 설명을 해놓은 블로그 글을 링크걸겠습니다.
밀러-라빈 소수판별법 (알고리즘) : 네이버 블로그 (naver.com)
밀러-라빈 소수판별법 (알고리즘)
안녕하세요. 오늘은 어려운 소수판별법에 대해서 알아볼 거예요. 밀러 라빈 소수판별법을 이용하기 위해서...
blog.naver.com
+++
밀러 - 라빈 소수판정법에 대해 3일정도 고민해봣지만 여전히 이해한 것 같지는 않다. 그냥 이런거 있구나 나중에 코드 긁어서 써먹어봐야겟다 정도의 느낌만 가지고 있으면 될 것 같다. 암호학을 사용하지 않는다면 현실적으로는 에라토스테네스의 체 정도만 사용할 것 같으니까.
해당 코드들은 제 깃허브에 있습니다. 유사코드는 제공하지 않습니다.
Workspace/알고리듬 at main · cyphen156/Workspace · GitHub
'컴퓨터공학 > 알고리듬' 카테고리의 다른 글
| 알고리듬#1+@ 이진 최대공약수(스테인의 알고리듬) (0) | 2024.02.15 |
|---|---|
| 알고리듬#1 최대공약수와 최소공배수 : 유클리드 알고리즘 (0) | 2024.02.14 |
| Chapter1 알고리즘 개요 (0) | 2022.09.16 |
