-
Gomory-Hu Tree in Subcubic Time
Introduction mincut terminology 무방향 그래프 $G = (V,E)$ 의 각 edge에 대해 양의 정수 weights $w: E \rightarrow Z_{+}$ 정의되어 있다고 하자. 정점들의 집합 $S$가 $s \in S, t \notin S$를 만족할 때 $S$를 $(s,t)$-cut 이라 한다. 이 때, $S$의 weight $\delta(S) = \Sigma_{e\in E(S, V \setminus S)} w(e)$ 가 최소인 경우를 ($s$,$t$)-mincut 이라 하고, 그 weight를 $\lambda(s,t)$라 한다. Gomory-Hu Tree Gomory-Hu Tree는 모든 $(s,t)$에 대한 mincut을 encoding하는 Tree이다. 다음과 같은 두 definition으로 정의 가능하다....
-
Triple DES의 안전성
1. Introduction Triple DES는 DES를 3번 진행하는 암호이고, DES가 낮은 키의 엔트로피(56비트)로 인해 컴퓨터 성능이 발전함에 따라 점차 충분한 안전성을 제공할 수 없게 되자 다음 암호인 AES가 등장하기 전까지 임시로 사용되었습니다. Triple DES는 DES를 서로 다른 키 $K_1, K_2, K_3$에 대해 3번 적용합니다. 즉 키의 길이는 168비트입니다. 이 때 Single DES와의 호환성을 위해 처음 두 번의 DES는 암호화, 세 번째의 DES는 복호화로 둡니다. 또한 경우에 따라 $K_1 = K_3$으로 두어 112비트의 키를 사용하기도 합니다. Triple...
-
Euler Tour 테크닉
문제 상황 다음과 같은 문제를 생각해 보자. (루트가 있는) 트리 $T$가 있다. 모든 정점은 초기에 $0$의 가중치를 가지고 있다. 이 때, 다음 두 종류의 질의를 처리해보자. 정점 $v$와 새로운 가중치 $x$가 입력으로 주어질 때, 정점 $v$의 가중치를 $x$로 바꾼다. 정점 $x$와 $x$의 모든 후손들(즉, 정점 $x$를 루트로 한 부트리의 정점들)의 가중치의 합을 구한다. 생각할 수 있는 가장 쉬운 풀이들은 $arr[x]$를, 정점 $x$의 가중치로 정의한다. 1번 질의는 상수 시간에 처리할 수 있다. 2번 질의에서 일일히 정점...
-
ESPiRiT을 이용한 Sensitivity Computation
Introduction 지난 글에서는 MRI의 개괄적인 원리, 즉 장비에서 얻은 raw data를 어떻게 이미지로 변환하는지에 대해 다루어보았습니다. 또한 그 중에서 scan time을 줄이기 위한 기법인 Parallel imaging과, 그로 인한 이미지 퀄리티 저하를 보상하는 알고리즘 중 SENSE, GRAPPA, 그리고 PRUNO에 대해 간략히 다루었습니다. 현재 가장 두루 쓰이는 방법은 GRAPPA, SENSE이지만 이 둘은 벌써 고안된 지 20년이 넘어가는 classic한 알고리즘입니다. Practical하진 않지만, 연구나 다른 특수한 목적으로 개발된 고성능 알고리즘들이 쏟아져나왔죠. 오늘은 그 중에서 수학적으로도 흥미롭고, 꽤 재미있는 인사이트를...
-
Bitslice을 활용한 암호 구현
들어가며 이번 글에서는 1997년 Eli Biham의 “A Fast New DES implementation in Software”에서 다시 환기된 Bitslice 기법에 대해서 작성해보려고 합니다. 이전 1970년대에 사용되던 Bitslice는 워드의 길이를 늘리기 위해서 더 작은 bit 너비에서 구성하는 것이었습니다. 현대에 들어서는 거의 사용되지 않았지만, Eli Biham이 평문을 병렬화하여 DES의 고속구현을 하며 소프트웨어단에서 재사용되기 시작했습니다. 현대의 Bitslice기법은 각 단어를 Bit별로 잘라, 여러 단어의 특정 bit들을 묶어 재지정한 다음 연산을 하는 과정을 의미합니다. 그렇게되면, 재지정된 한 단어는 기존 여러 단어들의 동일한 위치의...