Ubuntu PPTP VPN Server
pptpd 설치
다음 명령어를 실행한다.
sudo apt-get install pptpd
~
ip 설정
/etc/pptpd.conf 파일의 맨 마지막에 다음을 추가한다.
localip 192.168.0.1 remoteip 192.168.0.100-200
~
DNS 설정
/etc/ppp/pptpd-options 파일의 ms-dns 항목을 주석해제하고 수정한다.
ms-dns 8.8.8.8 ms-dns 8.8.4.4
~
사용자 추가
/etc/ppp/chap-secrets 파일에 사용자를 추가한다. "(아이디) pptpd (비밀번호) (IP)" 형식으로 한 줄에 하나씩 적으면 된다.
cubelover pptpd p4ssw0rd 192.168.0.123 guest pptpd guest *
~
interface 이름 알아내기
다음 명령어를 실행하면 interface가 여러 개 나오는데, 이 중 vpn에 routing할 interface의 이름을 찾는다. 유선랜을 사용하는 경우 보통 eth0지만 아닌 경우도 있다.
ifconfig -a
~
iptables 설정
앞에서 알아낸 interface의 이름을 (interface)에 넣고 실행한다.
iptables -t nat -A POSTROUTING -s 192.168.0.0/24 -o (interface) -j MASQUERADE
~
ip forwarding 설정
/etc/sysctl.conf 파일에서 net.ipv4.ip_forward=1 항목을 주석해제한다. 그리고 다음 명령어를 실행한다.
sudo sysctl -p
~
pptpd 재시작
다음 명령어를 실행한다.
sudo pptpd restart
~
UFW 설정 (UFW를 사용하는 경우)
/etc/default/ufw 파일에서 DEFAULT_FORWARD_POLICY를 ACCEPT로 고쳐준다.
DEFAULT_FORWARD_POLICY="ACCEPT"
/etc/ufw/before.rules 파일에서 *filter 앞 부분에 다음을 추가한다.
# nat Table rules *nat :POSTROUTING ACCEPT [0:0] # Allow traffic from clients to eth0 -A POSTROUTING -s 192.168.0.0/24 -o eth0 -j MASQUERADE # commit to apply changes COMMIT
그리고 # drop INVALID packets 바로 다음에 다음을 추가한다.
-A ufw-before-input -p 47 -i $iface -j ACCEPT
다음 명령어를 실행한다.
sudo ufw allow 1723 sudo ufw disable sudo ufw enable
~
여기까지 잘 동작하는 지 확인한다. 잘 동작한다면 재부팅할 때 iptable이 날아가는 것을 방지하기 위해서 저장해뒀다가 부팅할 때 불러오도록 해야 한다.
다음 명령어를 실행한다.
sudo su iptables-save > /etc/iptables.rules exit
/etc/rc.local 파일의 exit 0 이전에 다음을 추가한다.
/sbin/iptables-restore < /etc/iptables.rules
'...' 카테고리의 다른 글
ONTAK 2010 Day 7 Generator (0) | 2018.07.17 |
---|---|
BOJ Achievements (0) | 2018.05.17 |
Baekjoon Online Judge 13538 (3) | 2016.11.03 |
Baekjoon Online Judge 1659 (0) | 2016.02.02 |
1 이상 N 이하의 정수에서 i의 빈도수 (0) | 2016.01.27 |
Indexed Tree with template
#include <cstdio> #include <functional> using namespace std; template <typename _T> class IndexedTree { private: size_t m; _T *A; function<_T(const _T &, const _T &)> F; public: IndexedTree(size_t n, function<_T(const _T &, const _T &)> f) { for (m = 1; m < n; m <<= 1); A = new _T[m << 1]; F = f; } void Update(size_t idx, _T val) { idx |= m; A[idx] = val; while (idx >>= 1) A[idx] = F(A[idx << 1], A[idx << 1 | 1]); } _T Query(size_t L, size_t R) { _T Lval = _T(), Rval = _T(); L |= m; R |= m; while (L <= R) { if (L & 1) Lval = F(Lval, A[L++]); if (!(R & 1)) Rval = F(A[R--], Rval); L >>= 1; R >>= 1; } return F(Lval, Rval); } }; int a[10] = { 6, 2, 3, 8, 4, 5, 1, 9, 7, 10 }; int main() { IndexedTree<int> IT(10, [](auto u, auto v) { return u + v; }); for (int i = 0; i < 10; i++) IT.Update(i, a[i]); printf("%d %d : %d\n", 2, 6, IT.Query(2, 6)); printf("%d %d : %d\n", 3, 8, IT.Query(3, 8)); return 0; }
'구현' 카테고리의 다른 글
Stable Radix Sort (0) | 2016.10.21 |
---|
Dividing Polynomials
다항식의 나눗셈이란, \(x\)에 대한 \(n\)차 다항식 \(f(x)\)와 \(x\)에 대한 \(m\)차 다항식 \(g(x)\)에 대하여, 다음을 만족하는 \(x\)에 대한 \(n-m\)차 다항식 \(q(x)\)와 \(m-1\)차 다항식 \(r(x)\)를 구하는 것을 말한다. (\(n \ge m\))
\[f(x)=g(x)q(x)+r(x)\]
이는 높은 차수부터 하나씩 지워 나가는 것으로 \(O(n^2)\) 시간 안에 행할 수 있지만, 여기서는 Discrete Fourier Transform을 이용하여 \(O(n \log n)\)의 시간에 행하는 방법을 소개한다.
~
먼저, \(x\)에 \(z^{-1}\)을 대입하고, 양변에 \(z^n\)을 곱해보자.
\[z^nf(z^{-1})=(z^m g(z^{-1}))(z^{n-m}q(z^{-1}))+z^{n-m+1}(z^{m-1}r(z^{-1}))\]
여기서 \(z^nf(z^{-1})\), \(z^m g(z^{-1})\), \(z^{n-m}q(z^{-1})\) 그리고 \(z^{m-1}r(x)\)는 \(f(x)\), \(g(x)\), \(q(x)\), \(r(x)\)의 계수 순서를 바꾸고 \(x\) 대신에 \(z\)를 적은 것임을 알 수 있다.
이제부터 이들을 \(F(z)\), \(G(z)\), \(Q(z)\), \(R(z)\)라 하자. 그러면 다음처럼 정리할 수 있다.
\[F(z)=G(z)Q(z)+R(z)z^{n-m+1}\]
여기서 \(Q(z)\)는 \(z\)에 대한 \(n-m\)차 다항식임에 유의하자. 만약 \(G(z)H(z)=1\mod z^{n-m+1}\)을 만족하는 다항식 \(H(z)\)가 존재한다면, 우리는 \(Q(z)\)를 다음처럼 나타낼 수 있다.
\[Q(z)=F(z)H(z) \mod z^{n-m+1}\]
\(H(z)\)를 찾을 수만 있다면 Fast Fourier Transform을 이용하여 \(Q(z)\)를 \(O(n\log n)\)의 시간에 구할 수 있다. 이후 계수 순서만 바꾸면 \(q(x)\)를 구할 수 있다.
또한 \(r(x)=f(x)-g(x)q(x)\)인 점을 이용하여 \(r(x)\)도 \(O(n \log n)\)의 시간에 구할 수 있다.
~
그렇다면 \(G(z)H(z)=1\mod z^{n-m+1}\)을 만족하는 다항식 \(H(z)\)는 어떻게 구할까?
\(g(x)\)의 차수가 \(m\)이라고 했으므로, \(G(z)\)의 상수항은 \(0\)이 아님을 알 수 있다.
따라서 \(G(z)\)의 상수항을 \(c\)라 하면, \(G(z)(1/c)=1 \mod x\)임을 알 수 있다.
\(G(z)U(z)=1 \mod x^k\)을 만족하는 다항식 \(U(z)\)를 알고 있다고 할 때, \(G(z)V(z)=1 \mod x^{2k}\)를 만족하는 다항식 \(V(z)\)는 다음의 꼴을 가진다.
\[V(z)=U(z)+T(z)z^k \mod z^{2k}\]
\(G(z)\)를 \(k-1\)차 다항식 \(G_0(z)\)와 \(m-k+1\)차 다항식 \(G_1(z)\)에 대하여 \(G(z)=G_0(z)+G_1(z)z^k\)꼴로 나타냈을 때 \(G_0(z)U(z)=1+W(z)z^k\)라 하면
\[G(z)V(z)=(G_0(z)+G_1(z)z^k) (U(z)+T(z)z^k)=1+(W(z)+G_0(z)T(z)+G_1(z)U(z))z^k \mod z^{2k}\]
\[W(z)+G_0(z)T(z)+G_1(z)U(z)=0 \mod z^k\]
여기서 우리는 \(G_0(z)U(z)=1 \mod z^k\)임을 알고 있으므로
\[U(z)W(z)+T(z)+G_1(z)U^2(z)=0\mod z^k\]
\[T(z)=-U(z)(W(z)+G_1(z)U(z))\mod z^k\]이상을 정리하면
\[V(z)=U(z)(1-W(z)z^k-G_1(z)U(z)z^k)=U(z)(2-G_0(z)U(z)-G_1(z)U(z)z^k)=U(z)(2-G(z)U(z))\mod z^{2k}\]
\(k\ge n-m+1\)이 될 때까지 이를 반복하면 \(G(z)H(z)=1\mod z^{n-m+1}\)을 만족하는 다항식 \(H(z)\)를 구할 수 있다.
\(G(z)U(z)\)를 구하는 부분에서 Fast Fourier Transform을 사용하면 \(O(n\log n)\)의 시간에 \(H(z)\)를 구할 수 있다.
~
즉, \(f(x)/g(x)\)를 구하는 과정은 다음과 같다.
1. \(f(x), g(x)\)의 계수 순서를 바꿔 \(F(z), G(z)\)를 만든다.
2. \(G(z)\)의 상수항을 \(c\)라고 할 때, \(H(z)\leftarrow1/c, k\leftarrow1\)로 놓는다.
3. 다음 과정을 \(k\ge n-m+1\)이 될 때까지 반복한다.
3-1. \(k\leftarrow2k\)
3-2. \(H(z)\leftarrow H(z)(2-G(z)H(z)) \mod z^k\)
4. \(Q(z)\leftarrow F(z)H(z) \mod z^{n-m+1}\)
5. \(Q(z)\)의 계수 순서를 바꿔 \(q(x)\)를 구한다.
6. \(r(x)\leftarrow f(x)-g(x)q(x)\)
여기서 모든 다항식 곱셈에는 Fast Fourier Transform을 사용하고, \(\mod z^k\)인 경우 \(k\)차 이상의 항을 무시하고 계산하면 \(O(n\log n)\)의 시간에 나눗셈을 행할 수 있다.
'수학' 카테고리의 다른 글
きたまさ法 (0) | 2016.11.24 |
---|---|
Discrete Fourier Transform (0) | 2016.11.17 |
Number Theoretic Fast Fourier Transform (1) | 2016.11.02 |