수학자 John Rainwater

간만에 futility closet 블로그[1]를 보니 재미있는 이야기가 있다.

John Rainwater라는 수학자는 현재까지 10편의 논문을 쓰고, 가장 많이 인용된 것은 19회에 이르지만, 이 사람은 실존 인물이 아니다.[2]

1952년 워싱턴 대학의 Nick Massey라는 수학과 대학원생 학생은 전산상의 실수로 빈 학생증을 받게 되었는데, 그 당시 바깥에서 비가 내리고 있어서 Rainwater라는 가공의 인물을 만들었다고 한다. ㅋㅋㅋ 이 가상의 인물의 설정에 다른 학생들도 동참하여, 숙제도 꼬박꼬박 제출하였는데, 결국 그 학기 중간고사 시험을 칠 때 Arsove 교수에게 발각이 된 모양이다. Arsove 교수는 John Rainwater의 이름으로 발송한 폭발하는 만년필-_-을 받았어도, 대인배스럽게 그냥 넘어가준 모양이다. ㅋㅋ

수 년 후에 수학과 대학원생 그룹이 American Mathematical Monthly 문제들을 풀면서 John Rainwater의 이름으로 풀이를 송신한 모양인데, 이를 보고 MAA 측에서 MAA의 회원으로 가입하기를 권유했다고 한다. 당시에는 다른 회원 두 명의 추천이 있어야 했는데, 가장 이상적인 추천인으로 당시 수학과 학장이자 MAA 회장인 Carl Allendoerfer의 추천을 받는 것이 가장 좋았지만, Allendoerfer는 농담을 좋아하는 성격이 아니었던 것 같다. ㅋㅋㅋㅋ 그리하여 바쁘신 학장 대신에 학장의 비서를 설득하여 문서 위조-_-를 감행했다고 한다. ㅋㅋㅋ

보니까 한동안 John Rainwater의 이름으로 논문도 나오고, 그의 이름을 단 세미나도 개최되었던 모양인데, 일부 논문은 실제 저자가 누구인지 모호한 채로 남아있는 듯 하다.

다른 학술 분야는 모르겠는데, 익명 수학자 집단이 가상의 인물로 논문이나 책을 쓰는 사례는 니콜라 부르바키와 같은 다른 사례도 있으니, 아주 놀라운 이야기는 아니다. ㅎㅎ 그러나 재미로 인물을 만들어서 그런 설정(?)에 집단적으로 동참하고, 또 그런 전통이 이어지는 걸 보면, 이 사람들이 나름 유쾌한 사람들인 것 같긴 하다. ㅎㅎㅎ

 


[1] The Empty Set (futilitycloset.com)
[2] Biography of John Rainwater (at.yorku.ca)

저전력을 위한 이차방정식의 근의 공식을 개선하기

John D. Cook 선생의 블로그는 한동안 안 보고 있었는데, 해커뉴스[1]에서 John D. Cook 선생의 흥미로운 블로그 글[2]이 화제가 되고 있어 포스팅함. ㅋ

중학생들에게 ‘암기’라는 심리적 장벽-_-을 가져오기에 충분한 이차방정식 ax^2 + bx+c=0의 근의 공식은 잘 알려진 대로 다음과 같다.

\displaystyle x = \frac{-b \pm \sqrt{b^2 -4ac}}{2a} …… (1)

근데 실제 프로그래밍에서 플로팅 포인트 오차 때문에 이 공식을 그대로 쓰면 b가 매우 큰 경우에는 오차가 꽤 커진다고 한다. John D. Cook 선생은 파이썬으로 예시를 보여주고 있지만, 본인은 한국 수학 교사들의 영원한 동반자-_-라 할 수 있는 아래 한/글에 내장된 한글 스크립트로 구현해 보았다. ㅋㅋ

