The probability that two random integers are relatively prime.

영어공부를 하다 심심해서 오랜만에 기억나는 다음 정리를 다시 한번 증명해봤습니다.

(Theorem) The probability that two random positive integer are relatively prime is 1/\zeta(2)=6/\pi^2.

아래의 증명은 (아마도) Niven책[1]에서 처음 본 것 같습니다. 조금 다르더라도 이런 방식의 정의와 증명을 처음 본 건 Niven이 맞으니까 뭐 저기서 인용했다고 칩시다.

The probability that two random integers are relatively prime. 더보기

TEPS

Nowadays I’m studying English to achieve high score in TEPS, authorized English test in Korea. I really want to write about quantum computations, Shor’s algorithms, and other fascinating topics, but I cannot because I memorized words and grammar, solve and read too many problems in English everyday…

 

영어로 글을 쓰긴 참 힘들군요. 아무래도 한글이 답인 것 같습니다..
내일 당장 텝스 시험인데, 일단 700점이나 넘었으면 좋겠네요. 800점을 넘기는게 최종 목표긴 합니다만..

Quantum computation and Shor’s factorization algorithm (0)

Shor의 Factorization algorithm은 굉장히 유명한 논문입니다 [1]. classical 컴퓨터로는 어렵다고 믿어지는 소인수분해 문제를 양자컴퓨터로 다항식시간에, 그것도 굉장히 낮은 시간복잡도로 해결해버린 놀라운 알고리즘이거든요. 이 알고리즘에 따르면 양자컴퓨터가 현실화되면 RSA나 기타등등 소인수분해가 어렵다고 가정하고 시작하는 많은 암호논문이 종이쪼가리가 되어버립니다!! 이중에서는 실제로 쓰는 시스템도 많은데 말이죠..

최근에 미국 국가안보국(NSA, National Security Agency)에서는 대 양자컴퓨터 암호(post-quantum cryptography)를 만들어야 한다고 경고했고, NIST(National Institute of Standards and Technology)에서는 post-quantum cryptography의 표준을 공모했습니다 [2].

현실에서는 문제가 좀  있습니다. 물리적으로 큰 메모리를 갖는 양자컴퓨터를 만들기가 힘들거든요. 절대 0도에 가까워져야 하고.. 물리는 잘 모르지만 하여튼 힘들다고 합니다.
자세하게는 classical computer의 bit에 해당하는 quantum computer의 대상을 qubit라고 부르는데, 이 qubit를 100개 갖는 컴퓨터를 만드는 것도 힘듭니다. 구글이 2017년 말까지 50 qubit의 quantum computer를 만들겠다고 발표했는데 [3], classical computer의 것과 비교하면 애들 장난같죠. 훨씬 큰 qubit를 갖는 D-wave라는 물건이 있긴 한데, 이건 정확하게는 quantum computer는 아니고 quantum annealing이라는 global minimum을 찾는 알고리즘에 특화된 컴퓨터라고 합니다 [4].
이에 더해 소인수분해는 아예 4qubit정도만 사용하는 선에서만 성공했다고 하고, 심지어 shor의 알고리즘이 아니라 qubit를 적게 쓰는 다른 알고리즘을 통해서 했다는 말도 들었습니다.
즉 양자컴퓨터에서는 시간복잡도뿐만 아니라 공간복잡도도 엄청나게 큰 문제라는 거죠.

 

소인수분해에 관한 Shor의 결과는 다음과 같습니다.

[Shor] There is a quantum algorithm to factorize $n$, which uses \mathcal O(\log n) space and \widetilde{\mathcal O}(\log ^3 n) time.

Shor의 논문이 엄청 어려운 편은 아닌데, 개념이 생소하다보니 읽다보면 이게 대체 맞는 소리인가 헷갈리곤 합니다. 다음 글부터는 그 디테일들을 확인해 봅시다! 언제 올라올지는 모르겠지만요..

 

[1] Shor, Peter W. “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.” SIAM review 41.2 (1999): 303-332.

[2] NSA says it “must act now”, MIT technology report, Feb. 2016.
https://www.technologyreview.com/s/600715/nsa-says-it-must-act-now-against-the-quantum-computing-threat/

[3] Google’s quantum dream may be just around the corner, MIT technology report, Aug. 2016.
https://www.technologyreview.com/s/602283/googles-quantum-dream-may-be-just-around-the-corner/

