-
read, write, mmap을 이용한 Fast I/O 구현 (1)
Introduction 입출력 연산은 C++에서 가장 무거운 연산 중 하나입니다. 일반적인 산술 및 논리 연산은 대략 $1$초에 $1$억 번 정도 수행할 수 있는 것으로 알려져 있지만, 입출력 연산은 입력 또는 출력 값의 개수가 $10^5$ 이상만 되어도 입출력 속도가 전체 실행 시간에 상당한 영향을 줄 수 있습니다. (참고) 이럴 때 표준 스트림 함수인 cin, cout 대신 read, write와 같은 저수준 입출력 함수를 사용하면 입출력 시간을 유의미하게 줄일 수 있습니다. 다만 이 함수들은 문자열 이외의 자료형을 자동으로 처리하지...
-
cracking mysql_hash_password
Intro 안녕하세요, kwoncycle입니다. 이번 글에서는 mysql_hash_password 라는 해시 함수를 crack하는 방법에 대해 다룹니다. mysql_hash_password 함수는 2000년 이전에 MySQL에서 사용된 비밀번호 해시 함수로, 해시 로직은 아래의 코드와 같습니다. def mysql_hash_password(password): nr = 1345345333 add = 7 nr2 = 0x12345671 for c in password: if c == 32 or c == 9: continue nr ^= (((nr & 63) + add) * c) + (nr << 8) & 0xFFFFFFFF nr2 = (nr2 + ((nr2 << 8) ^ nr))...
-
TFHE : Fully Homomorphic Encryption over the Torus - 2
Introduction 안녕하세요. 지난 게시글에서는 동형암호 scheme중 하나인 TFHE의 암호화 / 복호화 / 덧셈 연산에 대해서 다루었습니다. 그리고 다음 게시글에서는 TFHE의 곱셈에 대해 다루기 위해서 GSW scheme과 gadget decomposition을 다루었는데요, 이 글의 이해를 위해서는 두 게시글을 읽고 오시길 추천드립니다! 이번 글에서는 TFHE에서의 곱셈(external product)가 어떻게 진행되는지와, 그리고 이러한 연산을 통해서 최종적으로 TFHE의 bootstrapping이 어떤 식으로 진행되는지에 대한 개괄적 설명을 하고자 합니다! TFHE Multiplication(External Product) Gadget Decomposition Gadget decomposition을 처음 접하시는 분은 이 글 의 설명을 읽으신다면...
-
Block Decomposition을 이용한 Online FFT 구현
Introduction 이 글에서는 Block Decomposition을 이용한 Online FFT(Fast Fourier Transform) 구현 방법을 소개합니다. 두 수열 $A$, $B$의 convolution $C$를 $\mathcal{O}(n\log n)$에 구하는 FFT 알고리즘은 두 수열 $A$, $B$가 모두 주어져야만 사용할 수 있습니다. Online FFT는 $A$, $B$의 원소 $a_i$, $b_i$가 하나씩 주어질 때 $c_i$를 온라인으로 구하는 알고리즘입니다. 이는 점화식이 convolution 형태이면서 $c_0, \cdots, c_{i-1}$을 알아야 $a_i$, $b_i$를 구할 수 있는 경우(예를 들면 카탈란 수 $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$)에 사용할 수 있습니다. Online FFT는 여러...
-
Custom Select Box 만들기 (overflow 문제 해결) - (Nuxt3, Vue3)
Intro 안녕하세요. 이번 글에서는 Nuxt3에서 Custom Select Box를 구현해보려고 합니다. 이때, overflow를 허용하는 Component 내부에 존재하는 Custom Select Box에 대해 생기는 스크롤 문제를 해결하는 것이 이 글의 목표입니다. 명확한 해결책을 제시해 주는 곳이 없어 이를 해결할 수 있는 방법을 공유하고자 합니다. 또한, Select Box 외에도 Tooltip과 같이 특정 컴포넌트가 position: absolute인 상태로 상대 위치를 계산해야 하는 상황에서도 동일한 방법으로 해결할 수 있습니다. Nuxt3로 작성된 글이긴 하지만, javascript 기반으로 작동하는 여러 트릭이 많아서 굳이 Nuxt3를 몰라도,...