function OnScriptMacro_test12()
{
	var temp = quadratic(1, Math.pow(10,8), 1);

	HAction.GetDefault("InsertText", HParameterSet.HInsertText.HSet);
	HParameterSet.HInsertText.Text = "Answer : " + temp[0] + ", " + temp[1];
	HAction.Execute("InsertText", HParameterSet.HInsertText.HSet);
}

function quadratic(a, b, c)
{
	var r = Math.sqrt(b*b - 4*a*c);
	return [(-b+r)/(2*a), (-b-r)/(2*a)];
}

function quadratic2(a, b, c)
{
	var r = Math.sqrt(b*b - 4*a*c);
	return [2*c/(-b-r), 2*c/(-b+r)];
}

실행해보면 Answer : -7.450580596923828e-9, -100000000 가 나오는데, 두 번째 근은 얼추 정확하지만, 첫 번째 근은 실제 근에 비해 무려 25%나 오차가 발생한다. b의 값이 매우 크기 때문에 \sqrt{b^2 -4ac}는 거의 b와 가깝게 되고, 이 두 값을 빼는 순간, 상대적으로 작은 차이의 값이 매우 크게 부각된다.

이 부분을 방지하기 위해, 원래 근의 공식의 분모와 분자에 -b \mp \sqrt{b^2 -4ac}를 곱하여, 분자를 유리화한 다음과 같은 근의 공식을 생각한다.

\displaystyle x = \frac{2c}{-b \mp \sqrt{b^2 -4ac}} …… (2)

위 한글 스크립트 코드의 3번 라인에 함수를 두 번째 걸로 바꾸면 된다. 실행해보면 Answer : -1e-8, -134217728 가 나오는데, 이번에는 첫 번째 근이 얼추 맞지만 두 번째 근이 같은 이유로 34%나 오차가 발생한다. 따라서 결론은 두 방법들 중 정확한 것들만 취하면 된다!!

왜 이런 방법이 필요한가에 대해 John D. Cook 선생은 저전력의 장점에 대해 설명하고 있다. floating point 계산에 드는 전력은 64피코줄, 레지스터에 데이터를 저장하는데 드는 전력은 6피코줄 정도의 에너지를 소모하지만, DRAM의 데이터를 읽는데 드는 전력은 무려 4200피코줄의 에너지를 소모한다고 한다. 따라서 식 (1)만으로 이차방정식을 풀려면 더 많은 전력소모를 하게 된다. 즉, 모바일이나 IoT에서 더 적은 전력소모로 프로그램을 구현하기 위한 방법이라 할 수 있다. (댓글을 참조 바람)

근데 본인은 프로그래머가 아니라서, 프로그래밍을 할 때 정말로 이차방정식을 풀 필요가 있나?? 싶은 의문이 좀 들던데, 해커뉴스[1] 사람들의 이야기를 보니 몇몇 경우에 따라서는 floating point error를 심각하게 생각하는 경우가 있는 모양이다. 이거이거 중학교 수학 샘들은 식 (2)와 같은 근의 공식도 암기하도록 교육하시길 바란다. ㅋㅋㅋㅋㅋㅋㅋㅋ

이걸 보니 일전에 제곱근 역수를 계산하는 트릭[3]이 생각나는데, 수학에 기반하여 연산속도를 높이거나 전력소모를 줄이는 프로그래밍 트릭이 앞으로도 쓸모가 없지는 않을 듯 하다. ㅎㅎㅎ

 


[1] The quadratic formula and low-precision arithmetic (hacker news)
[2] The quadratic formula and low-precision arithmetic (John D. Cook)
[3] 내 백과사전 제곱근 역수와 마법의 수 0x5f3759df 2014년 10월 29일

프리프린트 공유 사이트

수학, 물리학, 천문학, 컴퓨터 공학 분야의 출판전 논문을 공유하는 arXiv[1]는 유명한데, 오늘 페북의 고생물학 그룹을 보니 고생물학분야에서도 출판전 논문을 공유하는 PaleoXiv라는 사이트[2]가 생긴 듯 하다. 오호! 아직 총 논문이 74편 밖에 안 되니 신생 사이트인 듯. ㅋㅋ

