-
양자 컴퓨팅 입문 (2) - Grover's Algorithm
Grover’s Algorithm은 정렬되지 않은 데이터베이스에 있는 $N$개의 항목 중 특정한 조건을 만족하는 항목을 $O(\sqrt{N})$에 찾는 알고리즘입니다. 고전 컴퓨팅에서 이 문제를 해결하려면, 간단하지만 느리게 갈 수밖에 없습니다. 전수 조사(brute force)가 유일한 해결책입니다. 당연히 시간 복잡도는 $O(N)$이며, 랜덤하게 셔플해서 순서를 바꾼다 해도 마찬가지입니다. 그리고 이보다 더 나은 시간복잡도로 찾을 수는 없습니다. Grover’s Algorithm은 이 시간복잡도를 $O(\sqrt{N})$으로 낮추는데 성공하였고, 이 시간복잡도가 최적이라는 것이 알려져 있습니다. 또다른 유명한 양자 알고리즘인 Shor’s Algorithm과는 달리 알고리즘 자체가 간단하면서도 심도 있기 때문에...
-
부동소수점에 대한 이해 2
서론 지난 글에서는 부동소수점 자료형이 무엇이고, 이들의 대표적인 표준인 IEEE 754에서 규정한 이진법 16비트 자료형의 세부적인 구조 및 10진수와 서로 변환하는 법 등을 알아보았습니다. 이번 글에서는 지난 글에 이어, 부동소수점 자료형으로 나타낸 수들끼리의 사칙연산을 수행하는 과정을 알아보고, 실제 프로그래밍 언어에서의 수학 라이브러리 함수를 보며 비교적 간단한 연산들을 어떻게 구현하게 되는지에 대해 알아보도록 하겠습니다. 사칙연산 사칙연산과 같은 기본적인 연산은 CPU, 또는 FPU (floating-point unit)에 내장되어 있기 때문에 별도의 라이브러리 없이도 사용이 가능합니다. 이 문단에서는 부동소수점 자료형을...
-
Parametrized inapproximability for Steiner Orientation by Gap Amplification
Parametrized inapproximability for Steiner Orientation by Gap Amplification 이 글에서는 k-STEINER ORIENTATION 문제와 MAX (k, p)-DIRECTED MULTICUT 문제에 대한 FPT hardness result를 소개하는 논문을 정리한다. 먼저, k-STEINER ORIENTATION 문제는 다음과 같이 정의된다: 입력: mixed graph $G$ 와 $k$ 개의 terminal pair $T_G = {(s_1, t_1), (s_2, t_2), \ldots, (s_k, t_k)}$ (mixed graph 는 무방향 간선과 방향성 간선이 둘 다 존재할 수 있는 그래프를 뜻한다.) 출력: $G$ 의 모든 무방향 간선에 방향성을 주어서, $s_i \rightarrow t_i$...
-
LSH: 유사한 두 데이터 찾기
안녕하세요? 오늘은 두 데이터가 얼마나 유사한지를 계산하는 방법과, 이를 통해 유사한 두 데이터를 찾는 방법인 LSH(Locality Sensitive Hashing)에 대해 설명해보려고 합니다. Jaccard 유사도 예를 들어 다음과 같은 두 문자열 A, B가 있다고 가정해보겠습니다. A = “abcabcdefg” B = “cdefghiabc” 두 문자열을 조금 관찰해보면, “abc”와 “cdefg”라는 공통되는 부분을 가지고 있는 꽤나 유사한 두 문자열임을 알 수 있습니다. 아마 누군가 두 문자열이 유사한지 묻는다면, 저는 유사하다고 답할 것 같습니다. 하지만, 이 두 문자열이 얼마나 비슷한지를 수치적으로 명확하게...
-
Anomalous Elliptic Curves
서론 저번 글에 이어서 이번에는 데프콘 CTF의 예선을 진행하면서 anomalous elliptic curve에 대해서 공부하게 되었습니다. 본래 CryptoHack[1] 에서 anomalous elliptic curve와 그 취약점에 공부한 바가 있지만, 예선에 나온 문제는 CryptoHack에서 공부했던 공격에 취약하지 않은 anomalous elliptic curve를 구하는 문제였습니다. 어떤 문제가 나왔었는지 하나씩 살펴봅시다. 본론 Anomalous Elliptic Curve Anomalous elliptic curve는 곡선이 $F_p$ 위에서 정의될 때 order가 $p$ 인 곡선을 의미합니다. 타원 곡선을 정의를 하게 되면 그 곡선 상에 존재할 수 있는 점의 개수가 정해지는데,...