-
Solving Univariate Polynomial over Finite Field
서론 최근 finite field 위에서는 univariate polynomial을 빠르게 풀 수 있다는 소프트웨어 멤버십 노규민 님의 말씀을 들었습니다. 일반적인 합성수 modulus 위에서 Coppersmith method 등을 통해서 작은 값을 가지는 해를 구하는 방법에 대해서만 접해보았기 때문에, 이 방법에 흥미를 느끼고 한 번 정리해보게 되었습니다. 본론 찾아보니 해를 구하는 것은 Polynomial factorization과 밀접한 관련이 있어서, 유명한 Polynomial factorization 알고리즘인 Cantor–Zassenhaus algorithm을 알아보고, 이를 바탕으로 해를 구하는 방법에 대해서 알아보려고 합니다. Cantor–Zassenhaus algorithm Cantor–Zassenhaus algorithm의 메인 아이디어는 equal-degree factorization,...
-
Top Tree로 Dynamic Tree 관리하기
Top Tree로 Dynamic Tree 관리하기 이 글을 읽기 이전에 동적 계획법을 최적화하는 9가지 방법 (4/4) 의 “Dynamic Tree DP” 단원을 이해하는 것이 좋다. 이 글은 해당 내용을 잘 이해하고 있다고 가정하고 설명한다. 그래프의 특수한 경우인 트리는 PS를 포함한 알고리즘 전반에서 자주 활용되는 구조이다. 트리는 일반적인 그래프에 비해 여러 방면으로 효율적으로 관리할 수 있다. 이러한 방법은 그 자체로도 관심의 대상이 되며, 그래프 문제를 풀 때도 다양하게 응용할 수 있다. 너무나도 중요하다는 사실이 잘 알려져 있으니, 구태여...
-
Quine: 자기 자신의 소스코드를 출력하는 프로그램
우리가 주로 프로그래밍을 하는 목적은 문제를 효율적으로 풀거나, 특정 작업을 편리하게 처리하기 위해서일 것입니다. 그러나 어디서나 재미를 추구하는 것은 사람의 본능이기에, 오직 호기심과 흥미만을 목적으로 전혀 실용적이지 않은 코드를 짜는 경우도 꽤나 있습니다. 얼마나 창의적이게 이상한 C언어 코드를 작성했는지 겨루는 IOCCC라는 대회가 존재할 정도입니다. 이 글에서는, 쓸모는 없지만 신기한 프로그램의 대표적 예시인 ‘콰인(Quine)‘과 그 이론적 배경에 대해 알아보도록 하겠습니다. 콰인이란? 콰인(Quine) 은 실행했을 때 자기 자신의 소스 코드를 출력하는 프로그램을 이르는 말로, 미국의 철학자이자 논리학자인...
-
Deep Graph Library 소개
Introduction 우리가 흔히 알고 있는 인공 신경망에는 가장 기본적인 Fully-connected network 그리고 Convolutional Neural network (CNN)나 Recurrent Neural network (RNN) 등이 있습니다. 이러한 인공 신경망들은 보통 벡터나 행렬 형태로 input이 주어집니다. 하지만 input이 그래프인 경우에는 벡터나 행렬 형태로 나타내는 대신에 Graph Neural Network (GNN)를 사용할 수 있습니다. GNN의 기본 원리와 간단한 예시에 대해서는 지난 글 1 에서, GNN의 시간 및 공간 복잡도에 대해서는 지난 글 2에서 알아보았습니다. 이번에는 GNN을 조금 더 쉽게 사용할 수 있는...
-
Multi-Party Computation 2
1. Introduction 저번 시간에 이어서 Multi-Party Computation을 살펴보겠습니다. 저번 시간에는 MPC를 할 수 있는 Garbled Circuit을 만드는 방법을 알아보고 Garbled Circuit이 처음 등장한 1982년부터 Half-gates technique이 발표된 2015년까지 어떠한 흐름을 통해 발전해왔는지 확인했습니다. 이번 시간에는 실제 Garbled Circuit을 구현할 때에는 어떤 방법을 이용하는지, 그리고 그와 관련한 안전성과 공격을 살펴보겠습니다. 2. Half-gates technique 저번 글에서는 이 Half-gates technique에 관해 아주 간략하게 설명을 하고 넘어갔습니다. 그러나 이번 글에서 본격적으로 안전성에 대해 논의를 하다보면 Half-gates technique의 동작에 대해...