-
공개 키 암호화 시스템과 수학적 안전성
이 글에서는 공개 키 암호화 시스템이 발전해나가면서 같이 논의된 수학적 개념을 살펴보고자 합니다. 특히, 암호문으로부터 평문을 알아낼 수 없다는 막연한 속성을 수학적으로 어떻게 표현하는지 알아보고자 합니다. 목차는 다음과 같습니다. 공개 키 암호화 시스템 배경 지식 공개 키 암호화 시스템의 정의 Diffie-Hellman Key Exchange RSA 암호 One-wayness CPA Semantic Security and Indistinguishability Chosen Ciphertext Attack Random Oracle Model Malleability RSA-OAEP 마무리 각주 공개 키 암호화 시스템 공개 키 암호화 시스템Public Key Cryptosystem, PKC은 W. Diffie와 M....
-
프로그래밍 문제 출제하기
서론 삼성 소프트웨어 멤버십 블로그에는 대회 개최에 관한 글을 몇 개 찾아볼 수 있습니다. 대회 준비와 운영이 어떻게 진행되는지를 알 수 있는 유용한 글입니다. Acka1357님의 프로그래밍 대회를 개최하기 위한 10가지 djm03178님의 Codeforces #578, Codeforces #620 출제 후기 evenharder님의 UCPC 2020, KCPC 2018 출제 후기 hojoon0205님의 shake! 2019 출제 후기 이 글은 문제를 어떻게 만들 것인가에 초점을 둡니다. 아이디어를 어떻게 구상하고, 지문은 어떻게 작성하고, 데이터는 어떻게 만들고, 문제 검수는 어떻게 해야 하는지를 다룹니다. 백준 온라인 저지에...
-
Codeforces 레이팅의 경향 분석
서론 이전 글에서 Codeforces의 레이팅 계산법에 대해 다루어 보았습니다. 이번 글에서는 기존 라운드들에서의 통계를 이용하여 이 레이팅 체계가 어떤 경향을 보이고 있는지 살펴보고, 여기서 발견되는 구조적인 문제점의 원인을 분석해 보려고 합니다. 어떤 레이팅 시스템이 이상적이라면 각 참가자가 해당 라운드에서 기록한 ‘성적’에 따라 레이팅의 변화가 이루어져야 할 것인데, 많은 사람들의 경험에 의하면 특정 종류의 라운드에 참가하는 것이 다른 종류의 라운드에 참가하는 것에 비해 레이팅을 얻기가 훨씬 쉽다고 합니다. 이 현상이 어느 정도 심각한지를 집중적으로 조사해 보았습니다....
-
양자 컴퓨팅 - Surface Code
최근 양자 컴퓨팅의 error detection 및 correction에 사용되는 surface code의 기초를 잘 설명한 논문인 Surface codes: Towards practical large-scale quantum computation을 접했습니다. 이 포스트를 통해 양자 컴퓨팅에서 어떻게 error detection을 진행하고, surface code가 어떤 개념인지 설명하고자 합니다. 배경 지식 Shor’s Algorithm이나 Grover’s Algorithm 등의 양자 알고리즘이 개발되며 양자 컴퓨팅에 대한 관심이 커졌습니다. 2020년 현재 IBM Q Experience나 Amazon Braket, Microsoft QDK 등으로 양자 컴퓨팅 프로그래밍 언어를 사용할 수도 있습니다. 그러나 이런 시스템이 물리적인 양자 체계와...
-
P VS NP Question
P vs NP Question Contents 들어가며 P NP 란? 여러가지 NP문제들 PSPACE 와 NSPACE P = NP? 참고 들어가며 예전에 비해 프로그래밍이 좀 더 보편적인 분야로 자리잡으면서, 남녀노소 할 것 없이 많은 사람들이 프로그래밍을 접하고 있다. 또한 문제풀이로 알려진 Problem Solving 쪽을 많은 기업체 또는 학교에서 평가의 기준또는 test로 삼고 있다. 이러한 PS는 여러가지 분야가 있지만, 대부분이 주어진 제한적인 상황안에서 문제를 해결하게 된다. 보통 PS공부를 하기 위해서 알고리즘 공부가 필수라고 얘기한다. 그렇다면 알고리즘이란 무엇일까? 알고리즘을...