Hwan. 001

코드 3 - 에라토스테네스의 체

 에라토스테네스의 체를 활용하여 미리 계산된 소수 여부 테이블을 참조하는 방식으로 개수 확인한다.

작은 범위에서는 위의 알고리즘 들과 비슷하거나 느리지만 큰 수의 범위로 가면 훨씬 빠른걸 볼 수 있다.

#include <iostream>

using namespace std;

typedef unsigned long long ll;

/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(ll m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (ll i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (ll j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

int main() {
    clock_t start, end;
    ll N, M;
    ll sum=0;

    start = clock();
    cin >> N >> M;
    bool* arr = Sieve_of_Eratosthenes(M);

    for (ll i = N; i <= M; i++) {
        if (arr[i]) {
            sum++;
        }
    }

    end = clock();
    float res = (float)(end - start) / CLOCKS_PER_SEC;
    cout << "" << N << " " << M << " " << sum << ", " << res << "ms" << endl;
    
    return 0;
}

참고

• 계산 범위의 조절로 100만에서 1억으로 향상되었지만 여전히 큰 수를 처리하기엔 어려움
• 에라토스테네스의 체를 활용할 경우 테이블 생성으로 인해 작은 수 범위에서는 더 오래걸리지만,
  큰 수에서는 훨씬 적은 시간이 걸림. (1억에서 100억 단위로 향상됨)
• Openssl을 활용한 더 큰 소수의 활용은 아래 블로그에 있다.

https://nitwit.tistory.com/17

** 아래 코드는 검증되지 않았음(개인 학습용), 문제점 발견 시 댓글로 적어주시면 감사하겠습니다.

1. 이론 찾아보기

• 이론과 원리에 대해서 설명
  https://kevin0960.tistory.com/entry/RSA-%EC%95%94%ED%98%B8%EC%99%80-%EA%B7%B8-%ED%95%B4%EB%8F%85

• 구글링 중 찾은 사이트. RSA뿐만 아니라 ECC, 디피헬만 등 다양한 알고리즘들이 설명되어 있다. (C로 구현된 예제가 있음)
  https://www.crocus.co.kr/1203

• 나무위키, 이론 이해를 위해 참고 (설명 좀 더 디테일)
  https://namu.wiki/w/RSA%20%EC%95%94%ED%98%B8%ED%99%94

• 빠른 모듈로 거듭 제곱법
  https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

2. 코드

#include "stdafx.h"
#include <ctype.h>
#include <math.h>

int gcd(int a, int b);
int RSA(int n, int m, int d); 

int main(){
    // 키 생성
    //int p = 13, q = 37;
    //int p = 11, q = 13;
    int p = 17, q = 13;

    int n, e, d, f;

    n = p * q;
    f = (p-1) * (q-1);

    // e 결정
    for (int i = 2; i < f; i++) {
        // 서로소 판단
        if (gcd(p - 1, i) == 1 && gcd(q - 1, i) == 1) {
            e = i;
            break;
        } 
    }

    //d 결정
    for (int i = 1; i < n; i++) {
        if ((1 + f * i) % e == 0) {
            d = (1 + f * i) / e; 
            break;
        }
    }

    // 소수에 따라 자동 계산된 변수 값
    printf("p\tq\tn\te\td\tf\n");
    printf("%d\t%d\t%d\t%d\t%d\t%d\n\n", p, q, n, e, d, f);

    // 암호화
    int msg = 'b';
    printf("msg : %c\n", msg);

    int c = RSA(n, msg, e);
    printf("c : %c\n", c);

    // 복호화
    int msg2 = RSA(n, c, d);
    printf("msg : %c\n", msg2);

    return 0;
}

// 암복호화를 위한 모듈로 연산을 수행 (n, d는 공개키/ 개인키, m은 메시지)
int RSA(int n, int m, int d) {
    int bin1[10] = { 0, };
    int tmp, j = 1;
    unsigned long long x_tmp = 1; 
    int x[10]; // m^2^0~9 mod n

    // 거듭 제곱법 구현을 위한 값 미리 저장
    x[0] = (unsigned long long)pow(m, 1) % n;
    for (int i = 1; i < 10; i++) {
        x[i] = (x[i - 1] * x[i - 1]) % n;
    }

    // 지수를 이진수로 변환 (구현 편의성을 위해 그냥 역으로 넣음) 
    for (int i = 0; d > 0; i++) {
        tmp = d % 2;
        d /= 2;
        bin1[i] = tmp;
    }

    // 이진수가 1일 떄만 미리 계산된 값 곱셈
    for (int i = 0; i < 10; i++) {
        if (bin1[i] == 1) {
            x_tmp *= x[i];
        }
    }

    return x_tmp % n; // 곱셈 합을 모듈로해서 반환
}

// 최대 공약수
int gcd(int a, int b) {
    int tmp, n;

    if (a<b) {
        tmp = a;
        a = b;
        b = tmp;
    }

    while (b != 0) {
        n = a % b;
        a = b;
        b = n;
    }

    return a;
}

3. 결과