수학

피보나치수열의 성질

피보나치수열은 초등학생도 흔히 접하는 매우 간단한 형태의 수열이다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ... 그런데 이 간단한 수열에도 파고들면 수많은 수학적 의미를 찾을 수 있다. 한번 그 의미를 알아보자. 참고로 $F_n$이 의미하는 바는 $n$번째 피보나치 수로 $F_1=1$, $F_2=1$, $F_3=2$이다. 홀짝성(기우성) 아주 간단한 성질이다. 피보나치수열의 원소는 홀수, 홀수, 짝수, 그리고 반복을 이룬다. 이가 성립하는 이유는 다음과 같다. $F_1=1$ (홀수), $F_2=1$ (홀수)이다. 홀수+홀수=짝수이므로 다음 $F_3$은 짝수이고 $F_4$는 홀수+짝수=홀수가 되어 홀수 $F_5$는 짝수+홀수=홀수가 되어 홀수 $F_6$는 홀수+홀수=짝..

피보나치수열의 일반항

피보나치수열은 초등학생도 흔히 접하는 매우 간단한 형태의 수열이다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ... 피보나치수열을 수학적으로 쓰면 다음과 같다. 초기 조건: $F_1=1$, $F_2=1$ 점화식: $F_n=F_{n-1}+F_{n-2}$($n\geq 3$) 이 정도면 피보나치수열을 사용하는 데는 부족함이 없지만 큰 피보나치수, 가령 $F_{50}$을 계산하기엔 노가다가 심하다. 따라서 이번에는 피보나치수열의 일반항을 구해볼 것이다. 이 글을 읽기 전 동차점화식의 일반항을 먼저 읽어주세요! 이 글에서는 해당 개념을 응용할 것입니다. 항 3개를 사용하는 동차점화식의 일반형은 다음과 같다. $a_n=pa_{n-1}+qa_{n-2}$ 따라서 피보나치수열은 여기서 ..

동차점화식의 일반항

개요 수열에서 점화식이란 이전항을 이용해 다음 항을 알아내는 식이다. 예를 들어 어떤 수열 $a$에 대해 다음 식은 모두 점화식이다. $a_{n+1}=2a_n$ $a_{n+1}=a_n+4$ $a_{n+1}=3a_n+4$ $a_{n}=2a_{n-1}+3a_{n-2}$ 이 중 식 1, 2, 3 꼴의 점화식에서 일반항을 유도하는 방법은 이미 이 글에서 다루었다. 이번 글에서는 4번 형식의 점화식에서 일반항을 구하는 방법에 대해 알아보자. 동차점화식과 비동차점화식 점화식은 꼴에 따라 2가지 형태로 나눌 수 있다. 1번 식과 같은 꼴의 점화식을 "동차점화식"이라고 하고 2번 식과 같은 꼴의 점화식을 비동차점화식이라고 한다. $a_n=k_1 a_{n-1}+k_2 a_{n-2}+\cdots$$+k_m a_{n-m}$..

RSA 암호화 - RSA의 작동 원리

RSA 암호화 RSA 암호화 - 개념편 RSA 암호화 - 수학편: RSA와 소수 RSA 암호화 - 수학편: 나머지 계산 RSA 암호화 - RSA의 동작 방식 RSA 암호화 - RSA의 작동 원리 [알림] 이 글은 RSA 암호화 시리즈의 5편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다! 오일러 정리 RSA 암호화에서는 페르마 소정리가 일반화된 정리 격인 오일러 정리가 핵심 역할을 한다. 오일러 정리 서로소인 두 정수 $a$와 $n$에 대해 $a^{\phi (n)} \equiv 1\:(\mathrm{mod}\:n)$이다. 여기서 $\phi(n)$은 오일러 피 함수로 $n$ 미만의 자연수 중 $n$과 서로소인 수의 개수를 말한다. 오일러 피 함수는 자기 자신보다 작은 자연수 중 자신과 서로소인..

