Manbo's Blog

해당 글은 Fulton의 Algebraic Curves와 Silverman의 Arithmetic of Elliptic Curves를 정리한 것이다. Finite field $\mathbb{F}_p$ 위에서 정의된 두 Elliptic Curve $C_1, C_2$의 점 개수가 같으면 두 Curve는 isogenous 임이 알려져있다. degree가 1보다 큰 isogeny를 적용했을 때 점 개수가 줄어듦이 명확하고, 따라서 surjective가 아니게 되는 문제에 대한 의문을 해결한다. Dimension of a curve Variety $V$의 dimension은 function fie...

해당 글은 Silverman의 Arithmetic of Elliptic Curves의 Chapter 1을 정리한 것이다. Diopantine equation은 $ax + by = c$를 만족하는 정수해 $x, y$를 찾는 것을 말한다. 만약 2차 다항식이거나 변수가 $x,y$가 아니라 $x_1, x_2, …, x_n$으로 많다면 정수해를 어떻게 찾을 수 있을까? 그리고 그들은 어떤 특징을 가질까? 다항식을 통해 얻을 수 있는 점들의 집합은 대수적으로 어떤 특성을 갖는지 분석하는 것이 대수기하학이다. 이것의 기본이 되는 기념이 algebraic set, variety라고 할 수 있...

해당 글은 1997년도 논문 Quantum Database Searching by a Single Query를 정리한 것이다. 주어진 함수 $f:\mathbb{Z}_n \rightarrow \{0,1\}$에서 $f(x)=1$을 만족하는 해의 비율이 충분히 클 때, 한 번의 쿼리로 Grover algorithm을 수행할 수 있다.

해당 글은 Quantum Security Analysis of CSIDH논문을 정리한 것이다. Regev의 알고리즘은 2008년도 A Subexponential Time Algorithm for the DHSP with Polynomial Space 논문을 참조 Quantum algorithm for HSP 2편

해당 글은 Quantum Security Analysis of CSIDH논문을 정리한 것이다. 3개의 대표적인 양자 알고리즘이 존재한다. kuperberg의 첫번째, 두번째 알고리즘과 Regev의 알고리즘이 존재한다. 입력으로 주어진 함수의 정의역 G가 commutative group 일 때만 해당 알고리즘을 적용할 수 있다.(finitely generate일 필요는 없다.)

Isogeny는 Elliptic Curve 간의 group homomorphism을 말한다. $\mathbb{C}$ 위에서 정의된 Elliptic Curve들은 모두 isogenous할까? $\bar{\mathbb{F}}_p$ 위에서 정의된 Elliptic Curve들은 $\mathbb{C}$위에서 정의된 Elliptic Curve들과 어떻게 다를까? Velu’s formula를 이용해 Isogeny를 연산할 수 있다. kernel polynomial을 이용해서도 Isogeny를 연산할 수 있다.

Montgomery Multiplication은 모듈러 곱을 효율적으로 수행하는 알고리즘이다. $\mathbb{F}_p$ 상에서 곱은 대부분의 공개키 기반 암호에서 사용한다.(e.g. ECC, isogeny, lattice, … etc)