얼마전에 신경정신 과학의 출판전 논문을 공유하는 PsyArXiv라는 사이트[3]를 본 적이 있었는데, 위키피디아를 보니 사회과학의 출판전 논문을 공유하는 SocArxiv[4]도 있네??? 헐… 첨 알았음. 근데 사회과학쪽은 프리프린트 오픈억세스로 SSRN[5]이 있어서 어떨지 모르겠다. ㅋ 생물학 쪽의 bioRxiv[6]는 꽤 오래 전에 본 기억이 있다. 이쪽은 숫자가 꽤 많이 증가한 듯 하다.

위키피디아를 보니 viXra라는 사이트도 있는 듯 하다. 메인페이지[7] 하단의 자신들의 소개에 따르면, 코넬 대학교의 운영방침에 반하여 arXiv에 싣지 못하는 논문에 대한 대안으로 만든 사이트라고 한다. 뭔 일이 있었던 건가-_-? viXra는 arXiv를 거꾸로 한 것인데, 마치 DivX에 반발하여 만든 Xvid를 연상케 한다. ㅎㅎ

생각이 나서 오랫만에 snarXiv[8] 사이트에 가 봤는데, 아직도 운영되는 듯? ㅋㅋㅋ

 


[1] https://arxiv.org/
[2] https://paleorxiv.org/
[3] https://psyarxiv.com/
[4] https://osf.io/preprints/socarxiv
[5] https://www.ssrn.com/
[6] https://www.biorxiv.org/
[7] http://vixra.org/
[8] 내 백과사전 snarXiv 2010년 6월 9일

[서평] 소수와 리만 가설 – 질서와 패턴을 찾고자 하는 이들의 궁극적 도전 대상

소수와 리만 가설 – 질서와 패턴을 찾고자 하는 이들의 궁극적 도전 대상
배리 메이저(저자) | 윌리엄 스타인(저자) | 권혜승(역자) | 승산 | 2017-06-27 | 원제 Prime Numbers and the Riemann Hypothesis

 


일전에 본 블로그에서 언급[1]한 스테인 선생과 메이저 선생의 그 책[2]이 번역서로 출간될 줄은 꿈에도 몰랐다. 웬 떡이냐. ㅋㅋㅋ 작년에 출간된 듯 한데, 인제사 발견해서 후닥닥 읽어봤다. ㅋ

국내에 John Derbyshire의 책인 Prime Obsession의 번역서[3]가 출간되어 있어, 관심있는 사람은 이미 대부분 읽어봤을 것이라 생각한다. 본인이 알기로 국내 대중서 가운데 리만 가설이 중심 주제인 책은 이 한 권 뿐이었던 걸로 알고 있는데, 번역되지 않은 책들 중에서는 리만 가설에 대한 대중서가 꽤 있는 듯 하다.

그러나 그런 책들은 대부분 비교적 역사적 관점에서 리만 가설을 설명하는 책인데 비해, 이 책은 수학적 배경이 적은 사람에게 리만 가설이 왜 중요한지에 대해 실제로 수학적 설명을 시도하는 책으로, 다른 대중서들과는 조금 방향성이 다르다. 근데 내가 보기에는 독자들이 가진 수학실력의 폭을 너무 크게 잡은 바람에 앞부분은 너무 쉽고, 갈수록 어려워져서 뒷부분은 너무 어려운-_- 요상한 책이 돼 버렸다. ㅋㅋㅋ

텍스트의 분량 자체는 그리 많지 않지만, 이리저리 찾아가면서 읽으면 나름 시간이 걸릴 듯한 책이다. 뭐 나는 수학에 별로 관심이 없어서-_- 초 대충 읽었다. ㅋㅋㅋ