RSA 암호화 - RSA의 동작 방식

RSA 암호화 RSA 암호화 - 개념편 RSA 암호화 - 수학편: RSA와 소수 RSA 암호화 - 수학편: 나머지 계산 RSA 암호화 - RSA의 동작 방식 RSA 암호화 - RSA의 작동 원리 [알림] 이 글은 RSA 암호화 시리즈의 4편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다! RSA의 작동 방식 RSA는 다음 방식으로 작동한다. 키 쌍 생성: 아주 큰 두 소수 $p$, $q$를 생성한다. $N=pq$를 계산한다. $(p-1)(q-1)$과 서로소인 정수 $e$를 하나 정한다. $ed$를 $(p-1)(q-1)$로 나눈 나머지가 1인 정수 $d$를 계산한다. $p$와 $q$, $p-1$, $q-1$은 삭제한다. 공개키는 $N$과 $e$가 되고 비밀키는 $d$가 된다. 3단계에서 $e$..

RSA 암호화 - 수학편: 나머지 계산

RSA 암호화 RSA 암호화 - 개념편 RSA 암호화 - 수학편: RSA와 소수 RSA 암호화 - 수학편: 나머지 계산 RSA 암호화 - RSA의 동작 방식 RSA 암호화 - RSA의 작동 원리 [알림] 이 글은 RSA 암호화 시리즈의 3편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다! 특수한 형태의 나머지 연산의 필요성 RSA암호는 나머지 연산을 매우 자주 활용한다. 어떤 정수를 다른 정수로 나누었을 때의 나머지를 구하는 것이다. 컴퓨터 입장에서 나머지 연산은 매우 쉬운 일이다. C언어에서 $a$를 $b$로 나눈 나머지를 계산해서 $c$에 저장하는 코드는 다음 한 줄이면 된다. c=a%b; 이 방법은 매우 효과적이지만 RSA에 사용하기에는 적절하지 못하다. RSA에는 $a^b \equiv..

RSA 암호화 - 수학편: RSA와 소수

RSA 암호화 RSA 암호화 - 개념편 RSA 암호화 - 수학편: RSA와 소수 RSA 암호화 - 수학편: 나머지 계산 RSA 암호화 - RSA의 동작 방식 RSA 암호화 - RSA의 작동 원리 [알림] 이 글은 RSA 암호화 시리즈의 2편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다! 비대칭키 암호화의 기본 비대칭키 암호화는 비밀키로 공개키를 알 수는 있지만 공개키로는 비밀키를 알 수 없고, 두 키가 암복호화에 따로따로 사용돼야 하는 한 쌍의 키가 필요하다. 이는 보통 이산대수의 어려움을 통하여 구현된다. 이번 글에서 다룰 RSA는 소인수분해의 난해함을 기초로 보안이 유지된다. 두 소수 $p$와 $q$가 있다. 이 두 수를 곱하여 $pq$를 계산 하는 일은 누구나 쉽게 할 수 있으며 컴퓨..

삼각형의 넓이를 구하는 8가지 방법

삼각형은 평면 기하에서 매우 기본적인 도형이다. 그만큼 많은 정리들이 있기도 하다. 이 글에서는 이 삼각형의 넓이를 구하는 여러 방법과, 그 증명에 대해 알아본다. 1. 밑변과 높이를 알 때 $S=\frac{1}{2}ah$ 가장 일반적인 삼각형의 넓이 구하는 방법이다. 증명은 생략한다. 2. 두 변과 끼인 각을 알 때 $S=\frac{1}{2}ab \sin\theta$ 이때 높이는 $b\sin\theta$이기 때문에 삼각형의 넓이는 (1)의 방법에 따라 $\frac{1}{2}ab\sin\theta$이다. 3. 정삼각형의 한 변의 길이를 알 때 $S=\frac{\sqrt{3}}{4}a^2$ $\triangle ACH$가 $\angle AHC=90^{\circ}$, $\angle ACH=60^{\circ}$..