밀러-라빈 소수 판별법 (Miller-Rabin Primalirty Test) 은, 주어진 자연수 $n$이 소수인지 판별하는 간단한 방법이다. 모든 소수에 대해서 성립하는 페르마의 소정리가 주어진 $n$에 대해서도 성립할 수 있는지 여부를 보고, $n$이 합성수인지, 아마도 소수일지 판단한다. 소수 $p$가 서로소인 $a$에 대해서 다음이 성립한다는 것이 페르마의 소정리이다. $a^{p-1} \equiv 1 \pmod p$ 이 정리가 주어진 $n$에 대해서 위배되는지를 다음과 같이 판단한다. 이 때, $a=1$인 경우는 항상 성립하므로, $a$는 $2 \leq p$에서 적당히 샘플링하여 진행한다. 먼저 $n$이 2의 배수인 경우, $n=2$인 경우에만 소수인 것은 자명하다. 다음은 $n$이 홀수인 경우이..
Let it GO. Go의 동시성 - Goroutines (1)
이번엔 Go의 동시성의 가장 기초가 되는 블록을 소개하려 한다. 이름하여 Goroutines, 고루틴이라고 하겠다. 아주 쉽다. Let it "go" // Declare your function func WhateverYouWant() {...} // Let it "Go" go WhateverYouWant() 고루틴이라 불리는 이것들은 마치 스레드, 프로세스 같은 것을 떠올리면 비슷한 느낌이지만, 엄연히 다르다. 이름이 다르지 않은가? 스레드와 같이 하나의 함수를 다른 고루틴들과 함께 동일한 주소 공간에서 실행한다. 단 스레드의 관리를 OS가 한다면, 고루틴은 Go런타임이 관리한다. 여기서 말하는 "관리"는 실행, 생성 등의 Scheduling, 이에 동반되는 Context Switch 그에 필요한 레지..