-
Consistent Hashing
안녕하세요? 오늘은 웹서버 등에서 요청을 여러 곳으로 공평하게 분산시키는, load balancing 작업을 수행할 때 널리 사용되는 consistent hashing 알고리즘에 대해 알아보겠습니다. Consistent hashing은 1997년 Karger의 논문 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web에서 제안된 알고리즘입니다. 서론 Karger의 논문에서는, 다른 클라이언트에서 접근 가능한 많은 object를 가지고 있는 단일 서버의 상황을 가정하였습니다. 서버에 캐시를 두면 더 빠른 접근이 가능하다는 것은 자명합니다. Object들은 여러 개의 캐시에 분산되어야 하는데,...
-
Indistinguishability in Cryptography
1. Introduction 주어진 암호를 키에 대한 정보 없이 전수 조사보다 더 효율적으로 완전히 해독할 수 있다면 더할 나위 없이 강력한 공격입니다. 특히 현재 널리 쓰이고 있는 암호 시스템에 대해 이러한 공격을 찾았다면 정말 큰 업적을 세웠다고 할 수 있습니다. 그러나 수명, 많게는 수십명이 협력해 만들고 긴 시간을 걸쳐 검증을 받아온 암호 시스템에서 이러한 공격이 발견되기란 굉장히 어려운 일입니다. 이렇게 암호문을 완전히 해독하는건 매우 힘들지만 학계에서는 꼭 암호문을 완전 해독해내는 것이 아닌 더 느슨한 환경에서의 조그만...
-
rth Root Extraction
서론 이번에 CTF 문제를 풀면서 한 가지 특이한 문제를 보게 되었습니다. 문제의 핵심 부분은 다음과 같았습니다. 소수 $p$와 $\gcd(p-1,r)\neq1$인 $r$에 대해서 $m^r\text{mod}\ p$가 있을 때 $m$을 구할 수 있는가? 일반적으로 $\gcd(p-1,r)=1$이라면 $p-1$에 대한 $r$의 역수 $r^{-1}$을 구한 뒤 $(m^r)^{r^{-1}}$을 계산하면 $m$을 구할 수 있습니다. 하지만 그렇지 않은 경우에 대해서는 본 적이 없었기 때문에 검색하는데 시간을 꽤 들이게 되었습니다. 저는 한 논문을 보고 구현했지만, 일반적으로 Adleman-Manders-Miller Root Extraction이라는 Method를 사용한다는 것을 CTF가 끝난 뒤 알게 되었습니다....
-
'촛불과 그림자' 해결 일지
혹시 기하 문제를 좋아하시나요? Problem Solving에 나오는 어려운 기하 문제는 다양한 예외처리와 기하 문제 특유의 방향성 때문에 인해 일반적으로 기피대상입니다. 우연히 맞닥뜨린 문제인 BOJ 18190번 ‘촛불과 그림자’도 악명 높은 기하 알고리즘 문제로, solved.ac에서 Ruby V로 평가되는 고난이도의 문제입니다. 알고리즘 구상부터 해결까지 대략 일주일 정도 걸린 시련의 길을 반면교사로 삼고자 이렇게 글을 쓰게 되었습니다. 이후엔 촛불과 그림자 문제의 상세한 아이디어와 풀이가 나오므로 유의하시기 바랍니다. ‘촛불과 그림자’란? 해결 일지 1월 14일: 구상 1월 15일: 첫 제출에서 59%까지...
-
시간 복잡도를 고려한 코드 설계 전략
개요 알고리즘 문제에는 여러 가지 제한이 주어집니다. 여기에는 입력으로 주어지는 값의 범위, 그 값들이 가지는 성질 등의 조건도 있지만, 대부분의 경우 메모리 제한과 시간 제한이 같이 주어집니다. 많은 문제들에서는 이 제한을 크게 고려하지 않고도 답을 찾아내는 로직만을 생각하여 코드로 구현하면 통과할 수 있지만, 일부 문제에서는 시간 제한 때문에 직관적인 해결책으로는 통과할 수 없는 경우도 존재합니다. 따라서 알고리즘 문제를 풀 때에는 코드를 작성하기 전후로 로직과 코드의 시간 복잡도를 계산하는 것이 중요합니다. 시간 복잡도는 알고리즘을 공부할 때...