-
Rabin-Karp 해싱의 충돌쌍 찾기
안녕하세요, 이번 글에서는 Rabin-Karp 해싱의 충돌쌍을 찾는 다양한 방법에 대해 알아보겠습니다. Rabin-Karp 해싱이란? Rabin-Karp 해싱은 문자열의 해쉬함수입니다. 이 글의 내용에서 알 수 있듯이 암호학적으로 안전한 함수는 아니지만 $O(N)$의 전처리를 거치고 나면 문자열 내의 임의의 substring의 해쉬 값을 $O(1)$에 알 수 있다는 특성 덕분에 해당 특성이 필요할 때 활용하면 효과적입니다. 또한 구현이 쉬운 편이기 때문에 굳이 암호학적으로 안전한 함수가 필요없는 상황일 경우에는 Java와 기본 String hashcode를 포함한 다양한 곳에서 사용되고 있습니다. 해싱에 대한 자세한 설명은 제...
-
강화학습 핵심 개념 정리 (1)
강화학습 핵심 개념 정리 (1) Reinforcement Learning Key Concepts 이 시리즈의 목표는 강화학습을 잘 모르는 사람이 해당 분야의 전반적인 흐름을 파악하고 이 글을 토대로 세부적인 내용을 찾아볼 수 있게 하는 것입니다. 이번 글에서는 여러가지 주요 용어를 살펴보고, 다음 글에서는 Q learning 과 Policy Gradient 에 대해서 살펴보겠습니다. 문제 정의 강화학습에서 다루는 문제가 어떤 것인지부터 살펴봅시다. 주변 상태에 따라 어떤 행동을 할지 판단을 내리는 주체인 에이전트가 있고, 에이전트가 속한 환경이 있습니다. 에이전트가 행동을 하면 그에 따라...
-
Forgery Attack on ElGamal Signatures
서론 최근에 한 문제에 대한 질문을 받았습니다. FuzzyLand라는 사이트의 WebShop 2.0 이라는 문제로, ElGamal signature 에 대한 공격을 요구하는 문제였습니다. 문제를 풀다보니 아이디어가 흥미로워서 공유하게 되었습니다. 본론 ElGamal Signatures ElGamal signature는 RSA signature와 비슷하게 discrete logarithm의 어려움에 바탕을 둔 signature scheme입니다. ElGamal signature는 다음과 같은 방식으로 돌아갑니다. 파라미터 및 생성 어떤 $N$-bit 소수 $p$를 고릅니다. 그리고 Hash function $H$를 고릅니다. 2부터 $p-1$ 사이의 어떤 수 $g$를 고릅니다. 이 수를 generator라고 부릅니다. 이 때 generator라고 불리는...
-
Knuth's Algorithm X
안녕하세요? 오늘은 Knuth’s Algorithm X에 대해 알아보도록 하겠습니다. Knuth’s Algorithm X는 기본적으로 Brute-Force 알고리즘의 일종이지만, 성능이 좋은 편에 속하고 그 과정이 상당히 아름답습니다. Knuth’s Algorithm X Knuth’s Algorithm X는 간단히 말해, 어떠한 집합의 exact cover를 찾는 알고리즘입니다. Exact cover란 무엇인지, 간단한 예시를 통해 살펴보도록 하겠습니다. 집합 X = {1, 2, 3, 4, 5, 6, 7}이 있고, 집합 X의 부분집합의 집합인 집합 S가 주어집니다. S = {A, B, C, D, E, F}라고 하고 각각을 다음과 같이...
-
Effective Modern C++ (2)
저번시간에 이어서 오늘은 예전에 Effective Modern C++ 을 공부하며 정리했던 내용들을 포스팅해볼까 합니다~ C++11/14 에서의 best practice 에 관한 내용으로서 최근 C++20 이 나오는 시점에서 이 또한 최신 내용은 아니긴 하지만 여전히 많은 부분들이 유효합니다. Chapter 4. 똑똑한 포인터 (Smart Pointer) 항목 18. 소유권 독점 자원의 관리에는 std::unique_ptr를 사용하라. 보통 smart pointer를 처음 접한 사람들은 std::shared_ptr만을 남용(?)하는 경향이 있다.그러나 std::shared_ptr이 매우 강력한 존재이긴 하지만 크게 2가지 측면에서 단점이 있다. 첫 번째는 overhead이다. 참조 계수를 관리하기...