-
SMAWK algorithm
들어가며 SMAWK 알고리즘은 $n \times m$ 크기의 totally monotone한 행렬에서 모든 행마다 최솟값의 위치를 $O(n+m)$ 시간에 구하는 알고리즘이다. 이 글에서는 SMAWK 알고리즘에 대해 소개하고, 이를 통해 해결할 수 있는 문제들에 대해 소개한다. 단조성. $2 \times 2$ 행렬 $\left[ {\begin{array}{ccc}a & b \ c & d \ \end{array}} \right]$ 은 다음 조건이 성립하면 monotone하다고 한다. $c < d$이면 $a<b$이다. $c=d$이면 $a\leq b$이다. $n \times m$ 행렬은 만약 모든 $2 \times 2$ 부분행렬이 monotone하다면 totally monotone하다고 한다....
-
Isogeny-based cryptography
Introduction 현재 사용되고있는 공개키 암호 시스템은 많은 수가 기본적인 RSA의 변형으로 discrete logarithm problem(이산로그) 또는 integer factorization problem 문제의 어려움을 기반으로 하고 있으며, 타원곡선 상에서의 연산에 기반한 시스템 역시 elliptic-curve discrete logarithm problem(ECDLP)을 기반으로 합니다. 이 3가지 문제들은 모두 양자컴퓨터상에서 Shor’s algorithm으로 빠른 시간에 풀 수 있음이 알려져있기 때문에, 양자컴퓨터가 등장하더라도 그 안전성을 보장할 수 있는 post-quantum cryptography algorithm이 필요하게 되었습니다. NIST(미국 국립표준기술연구소) 에서는 양자컴퓨터의 출현에도 안전한 Post-Quantum Cryptography의 표준화를 위해 여러 알고리즘들을 제출받아서 보안성과...
-
Solving 8-puzzle problem with search algorithm
Abstract 8-퍼즐 문제는 3X3 크기의 프레임과 1부터 8까지의 숫자로 이루어진 슬라이딩 퍼즐을 순서대로 배열하는 문제입니다. 더 일반화된 문제는 N-퍼즐 문제로, 최적의 해를 찾는 것이 NP-hard라고 합니다. 이번 글에서는 가장 기본적인 BFS, DFS에서부터 IDS 알고리즘, A* 알고리즘까지의 방법론으로 8-퍼즐 문제를 풀어보고, 그 성능을 분석해보도록 하겠습니다. 8-퍼즐 문제 8-퍼즐은 3X3 그리드로 나누어진 정사각형 프레임 안에 8개의 타일과 하나의 빈 공간이 있는 슬라이딩 타일 퍼즐입니다. 아마 한번쯤은 해보셨을 것으로 생각됩니다. 8-퍼즐 각 타일은 서로 구분되는데, 보통은 1부터 8까지의...
-
Optimal Ate Pairings, BLS12-381, BN254 알아보기
이전 글에서 이어서 가겠습니다. Optimal Ate Pairings [Ver09]의 내용입니다. 다시 Tate Pairing으로 돌아가서, \[(f_{s, P}) = s(P) - ([s]P) - (s-1) \mathcal{O}\] 인 함수 $f_{s, P}$를 생각하면, reduced Tate Pairing \[t_r(P, Q) = f_{r, P}(Q)^{(q^k - 1) / r}\] 를 얻을 수 있었습니다. 이제 이를 최적화하는 Ate Pairing을 알아봅시다. Lemma \[f_{ab, Q} = f_{a, Q}^b \cdot f_{b, [a]Q}\] 증명: 단순 계산. 어렵지 않습니다. 그러면 특히 $[r]Q = \mathcal{O}$인 경우에는 \[f_{mr, Q} = f_{r, Q}^m\] 가...
-
Segment Tree Beats와 Kinetic Segment Tree
Segment Tree Beats와 Kinetic Segment Tree 이 글에서는 Kinetic Segment Tree라는 새로운 세그먼트 트리를 소개한다. 어떠한 원소가 Kinetic하다는 것은 시간에 따라서 움직인다는 것으로, 쉽게 말해 그 원소가 일차함수거나 다항함수라는 것이다. 세그먼트 트리도 대회에 자주 나오고, Kinetic한 원소도 대회에 자주 나오니 (대표적으로 컨벡스 헐 트릭), 그것의 조합 역시 익혀보면 도움이 될 것이다. 또한, Kinetic한 원소와 전혀 상관이 없는 문제들에서도 Kinetic한 성질이 파악된다는 점에서 착안하여 (대표적으로 CHT를 사용한 DP 최적화), 이 Kinetic Segment Tree가 어떻게 응용될 수...