뭐 여하간 책안에 적분, 로그, 시그마 등등의 수식이 등장하니 최소한 고교수학 정도의 실력은 있어야 볼만할 듯 하다. 수학에 좀 관심이 있는 고교생들은 좋아할 듯. ㅋ

 


[1] 내 백과사전 Barry Mazur와 William Stein의 새 책 2015년 11월 25일
[2] Prime Numbers and the Riemann Hypothesis (amazon.com)
[3] 존 더비셔 저/박병철 역, “리만 가설“, 승산, 2006

CoCalc : 웹기반 토탈 수학 관리 플랫폼?

스테인 선생의 구글플러스[1]에서 CoCalc에 대한 이야기를 들었는데, 이런 서비스가 있는 줄 처음 알았다. 위키피디아를 보니 론칭한지 5년이나 됐네-_-

근데 이게 무슨 서비스인지 한마디로 설명하기 곤란한 것 같다. 홈페이지[2]의 설명을 대충 보니 수학 문서작업을 할 수도 있고, 공동 저술을 할 수도 있고, 여러가지 CAS 언어 기반으로 계산도 할 수 있고, 교사가 학생들에게 숙제 같은 것도 배포할 수 있는 교육용 툴로도 쓸 수 있는 것 같다. 완전 수학의 짬뽕 토탈 솔루션이네-_- 간단한 소개가 유튜브 영상[3]으로도 있다.

독특한 기능으로, 타임라인이라는 것이 있어서 편집하는 모든 중간 과정이 기록되고 어느 부분이든 복구가 되는 듯 하다.

앞으로 좀 더 네트워크의 속도가 빨라진다면, 개인용 컴퓨팅 환경은 OS와 저장 공간에 독립적인 웹베이스로 갈 것 같은데, 정말 스테인 선생의 백년지대계 같은 느낌이다. 근데 수학 저변인구가 그리 크지 않다는 걸 감안한다면, 과연 수익성이 얼마나 있을까 싶기도 하다. ㅎㅎㅎ 아무래도 수익성을 생각한다면 교육 플랫폼 쪽으로 나가야 할 것 같기도 하다.

 


[1] https://plus.google.com/u/0/115360165819500279592/posts/9CE6y4w99aG
[2] https://cocalc.com/
[3] An overview of CoCalc (youtube 9분 1초)

필즈상 수상자 Cédric Villani의 최근 행보

Cédric Villani 선생의 이름은 필즈상 수상자다 보니까 여기저기서 종종 듣는데, 잘은 몰라도 나름 똘끼-_-가 있는 사람 같아 보인다. 뭐 수학계에는 똘끼가 워낙 흔해서 이런 건 눈에 띄는 축에도 안 들지만… ㅋㅋㅋ

Villani 선생의 최근 행보에 대해 이야기하는 The Verge의 기사[1]를 읽어 봤다. 수학계의 레이디 가가-_-라네…. ㅋㅋㅋㅋ

이 아저씨 얼마 전에 국회의원에 출마해서 하원에 당선되었다는 이야기는 들었는데, 마크롱 내각에 합류해서 나름 활약중인 듯 하다. 근데 국회의원에 당선돼 놓고 왜 행정부로 옮겼는지는 모르겠음. 마크롱씨가 젊은 정부로서 나름 개혁의지가 강한 듯 한데, 노동 유연성을 좀 높이려다가 근래 철도 노조의 파업[2]으로 꽤 고생하고 있는 듯. 얼마전에는 사르코지도 뇌물 수수 혐의로 잡혀있다[3]고 하던데, 여기나 저기나 똥같은 전직 대통령을 잡아 넣고 개혁하느라 나라가 꽤 시끄러운 것 같다. ㅋ

