지난번 글에서는 이산 로그 문제에 대해 다뤘으니 이번에는 소인수분해 문제를 해결하는 알고리즘에 대해 알아보자. 코드는 이전과 마찬가지로 아래와 같은 수정이 들어간 파이썬 문법을 따랐다.
양 끝을 명시적으로 나타내기 위해 range(st, ed+1) 대신 [st...ed]와 같은 표기를 사용했다. 파이썬에서 거듭제곱을 나타내는 a**b 대신 일반적으로 사용되는 a^b 표기를 사용했다. 지난 이산 로그 문제와는 달리 모두가 알 것이라 믿고 소인수분해 문제에 대한 자세한 설명은 생략한다. 또한 알고리즘 설계를 간단히 하기 위해 소인수분해 문제의 요구조건을 주어진 자연수 n에 대해, 1과 자기 자신(=n)을 제외한 약수를 발견하는 것으로 정했다.
직장 도서관에서 책을 빌릴 수 있긴 하지만 책을 신청하면 빨라도 1주일 후에 구매되는 일이 많고, 약속시간이 애매하게 남거나 굳이 책을 넣어갈 가방이 없는 경우(ex: 노트북 파우치) 종이책을 들고다니기엔 부담스러웠던 적이 종종 있었다. 그러던 중 지난 4월 초 직장에서 상여금이 나왔고(!) 주변 지인들로부터 전자책에 대한 긍정적인 평을 많이 들었던 터라 전자책 리더기를 하나 장만했다.
암호학, 특히 공개키 기반 암호시스템은 주로 1)소인수분해 문제 혹은 2)이산 로그 문제를 기반으로 설계되는 경우가 많다. 그중 이산 로그 문제와 이를 해결하는 알고리즘에 대해 알아보자. 예시로 든 코드는 기본적으로 파이썬 문법을 따라 작성했으며 가독성을 위해 다음과 같은 부분을 수정했다.
파이썬에서 range(n)은 0부터 시작해 n이 아닌 n-1까지를 포함한다. 양 끝을 명시적으로 나타내기 위해 [st...ed]와 같은 표기를 사용했다. 파이썬에서 거듭제곱을 나타내는 a**b 대신 일반적으로 사용되는 a^b 표기를 사용했다. mod p에서의 역원을 a^(-1)로 표기했다. 실제 구현에서는 다음과 같이 구할 수 있다. 페르마 소정리에 의해 $a^{p-1} \equiv 1 \pmod p$이므로 $a\cdot a^{p-2} \equiv 1$에서 $a^{-1} \equiv a^{p-2}$ $p$가 소수가 아닌 경우, 확장 유클리드 알고리즘을 사용한다 이산 로그 문제 이산 로그 문제는 이산 대수 문제라고도 하며, 순환군 $\langle g \rangle$와 군의 원시근(primitive root) $g$, 그리고 $y \in \langle g \rangle$ 가 주어졌을 때, $y=g^k$를 만족하는 최소의 자연수 $k$를 찾는 문제이다. 암호학에서는 큰 소수 $p$에 대해 $p$로 나눈 나머지들의 모임인 $\mathbb{Z}_p^\ast$를 사용하는 경우가 많다.
발상: Knockoff Nets 어제(2일) 대학원에서 Mario Fritz 박사님의 AI Security에 대한 강연을 들어볼 수 있었다. 딥러닝이 대세가 되면서 등장한 여러 보안 문제들에 대한 특강이었는데, 그중 Model Stealing(구체적으로는 Functionality Stealing)에 대해 다룬 knockoff-net 관련 내용이 흥미로워 pytorch로 구현해보았다. 다만 노트북이라는 한계로 원본 논문보다는 디테일을 다소 단순화했다(…)
예제 dataset 가져오기 지금까지는 \(y=ax+b\)나 \(y=ax^2+bx+c\) 처럼 간단한 형태의 숫자→숫자 함수만을 모델링했으니 이제 좀더 흥미로운 데이터를 살펴보자.
딥러닝, 특히 이미지 인식 관련 예제를 보면 MNIST나 CIFAR-10같은 이름이 많이 등장한다. 이 둘은 Image Classification 문제의 대표적인 예시로 각각 손글씨와 물체 사진 이미지셋에 해당하며, 흔히 모델의 벤치마크 용도로 활용되고 있다. 이번 글에서는 좀더 단순한 MNIST를 사용하기로 한다. MNIST 데이터는 아래와 같이 색이 없는 1채널(=gray scale) 28x28픽셀 이미지들의 모음으로 0에서 9까지 총 10개의 라벨을 가지고 있다.
학습의 각 단계를 추상화하기 앞서 그래디언트를 이용해 간단한 학습이 이루어지는 과정을 알아보았다. 이전 글의 마지막 코드를 다시 살펴보면 학습의 한 round를 크게 다음과 같은 단계들로 추상화시킬 수 있다.
for i in range(num_adjust): # 1) 파라미터를 이용해 입력(xs)으로부터 예상 결과를 생성 y_pred = a*xs + b # 2) 예상 결과(y_pred)와 실제 결과(ys)를 비교해 오차를 계산 err = ((y_pred - ys)**2).mean() # 3) .backward()를 통해 각 파라미터가 오차에 관여하는 정도를 역산 err.backward() # 4) 역산된 grad를 바탕으로 파라미터 수정 a.data.sub_(0.01 * a.grad) b.data.sub_(0.01 * b.grad) # 5) 파라미터들의 grad값을 0으로 초기화 a.grad.zero_() b.grad.zero_() 그런데 이번과 같이 모델이 \(y=ax+b\) 처럼 간단한 형태인 경우 파라미터(a, b)들을 각자 관리할 수 있지만, 복잡한 모델의 경우 이는 상당히 번거로운 과정이 될 수 있다. 흩어진 파라미터들을 통합해 관리한다면 어떤 형태가 가능할지 생각해 보자.
요새는 뭘 찾아봐도 딥러닝이 나온다..
성향이 continuous, gradient 같은 거랑은 안 맞아서 최대한 피해보려고 했지만 결국 시대의 흐름에 거스르지 못하고 어떻게 사용하는지 정도는 알아두는게 좋을 것 같아서 정리해봤다.
요구사항(prerequisite) python에 대한 기초지식 (ex: ABC.xyz()는 클래스/객체 ABC 안에 있는 xyz 라는 함수를 호출하는 것이다) 함수에 대한 개념(규칙에 따라 input → output으로 이어지는 블랙박스로 이해해도 된다) 머릿속 이미지화를 위한 약간의 상상력(?) tensor 클래스 tensor는 \(n\_1 \times n\_2 \times \cdots \times n\_d \) 개의 숫자를 \(d\)차원으로 정렬한 객체이다. 편의상 예시는 2차원 이하만을 다룰 예정이지만 임의의 차원을 가질 수 있다는 점은 알아두자.
TL;DR : 아무래도 페이스북 티셔츠와는 연이 없는 모양이다(…)
2018년 해커컵에 이어 2019년도 페이스북 해커컵 대회가 열렸다. 이번에는 지난번같은 실수 없이 티셔츠, 운이 좋다면 Round 3까지 진출하는 걸 목표로 삼았지만 결국 달성하지 못했다. 일요일 새벽 2시에 열리는 Round 2를 위해 토요일 저녁에 미리 잠들고, 알람까지 맞춰놨지만 눈을 뜨니 2시 23분이었고 급하게 노트북을 켰지만 이미 대회 시작에서 30분이 지난 상황이었다.
TL;DR : 코드잼 티셔츠 받음
2019년 코드잼 본 대회를 치렀다. 몇 번 글을 썼던 Kickstart와는 달리 1년에 1번밖에 열리지 않는 대회이고, 작년엔 훈련소에 있느라 참가를 못 해서인지 조금은 긴장된 마음이었다. 대학 시절 내내 코드잼, 해커컵을 통틀어 티셔츠와는 인연이 없었기에 이번에야말로 하나 받아내겠다는 생각을 했다.
구글 코드잼(Google Code Jam)은 이름에서처럼 구글에서 주최하는 코딩대회로 Qualification Round와 온사이트 World Final을 포함해 총 5단계로 이루어진다. World Final은 전 세계를 통틀어 상위 25명밖에 나갈 수 없어 기대조차 안했고(…) 그 이전 단계인 Round 3(세계 상위 1000명)까지를 목표로 삼았다.
지난 25일 목요일, 삼성역 인근 서울 파르나스 호텔에서 FireEye Cyber Defense Live 2019 Seoul 컨퍼런스가 열렸다. Cyber Defense Live는 미국의 보안회사 FireEye에서 주최하는 컨퍼런스로 국제 사이버 보안의 최근 동향과 공격/방어에서의 새로운 인사이트 제시, 기업 차원에서의 PR 등 다양한 주제가 포함되어 있었다. 사실 이런 컨퍼런스가 있는 줄도 몰랐는데 직장에서 출장으로 보내줌
