Hhan – 페이지 11 – Pseudorandom Things

How to compute greatest common divisor fast?

2016년 10월 26일2020년 5월 8일Hhan댓글 남기기

임의의 자연수는 소인수분해가 유일하고, 크기순서가 잘 주어져 있기 때문에, 다음과 같은 greatest common divisor를 정의할 수 있습니다.

(Definition)For two positive integer $a,b$ , the greatest common divisor $g$ is the largest positive number that divides $a,b$ without remainder.

짧게는 $\gcd(a,b)$ 로 씁니다. 다르게는 정수 $x,y$ 에 대하여 $ax+by$ 의 음아닌 최솟값으로 정의할 수도 있지요. 수학을 전공하지 않은 분들도 이를 계산하는 다음 유클리드 알고리즘은 한 번씩 교과서에서 보셨을 것 같습니다.

[Algorithm] ${\rm Euclidean-Gcd}(a,b)$
input : $a,b \in \mathbb{N}$
output : $\gcd(a,b)$

If $b>a$ , return ${\rm Euclidean-Gcd}(b,a)$ .
If $b=0$ , return $a$ .
Otherwise return ${\rm Euclidean-Gcd}(b,a\mod b)$ .

이 알고리즘은 시간이 얼마나 걸릴까요? $a,b$ 가 n bit size정도 되는 경우 $O(n^2)$ 정도의 시간복잡도를 가짐을 증명할 수 있습니다.

$\gcd(a,b)$ 의 계산방법은 유클리도 알고리즘이 가장 쉽고 좋은 방법일까요? 그렇다면 이런 글을 쓸 필요도 없고, 질문을 할 필요도 없었겠지요. 유클리드 알고리즘은 3번 과정에서 $a \mod b$ 의 연산을 필요로 하고, 이 연산 때문에 시간복잡도에 곱하기 항이 생기게 됩니다. 우리가 더하기나 빼기는 좀 잘하는데, 곱하기, 나누기는 글쎄요… 이를 피하기 위한 다음과 같은 알고리즘도 있습니다.

[Algorithm] ${\rm Binary-Gcd}(a,b)$
input : $a,b \in \mathbb{N}$
output : $\gcd(a,b)$

If $b>a$ , return ${\rm Binary-Gcd}(b,a)$ .
If $b=0$ , return $a$ .
If $a$ and $b$ are both even, retrun $2 \cdot {\rm Binary-Gcd}(a/2,b/2)$ .
If $a$ is even and $b$ is odd, return ${\rm Binary-Gcd}(a/2,b)$ .
If $a$ is odd and $b$ is even, return ${\rm Binary-Gcd}(a/2,b)$ .
Otherwise return ${\rm Binary-Gcd}((a-b)/2,b)$ .

Binary-gcd는 유클리드 알고리즘과 달리 나누기 연산을 피해갔습니다. Asymptotic time complexity는 같습니다만, 실제 알고리즘은 조금 더 빨리 작동합니다. 그렇다면 이게 최적의 알고리즘일까요? 물론 아닙니다!

계속 읽기 →

Mihăilescu’s Theorem

2016년 10월 25일2020년 5월 8일Hhan댓글 남기기

혹은 Catalan Conjecture라는 이름으로도 알려져 있습니다. 2002년에 Mihăilescu가 증명을 완료한 것으로 알고 있는데, 간단하게 말해 연속한 거듭제곱수는 8=2^3과 9=3^2밖에 없다는 정리입니다. 정확하게 말하면 다음과 같겠죠.

[Mihăilescu’s Theorem/Catalan’s Conjecture]

$x^m-y^n=1$ 을 만족하는 자연수 해 $(x,y,m,n)$ 은 $(3,2,2,3)$ 으로 유일하다.