뭐 여하간 마크롱 내각에서 수학/과학 쪽을 담당하는 테크노크라트 역할을 하는 모양이던데, 근래 인공지능과 관련하여 정부의 정책 방향과 전략을 제시하는 보고서를 발간한 것 같다. 웹사이트[4]가 별도로 있는데, 보고서는 이 사이트[4]에서 pdf 포맷으로 다운로드 받을 수 있다. 사업하느라 바쁘신 분들은 10페이지부터 시작되는 executive summary를 보면 된다. 근데 나는 영어 울렁증이라…. -_-

유럽을 기반으로 하는 빅테크 기업(GAFAM; 구글, 애플, 페북, 아마존, 마소)이 없어서, 유럽 정부들은 나름 고심을 하는 모양인 듯 하다. 이제 인터넷 시대, 모바일 시대를 지나서 인공지능 시대로 들어가는 듯 하니, 이 시류에 따라 빅테크 기업을 하나 키워보려는 정부의 소망 비스무리한 걸 느낄 수 있다. 레이 쥔이 ‘태풍의 길목에 서면 돼지도 날 수 있다‘ 고 말했더라는 진위불명의 소문이 있던데, 출처는 불명해도 여하간 이 말 대로 멍때리지 말고 새로운 기술 도래의 시기를 놓쳐서는 안 될 듯 하다. 마크롱씨도 나름 노력하는 듯.

필즈메달이 미래에 업적을 이룰 사람에게 주는 격려상이라는 취지에서, 필즈메달 수상자가 딴 일 하는 걸 별로 안 좋게 보긴 하는데, 뭐 정부에서 중요한 과학기술 정책에 의미있는 조언을 해서 과학기술 발전에 도움이 된다면 나쁘지는 않다고 생각한다.

Villani 선생의 책은 국내에 역서[5]가 한 권 있는데, 게을러서 사 놓고 여태 읽지 않고 있다. 대충 앞부분만 보니 수필에 가까운 내용인 듯 한데, 별달리 설명도 없이 전문 용어를 사용하는게, 아무래도 대중적 독자를 염두해서 쓴 책은 아닌 듯 하다. 켁.

 


[1] the verge MEET THE ‘LADY GAGA OF MATHEMATICS’ HELMING FRANCE’S AI TASK FORCE Mar 28, 2018, 8:10am EDT
[2] 로이터 French train chaos strikes again as standoff with Macron deepens APRIL 8, 2018 / 2:05 PM
[3] 가디언 Nicolas Sarkozy in police custody over Gaddafi allegations Tue 20 Mar 2018 09.04 GMT
[4] https://www.aiforhumanity.fr/en/
[5] 세드릭 빌라니 저/이세진, 임선희 역, “살아 있는 정리“, 해나무, 2014

기하(幾何)의 어원에 대해

‘국보’ 양주동 선생의 수필 중에 『몇 어찌』라는 수필[1]이 있다. 한학을 통달하여 세상 모르는 한문이 없던 그에게 ‘幾’자와 ‘何’자가 붙은 기괴한 단어의 의미를 도통 알 수 없어, 수 일동안 고민을 하고 기하학의 논증과 체계를 익힌 이후에, 그가 서구의 학문에 대해 감탄하게 된다는 이야기다.

幾何가 여태 geometry의 음차로 알려져 있는 것이 일반적인데, 일본어 위키피디아를 보니 이것이 아니라는 주장[2]이 있다고 한다. 원문이 일본어라서 번역을 시도해 봤는데, 일본어 실력도 딸리고-_- 음운론에 대해서는 일자 무식이고 IPA도 모르다보니 힘들어서 번역하다가 접었다-_-

써 놓은 부분은 아까워서 걍 올려본다. ㅋ 원문을 읽고 싶은 분들은 [2]에서 무료로 pdf를 받을 수 있으니 참고하기 바란다.

검색하다가 알게 된 사실인데, 일본에서는 DOI 대신에 국립정보학 연구소에서 발행하는 CiNii라는 문헌 코드번호를 쓰는 것 같다. NII 코드 번호로 문서를 검색해 볼 수 있는 사이트[3]도 있다.