[4] D-wave system, wikipedia.
https://en.wikipedia.org/wiki/D-Wave_Systems

 

A toy problem

얼마전에 (크리스마스날!) 학원 수업 대타를 하루 했습니다. 이제 다시는 학원수업을 하지 않을줄 알았는데.. 오랜만에 올림피아드 문제좀 풀어볼까 하고 잠시 시간을 내어 수업을 했습니다. 그런데 그 전후로 너무 바빠서 생각보다 힘들었습니다..

그날 수업을 위해 준비한 문제중 다음과 같은 문제가 있습니다.

There are n positive integer a_1,\cdots , a_n, need not to be different, in the blackboard. In each “step”, we can erase two numbers a,b  and write greatest common divisor and least common multiple of a,b in the blackboard. The “meaningful step” is a step which change the set of integers in the blackboard.

  1. Prove that the possible number of meaningful steps is finite.
  2. Regardless of the way we do steps, if we cannot do any meaningful steps, the possible set of integers in the blackboard is  unique.

원래 문제는 1번만 있었는데, 너무 쉬워서 내지 말까 고민했었습니다. 근데 왠지 더이상 할 수 없는 상태가 유일하지 않을까 싶어서 이리저리 고민해보니 적당한 난이도로 해결이 되고, 재미있는 toy problem인 것 같아서 출제했습니다. 풀이는 비밀로 ㅎㅎ.

Quantum computation semiar

오늘(27일) 학교에서 Quantum computation과 Shor’s factorization algorithm에 대해 세미나를 진행했습니다. 연사는 저였습니다 후후.

Shor의 논문만 읽으면 헷갈리는 부분들이 많은데, 다른 책과 위키 등을 참고해가면서 그런 부분들을 채워서 발표했습니다. 왜 bit operation에 대응대는 무언가가 아닌 quantum gate에 대해서만 논의하는지, 어떤 quantum gate가 computational한 건지, 그리고 몇 가지 내용이 대체 왜 들어있는 것인지 굉장히 고민이 많았는데, 이것 저것 찾아가면서 어떻게든 채워서 했습니다.

다행히도 세미나에서는 제가 이해한 것에 반하는 질문 등은 나오지 않았습니다. 과연 제가 이해한 게 맞을까요..? (매번 그렇듯)세부적인 내용은 추후 포스팅 하겠습니다. 이건 그래도 포스팅하고싶은 욕구가 강해서, 아마 곧 할 수 있을 것 같습니다! 아마도요..

요즘의 관심사

요즘은 시험기간이여서 글도 많이 쓰지 못하고, 다른 공부도 거의 하지 못합니다. 기말이 있는 과목은 복소다양체(Complex Manifold)와 대수기하학 개론(Introduction to Algebraic Geometry)입니다. 대수기하학 개론은 Take-home exam으로 시험 문제를 일주일간 푸는 시험이고, 복소다양체는 기말 과제로 각자가 정한 주제로 발표하는 시험입니다.

대수기하학 개론에 대해서는 별로 할 말이 없습니다. 재미있긴 한 과목이지만 요즘 다루는 툴이나 이론들이 그렇게 끌리지는 않아서요.. 그래도 Grobner basis는 참 재미있는 툴인 것 같고, 대수기하 과목이 열리면 듣긴 할겁니다 ㅎㅎ

복소다양체의 기말 과제로는 Kenkichi Iwasawa의 “Sheaves for Algebraic Number Fields”를 읽고 발표하기로 결정했는데.. 좀 웃깁니다. 복소다양체보다 정수론을 매일 공부하고 있습니다. 정확하게는 Weiss의 Algebraic Number Theory 책을 읽고 있는데, 지난번의 포스팅도 그 책에서 발견하고 올린겁니다 ㅎㅎ.
재미는 있습니다만 결국 복소다양체에 대해서는 하나도 배우지 못할 것 같습니다.. 수업도 많이 빠졌고.. TeX파일로 정리해서 파일을 제출하고 발표하는 과제이기에 그 파일을 여기 올리거나, 혹은 전후 문제들과 내용들을 간략하게 정리해서 이 블로그에 올릴 수도 있을 것 같습니다.