이렇게 간단한 문제가 21세기가 되도록 풀리지 않았습니다! 사실 정수론의 큰 문제인 골드바흐의 추측이나 쌍둥이 소수 추측이 정말 수년 전에 크게 진전을 이룬 것이나 수학자들을 한참을 괴롭힌 페르마의 마지막 정리가 최근에 증명된 것을 생각하면.. 뭐 그럴수도 있겠다, 싶습니다.

이 정리의 증명에는 정말 많은 수학적 진보가 얽혀 있습니다(혹은 그런 것처럼 보입니다). 오일러가 $x^2-y^3 =1$ 의 해가 $(3,2)$ 로 유일한 것을 보이는 데에 타원곡선의 아이디어를 적용했고, $m,n$ 중 하나가 2인 나머지 경우는 Gaussian integer 등의 quadratic integer와 관계가 있습니다. $m=2$ 인 경우의 증명은 LLL lattice reduction으로 유명한 Hendrik Lenstra가 증명을 하기도 했다는군요. 증명을 마무리한 Mihăilescu는 이 Lenstra의 제자이기도 합니다. Mihăilescu가 마무리 한 나머지 경우는 cyclotomic extension과 관계가 있는 것 같은데, 아직 증명을 읽어보지는 않았습니다. 여유가 나면 읽어보겠는데.. 사실 그것보다 영어공부를 먼저 해야합니다…

여기서는 이와 관련된 올림피아드 스타일의 문제를 하나 소개해보겠습니다. 사실 저는 Mihăilescu’s Theorem의 보조정리로 알았는데, 실제로 그런지는 잘 모르겠습니다. 아마 거짓인 것 같은데..

$x^2-y^n=1$ 을 만족하는 자연수 $(x,y,n)$ 은 $y$ 은 $n>3$ 일 때 $y$ 의 소인수의 개수가 $n$ 의 소인수의 개수보다 2개 이상 더 많다.

증명은 재미있습니다. Mihăilescu’s Theorem에 따르면 해가 없으니 아무 것도 말하지 않는 명제지만. 올림피아드 스타일의 증명은 개인적으로 참 좋아하는 증명입니다. 나중에 혹시 기회가 되면 소개를 드리도록 하고.. Mihăilescu’s Theorem과 관계된 conjecture를 하나 소개하고 이 글을 마치도록 하죠.

임의의 자연수 $N$ 에 대하여 $x^m-y^n=N$ 의 자명하지 않은 자연수 해는 유한하다.

이는 cyclotomic extension 등을 직접적으로 적용하기 어려워 보이는데.. 쉽지 않은 문제인 것 같습니다.

Reference

Daems, Jeanine. “A cyclotomic proof of Catalan’s conjecture.” (2003): 21-46.

https://en.wikipedia.org/wiki/Catalan%27s_conjecture

중국집 ‘련’

2016년 10월 25일2020년 5월 8일Hhan댓글 남기기

아쉽게도 사진이 없습니다..

오늘 친구들과 가볍게 밥과 술을 하려 ‘련’을 방문했습니다. 원래는 일식집을 가려 했지만, 일본풍의 가게들 답게 월요일에는 다들 쉬나봅니다.

음식은 과일탕수육, 물만두, 군만두, 이과두주 1병, 칭따오(작은병) 3병, 사천 굴탕면, 깐풍기를 시켰습니다. 총 가격은 6만 5천원이여서 각각 16000원, 17000원을 냈습니다.

맛있었습니다. 이과두주는 56%의 도수라고 했는데, 그렇게 높은 도수의 술 중에서 이렇게 깔끔하게 마신 술은 굉장히 오랜만인 것 같습니다. 속은 조금 쓰렸습니다만.. 모든 음식과 술을 맛있게 먹었습니다. 위치가 약간 구석이라 아쉽지만, 괜찮습니다. 아주 좋습니다. 다음에는 사진을 찍어야겠습니다.

가격 : 식사 6~8000원, 요리 12000원~
영업시간 : 매일 11:30~22:00, 휴식시간 월~목 15:00~17:00