만주어 자료에서 본 「기하」의 어원에 대해

0 시작하며
「기하」는 geometria의 접두어인 geo-를 음차한 것이라는 설이 예로부터 널리 퍼져 있다. 이 속설은 발음으로 봐도, 의미로 봐도 착오가 있다. 이 논증은 중국학의 기본적인 훈련을 받아보면 어렵지 않다. 또, 그 시기의 기본적 논점은 이미 알려져 있어서, 예를 들면, 명말청초 당시에 Euclid 『원론』을 들여온 P. Engelfriet의 방대한 저서 중에도 보인다.(1) 그러나 이런 주장은 중국학 연구자 이외에 그다지 알려져 있지 않고, 또, 과학사 연구자가 저술한 논증에는, 어원학에 대해 상세히 설명하기도 어려운 부분이 있다. 그러므로 번잡하긴 하지만, 여기서는 속설이 잘못된 점에 대해 이유를 다시금 상세히 제시하고자 한다. 수학 교과서나 대중서를 쓰려는 사람들은 특히, 이하의 논설을 유의한 후에, 속설이 확대 재생산되는 일이 없기를, 필자는 희망하는 바이다.

이 글의 구성을 설명한다. 먼저 제1절에서 16~18세기의 중국어와 만주어의 음성에 관해서 과거 여러 연구를 바탕으로, 「기하」가 geometria의 음역일 수 없음을 논증한다. 제2절에서, 명말청초 예수회에서 저술한 한문ㆍ만주문 문헌을 바탕으로 「기하」는 명말청초 당시에 geometria를 의미한 것이 아니라는 것을 논증한다. 제3절에서, 19세기 전반에서 중엽까지 프로테스탄트계 선교사가 저술한 대수의 영어-중국어 사전을 바탕으로 「기하」가 geometria를 의미한다는 말이라고 이해를 한 경위를 개괄한다. 이 절의 내용은 강연 이후에 추가된 내용이다. 그리고 결론으로 속설의 발생한 시기와 유포자에 대한 추측을 서술한다.

1. 음성
17세기 당시 「幾」자의 공식 발음 (말하자면 관화음(官話音))과, 예수회의 geometria의 발음 사이에는 전혀 관계가 없다. 이것을 논증하기 위해서, 먼저 「幾」자의 발음을 고찰하고, 다음으로 geometria의 발음을 고찰한다. 논의에 들어가기 전에, 중국어 음운에 대한 용어를 서술해 둔다. 중국어 1음절은 일반적으로 (CV)V(S) 인 모양을 하고 있다. 여기서 V는 모음이고, C는 자음이고, S는 모음 또는 자음이다. 「()」으로 묶인 음은 생략될 수도 있는 부분이다. 이 하나의 음절 (CV)V(S)를 (C)+(V)V(S)로 두 부분으로 분해하여, 앞부분 자음 (C)를 성모(声母)

(포기함 ㅋ)

한편, 수학용어의 function은 한국에서 함수(函數), 중국에서 函数라는 용어를 사용하는데, 유독 일본만은 関数로 쓰고 있다. 일본어 위키피디아에 따르면 19세기에는 일본도 函數를 썼다고 한다. 20세기 국어 개혁과정에서 사용한자의 종류를 줄이는 노력을 하면서 발음이 같은 関으로 변경된 것이라고 한다.

 


[1] http://zariski.egloos.com/1259922
[2] 渡辺 純成, “満洲語資料からみた「幾何」の語源について (数学史の研究)”, 数理解析研究所講究録, 1444, p34-42, NII Article ID : 110001374083
[3] https://ci.nii.ac.jp/

교과서적인 RSA와 심각하게 허술한 보안 상태인 QQ 브라우저

얼마전에 텐센트가 중국 기업 최초로 시총 5천억달러를 돌파했다는 뉴스[1]를 봤는데, 바이두, 알리바바와 함께 천하삼분지계를 노리는 세 회사 중에서 텐센트가 제일 잘 나가는 모양이다.