시험이 끝나고는 Quantum Computation에 대해 공부해보려고 합니다.
일전에 P. Shor의 Quantum polytime에 Factorization과 Discrete Logarithm을 푸는 논문을 예전에 읽은 적이 있는데, 그 때는 대충 이상한 점들도 넘어갔었습니다. 최근에 이것저것 찾아보면서 다시 읽었더니 빈 곳들이 메꿔지는 느낌입니다. 정말로 양자컴퓨터가 실현화 가능할지는 의문이긴 하지만, 그래도 꽤나 재미있는 주제라 약간은 공부해보려 합니다.

-끝-

Asiacrypt 2016

kakaotalk_20161208_131725316

베트남에서 학회 Asiacrypt 2016에 참여하고 있습니다. IACR이라는 reseach group(?)에서 영향을 많이 주나본데, 그걸 이용해서 재미있는 디자인을 했습니다.

 

kakaotalk_20161208_131719777

이 사진은 참 잘찍은 것 같습니다. 하지만 베트남은 사실 그렇게 예쁘지 않습니다.. 물은 꽤나 더러운 편이고, 공기는 굉장히 안좋습니다. 인도도 별로 없어서 걸어다니기도 꽤 힘듭니다. 호텔은 싼 편에 묵을 수 있어서 좋습니다.

 

kakaotalk_20161208_131721075

베트남 사람들은 참 야채를 좋아합니다. 하지만 저는 고수의 맛을 도저히 버틸수가 없습니다.. 먹기는 어떻게 꾸역꾸역 먹는데, 그 맛이 나면 도저히 밥같지가 않습니다. 많이 빼먹습니다.. 야채 말고도 쓰는 소스들의 향도 되게 싫어서 식사가 참 안맞습니다. 쌀국수를 좋아하지 않아서 친구들에게는 별로 안먹겠다고 했는데, 먹을게 이거밖에 없습니다…

 

kakaotalk_20161208_131723659

이 나라는 오토바이를 타고 다니는 사람이 정말 정말 정말 정말로 많습니다. 거의 신발인 것 같습니다. 이 나라에서는 오토바이가 없는 저는 신발없이 걸어다니는 이상한 놈입니다. 정말 놀라운게 이 사람들은 신호도 잘 안지키고 중앙선도 잘 안지키는데, 사고를 아직 한번도 못봤습니다. 교차하는 두 개의 오토바이 행렬이 멈추지않고 슝슝 지나가기도 합니다. 놀라운 나라입니다. 아무래도 공기가 안좋은 것은 오토바이때문인 것 같습니다.

 

kakaotalk_20161208_131722330

이쁜거는 그래도 가끔 팝니다. 그치만 별로 사고싶지는 않고.. 돌아갈 때에는 커피정도나 사서 돌아갈까 생각중입니다. 베트남은 커피가 유명하다고 하더군요.
kakaotalk_20161208_131718347

여기서 준 공책은 마음에 듭니다. 보통 학회에서는 과학실험 보고서를 써야할 것 같은 투박한 연습지들을 주곤 하는데, 이건 작은 공책입니다.

 

연구하는 것들을 포스팅하고 싶은데, 그 전에 lattice에 관해서 올려야 이것들이 설명이 가능합니다. 너무 귀찮습니다.. 요증 생각하는 문제는

1)주어진 적당한 number field와 그의 ring of integer에 대해 (적당히 주어진 norm에 대해) norm이 작은 a,b가 고정되어 있고, h=a/b를 알고 있을 때 (a,b)의 쌍이나 작은 s에 대해 (sa,sb)의 쌍을 구하는 문제가 있습니다. 정수에서의 rational reconstruction의 일반화이고, NTRU문제라고 부릅니다.

2)비슷하게, 주어진 number field와 ring of integer에 대해 어떤 g가 고정되어 있습니다. 이 때 g의 배수가 많이 주어질 때, g를 구하는 문제가 있습니다. 좀 더 정확하게는 ideal이 주어져 있을 때, 그 ideal이 principal인지 판단하고, 만약 principal이라면 generator를 구하는 문제입니다. principal ideal problem이라고 부릅니다. 어찌보면 정수에서의 greatest common divisor문제의 일반화이기도 합니다.

이 두 문제인데, 그 방법을 설명드리기는 참 힘듭니다. 자세한 것들은 다음 기회에..