Isogeny란 간단하게 elliptic curve 간의 group homomophrism이라고 말할 수 있다. Isogeny의 특별한 성질을 이용해서 암호를 만들 수 있다. 설명에 앞서 각 용어들이 무엇을 나타내는지 정의하자. Short Weierstrass form : $y^2=x^3+ax+b$Montgomery curve : $By^{2}=x^3+Ax^2+x$ where $B(A^2-4)\ne 0$. NB. $B\ne 0$이므로 $x=B^{3}u,y=Bv$를 이용하면 $B=1$인 형태 $y^{2}=x^{3}+Ax^{2}+x$를 얻는다. Short Weierstrass form에서 Montgomery model로 변환하는 방법은 $x^{3}+ax+b \equiv 0\pmod{p}$의 root $r$과..

MOV (Menezes-Okamoto-Vanstone) attack이란 $E(\mathbb{F}_{p})$위의 이산로그 문제를 $\mathbb{F}_{p^{k}}$에서의 이산로그 문제로 환원하여 문제를 해결하는 공격 기법이다. 이때 $p$는 소수이다. MOV attack을 이해하기 위하여 알아야할 이론적인 배경을 알아보자.$E/K$는 elliptic curve이고 $O$는 base point이다. Definition 1. $E[m]:=\{P \in E\ |\ [m]P=O\}$. Weil-pairing with $m \in \mathbb{Z}_{>0}$ is a map$e_{m}:E[m] \times E[m] \rightarrow \mu_{m}$ by setting $e_{m}(S,T)=\frac{g(X+..

와... 멀어만 보이던 루비를 드디어 달성했습니다. 군대를 7월 15일에 가서 군대 가기 전에 루비 찍고 가려했는데 그 목표를 달성했네요!!!! 이제 solved.ac 디코에서도 분홍색 닉네임입니다!! 꺄~~~~~~루비 가려고 마음 먹은게 루비까지 50점도 레이팅이 남았을 때였습니다. 그때는 클6이었는데 클8을 열심히 밀어서 레이팅 20을 얻었습니다. 이후 개꿀 날먹처럼 보이는 r5 문제를 2문제 정도 풀었는데 다 거짓말이었습니다;;;; 요즘 정수론을 안하고 있었는데 다시 하니까 너무 재미있었습니다. 특히, r5 위수는 쿼리입니까? 가 제일 인상 깊었습니다. 여기에서 구현해 놓은 것으로 한 d2 3개정도 날먹한거 같네요^^. 마지막으로 푼 문제는 coefficient 라는 페트로 문제인데 FFT 오차가 ..

오랜만에 찾아온 백준 포스팅이에요~! 7.15에 군대에 가는데 그 전에 루비를 찍고 가려고 열심히 문제 풀고 있습니다!최근에 클8도 따고 해서 루비까지 남은 레이팅은 21점!!! 남은 레이팅은 제가 좋아하는 정수론으로 채울겁니다!아 정수론 오랜만에 하니까 감이 좀 떨어진듯 하네요;; 일단 각 쿼리를 각각 처리해봅시다.  첫 번쨰 쿼리$N=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{t}^{r_{t}}$가 $N$의 소인수분해라고 합시다. 주어진 $a$에 대하여 $a^{e}\equiv 1\pmod{N}$을 만족하는 최소의 $e$를 찾기 위해서는 먼저 $\gcd(a,N)=1$이어야 합니다. $\gcd(a,N)=1$을 가정해두고 논의를 진행합시다. $a$의 위수를 찾기 위해서 다음 렘마를 사..

본 글은 다음 세 논문을 바탕으로 쓰여 있습니다. 우리는 크기가 $p\times q$, $q\times r$인 두 행렬을 곱하는 cost를 $pqr$이라고 생각합니다. 행렬 $M_{1}\times \cdots \times M_{n-1}$을 곱하는데 필요한 최소의 연산 횟수는 얼마일까요? $M_{i}$의 크기를 $w_{i}\times w_{i+1}$이라고 두고 $w_{1}$부터 시계 방향으로 꼭짓점에 $w_{i}$들을 할당하여 $w_{n}$으로 끝나는 아래의 볼록 다각형을 생각해봅시다. Part 1. Lemma 1에서는 위 볼록 다각형을 partition하는 것이 행렬들의 연산 순서와 대응된다고 합니다. 볼록 다각형의 partition의 cost는 partition으로 만들어지는 삼각형들의 각 가중치를 합..

새로운 유형을 도전해서 그런가 좀 어려운 문제였다. 우리는 1부터 $2^{64}-1$까지의 수를 모두 2진수로 표현할 수 있다. 그리고 진수로 표현된 자릿수를 이용해서 모든 수를 64-dimensional vector에 대응시키자. 우리는 각 bit의 자릿수에 대해서 xor 연산을 생각하기 때문에 base field가 $\mathbb{Z}/2\mathbb{Z}$인 64-dimensional vector space를 고려한다. 그렇게 된다면 덧셈이 곧 xor연산이 된다. 이제 Xorshift64 함수는 linear operator로써 작동하고 이에 대응되는 행렬 $M\in M_{64\times 64}(\mathbb{Z}/2\mathbb{Z})$를 생각할 수 있다. 이 행렬을 구하는 방법은 vector sp..