해커뉴스[2]에서 텐센트의 QQ 브라우저가 얼마나 보안에 취약한지에 대해 설명하는 arxiv의 글[3]을 봤는데, 와 진짜 대단하네-_- 텐센트가 중국 정부의 검열에 엄청난 기여를 하고 있는 것 같다. ㅎㅎ 시총 5천억달러의 위업이 무색해지는 순간이다.

내용[3]을 보니 QQ브라우저는 텐센트 서비스로 로그인 하는 순간에 IMEI, IMSI, 와이파이 맥주소, 와이파이 SSID, 안드로이드 ID, 방문한 모든 페이지의 URL 등등의 개인정보를 전송한다고 한다-_-

QQ 브라우저는 PRNG 알고리즘으로 AES를 쓴다고 하는데, 그냥 쓰는게 아니라 89999999이하의 난수를 생성하는 nextInt(89999999) 함수 앞에 문자열 10000000을 붙여 사용하여 엔트로피를 줄여 쓴다(즉, 원래 경우의 수인 2128보다 작게 줄여 쓴다)고 한다. 경우의 수가 작으면 그만큼 뚫기도 쉬워진다.

이 뿐만 아니라, QQ 브라우저가 쓰는 RSA 알고리즘은 겨우 128비트(!) 밖에 안 되는데, 합성수 245406417573740884710047745869965023463 을 쓰고 있다고 한다. 내가 가지고 있는 maple의 ifactor 함수로 시험삼아 돌려보니 1초만에
245406417573740884710047745869965023463 = 14119218591450688427 * 17381019776996486069
이라고 바로 인수분해 된다-_- 1024비트 합성수도 불안하다고 난리치는 세상에 128비트라니… ㅋ

게다가 QQ 브라우저의 RSA 알고리즘은 완전히 교과서 그대로인 RSA (즉, textbook RSA)라서 padding이나 일체의 보완책이 없기 때문에 매우 뚫기 쉽다고 한다. RSA를 교과서 내용 그대로만 쓰는 경우에는 매우 취약하다는 건 처음 알았네-_-

비대칭 암호의 경우, 공격자가 암호장비와 복호장비가 별도로 확보되는 상황이 있는데, 암호장비에 적절한 평문을 넣어 공격하는 방법이 Chosen-plaintext attack이고, 복호장비에 적절한 암호문을 넣어 공격하는 방법이 Chosen-ciphertext attack(CCA)이다. 이 때, 적절한 암호문을 융통성있게 잘 넣어 보는 공격법이 Adaptive chosen-ciphertext attack이라고 하는데, 업계에서는 CCA2라는 약자로 부르는 것 같다. 이런 건 처음 알았음. ㅎㅎ

저자는 글[3]에서 CCA2를 이용하면 교과서적인 RSA가 얼마나 뚫기 쉬운지 이야기하고 있는데, 그 밖에도 알려진 다양한 공격법으로 뚫리는지에 대한 이야기를 하고 있다. 음… ㅋ

 


[1] 연합뉴스 텐센트, 中 IT기업 최초로 시가총액 5천억弗 돌파 2017/11/21 09:51
[2] https://news.ycombinator.com/item?id=16362488
[3] Jeffrey Knockel, Thomas Ristenpart, Jedidiah Crandall, “When Textbook RSA is Used to Protect the Privacy of Hundreds of Millions of Users”, arXiv:1802.03367 [cs.CR]

Goodstein의 정리와 증명불가능성

며칠 전에 Goodstein의 정리라는 걸 처음 봤다. 대충 위키피디아를 읽고 글을 써본다. ㅋㅋ 이 글에 나온 모든 지식은 위키피디아에 있음.

Goodstein의 정리가 뭔고 하면, 상속 n진법 표현(hereditary base-n notation)이라는 걸 생각해보자. 이건 또 뭔고 하면-_-

