×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,791,955명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

선형 합동 생성기(Linear Congruential Generator, LCG)는 유사 난수 생성기(의사 난수 생성기)라 하며, 간단한 난수를 생성하기 위해 이용할 수 있다.


이때 LCG는 다음과 같은 점화식으로 정의 할 수 있다.


Xn+1 = (a*Xn + c) % m

(이 방식을 통해 C의 rand, srand가 형성된다.)


이때 각각의 변수들은 다음과 같은 조건을 가진다.


1. m > 0

2. 0 < a < m  

3. 0 < c < m

4. 0<= X0 < m (X의 초기값)


선형 합동생성기를 이용하면 항상 주기가 생긴다.


하지만 주기가 매우 길다면 이 의사 난수 생성기에 의해 생긴 수들은 난수라고 할 수 있다.

(이때문에 유사 난수, 의사 난수 라고 칭한다.)


이때 주기는 최대 m임은 자명하다.(m이 10이라 치면 난수의 주기가 최대 0,1,2,3,4,5,6,...,9 같은 경우가 나오는 경우)


따라서 선형 합동생성기를 이용한 암호학은 쉽게 공격자가 해독하여 공격할 수 있기에 암호학에서는 사용하지 않는다.

(마지막으로 생성된 난수를 알면 그 뒤에 만들어질 난수를 모두 예측 할 수 있게 된다.)


이때 주기를 최대로 하기위해서는 다음과 같은 필요충분 조건이 필요하다.


1. c 와 m이 서로소여야 한다.

2. a - 1이 m의 모든 소인수로 나누어져야 한다.

3. m이 4의 배수일 경우, a - 1도 4의 배수여야 한다.



아래 소스코드는 최대 주기를 갖지 않지만 임의의 값을 변수에 대입하여 얻어낸 난수이다.


그리고 아래에서 cout에서 이용된 "\t\n"[!(i % 10)];은 http://www.crocus.co.kr/1143?category=116609 를 참고하자.





소스 코드 : 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main()
{
    int x = 13, a = 213, c = 1717, m = << 20;
 
    cout << "LCG 의사 난수 생성기" << endl;
 
    for (int i = 1; i <= 100; i++)
    {
        cout << x << "\t\n"[!(i % 10)];
        x = (a*+ c) % m;
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus







반응형

'Applied > 알고리즘' 카테고리의 다른 글

[STL] qsort 구현  (0) 2018.02.02
해시 테이블(Hash Table)  (0) 2018.01.31
하노이 탑 K번째 찾기  (2) 2018.01.26
나이트 투어 알고리즘(Warnsdorff's Rule)  (5) 2018.01.13
MCMF(Minimum Cost Maximum Flow) 알고리즘  (0) 2017.12.05