35는 이진법으로 2^5 + 2^1 +2^0 인데, 지수 5는 이진법으로 표현되지 않았으므로 다시 한 번 이진법으로 표현한다. 즉, 2^{2^2 +1} + 2^1 +2^0 이 hereditary base-2 notation이 된다.

임의의 어떤 수가 초항으로 주어질 때, hereditary base-2 notation부터 시작해서 hereditary base-n notation을 hereditary base-(n+1) notation으로 바꿔치기 한 후 1을 뺀 수를 다음 항으로 하는 수열을 생각하자.

예를 들어 위키피디아에 나온 예시를 그대로 옮겨보자.
초항이 19 = 2^{2^2}+2^1 + 2^0이면,
두 번째 항은 3^{3^3} + 3^1 + 3^0 -1 = 7625597484990이 된다. ㅋ
세 번째 항은 4^{4^4} + 3 \approx 1.3 \times 10^{154} 이 되고,
네 번째 항은 5^{5^5} + 2 \approx 1.8 \times 10^{2184}
다섯 번째 항은 6^{6^6} + 1 \approx 2.6 \times 10^{36305}
여섯 번째 항은 7^{7^7} \approx 3.8 \times 10^{695974}
일곱 번째 항은
\begin{gathered}8^{8^8} -1 = \hfill \\ \quad 7\cdot 8^{7\cdot 8^7 + 7\cdot 8^6 + 7\cdot 8^5 + 7\cdot 8^4 +7\cdot 8^3 +7\cdot 8^2 +7\cdot 8+7}+\hfill\\ \quad 7\cdot 8^{7\cdot 8^7 + 7\cdot 8^6 + 7\cdot 8^5 + 7\cdot 8^4 +7\cdot 8^3 +7\cdot 8^2 +7\cdot 8+6}+\\ \quad \cdots +7\cdot 8^2 + 7\cdot 8 +7 \hfill\\ \quad \approx 3 \times 10^{15151335}\hfill\end{gathered}
이 된다. 아놔-_-

이런 수열을 Goodstein 수열이라고 하는데, Goodstein의 정리는, 모든 Goodstein 수열은 궁극적으로 영에 수렴한다는 정리이다. 헐-_- 저게 영이 된다고??

근데 증명은 ordinal number를 가지고 하는 것 같다. 별로 수 같지 않은 존재지만-_- ordinal number의 addition, multiplication, exponentiation이 잘 정의돼 있다고 한다. 각 base를 ordinal number로 바꿔치기한 새로운 수열을 병렬적으로 생각하면 strictly하게 감소하기 때문에, 이 병렬적 수열이 영에 수렴하기 때문에 Goodstein 수열도 영으로 수렴한다고 하는 듯. 사실 잘 이해가 안 돼서 책을 좀 찾아봤는데, 수리논리학 책을 본 적이 없으니 아놔 봐도 잘 이해가 안 됨-_-

근데 뭔가 수 같지 않은 걸로 증명하는게 영 보기 좋지 않은데, 정수론 문제니까 정수 집합 안에서 깔삼하게 증명 안되나? 싶은 생각이 드는데, 여기서 대 반전-_-!!! 이 정리는 Peano arithmetic에서 증명이 불가능하다는 것이 증명되었다고 한다. 위키피디아를 보니 이 증명은 꽤 빡세다고 하네-_-

여하간, 참인 명제지만 공리계 안에서 증명 불가능한 사례인데, 일전에 이야기한 적[1]이 있다. 보통 이런 명제는 자기를 지칭하는 self-reference를 포함하는 어거지 같은 명제가 많지만 (나는 거짓말을 하고 있다!! 이런 거-_-) 몇 안 되는 self-reference가 아닌 명제들 이라나 뭐라나.

 


[1] 내 백과사전 참인 명제와 증명가능한 명제의 차이 2017년 3월 18일