검색결과 리스트
Natural Science/Mathmatics에 해당되는 글 2건
- 2014.12.20 소수는 무엇인가? 제 2부 소수의 종류에는 무엇이 있을까? 2
- 2014.12.19 소수는 무엇인가? 제 1부 소수의 중요한 성질과 생활에의 적용 1
글
소수는 무엇인가? 제 2부 소수의 종류에는 무엇이 있을까?
소수란 무엇인가?
제 2부. 소수의 종류에는 무엇이 있을까?
✔ 시작하기에 앞서서...
제 1부에서 소개한 소수(Prime Number)의 수학적 정의는 1과 자기 자신 이외의 다른 양의 정수로 나누어지지 않는 1보다 큰 정수라고 하였습니다. 이번 칼럼에서는 이 정의를 확장하여 더욱 이색적이고 특별한 소수의 종류에 대해서 소개하겠습니다. 소수의 종류에는 에라토스테네스의 체(Sieve of Eratosthenes), 페르마 소수(Fermat Prime), 메르센 소수(Mersenne Prime), 쌍둥이 소수(Twin Prime), 다계승 소수(Multifactorial Prime), 제르맹 소수(Germain Prime), Primorial Prime 등 많은 종류의 소수가 있습니다. 따라서 지금부터 소수의 종류에 대해 하나씩 알아보도록 하겠습니다.
※ 소수를 찾아내는 방법의 종류라고 생각해주시면 됩니다.
✔ 에라토스테네스의 체 (Sieve of Eratosthenes)
중학교 1학년 수학 시간에 소수에 대해 처음 배우면서 슬쩍 구경하고 지나치는 정도로 접한 그 방법입니다. 하지만 인류는 오랜 옛날부터 소수에 대해 관심이 많았기에 찾아내는 방법 또한 옛날부터 알게되어 지금까지 전해져 왔습니다. 그 중에서 잘 알려진 방법이 "에라토스테네스의 쳬" 라고 말할 수 있습니다. "에라토스테네스의 체" 는 그리스 출신의 에라토스테네스가 고안한 방법으로 그는 그리스의 지리학자이며, 시인이며, 천문학자며, 수학자였습니다. "에라토스테네스" 라는 분은 아마 중학교 과학시간에 배울 때 지구의 둘레를 상당히 정확한 정도로 처음 잰 사람으로 유명하다고 배웠을 것입니다. (제가 배울땐 3학년 1학기에 있었는데 있던걸로 기억합니다.) 그 외에도 자전축이 기울어진 정도 역시 상당히 정확하게 측정했었고, 위도, 경도의 개념을 만들기도 하였습니다.
에라토스테네스가 수학에 남긴 족적으로 "에라토스테네스의 체" 라고 부르는 소수 생성법이 있습니다. 이름에서 알 수 있듯이 자연수를 "체"로 쳐서 "소수"만 골라내는 방법으로 간단히 아래에 박스에서 알아보겠습니다.
1. 먼저 1은 소수의 정의에 부합하지 않으므로 제외합니다. 이것은 숫자 "1"에 대해 한 번 체를 친 셈입니다. 남은 숫자는 2 이상의 자연수가 됩니다. 이 중 가장 작은 수 2는 소수입니다. 이제 소수 한개를 찾아냈습니다.
2. 방금 찾아낸 소수 2의 배수는 모두 체를 쳐서 걸러봅니다. 즉, 짝수를 모두 걸러내 버리고, 홀수 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, … 만 남긴다는 뜻입니다. 그러고 나면 남은 수 중 가장 작은 수 3은 소수가 됩니다. 이제 두 번째 소수 3을 찾아냈습니다.
3. 방금 찾은 소수 3의 배수 역시 모두 걸러봅니다. 즉, 3, 6, 9, 12, 15, … 등등을 모두 걸러서 버린다는 뜻입니다. 그러면 남는 수는 5, 7, 11, 13, 17, 19, 23, 25, 29, … 이 남게 됩니다. 이 중 가장 작은 수 5도 소수가 됩니다. 이제 세 번째 소수 5를 찾아냈습니다.
4. 방금 찾은 소수 5의 배수도 역시 모두 걸러봅니다. 이제 남은 수는 7, 11, 13, 17, 19, 23, 29, … 이 남게 됩니다. 이제 네 번째 소수 7을 찾아냈습니다.
5. 방금 찾은 소수 7의 배수도 역시 모두 걸러봅니다. 이제 남은 수는 11, 13, 17, 19, 23, 29, 31, … 이 남게 됩니다. 이제 다섯 번째 소수 11을 찾아냈습니다.
6. 위와 같은 조작을 계속하여 반복하면 차례대로 소수를 찾아낼 수 있습니다.
특정 숫자 이하의 모든 소수를 찾는 방법 중 이보다 더 단순한 방법은 없을 것 같아 보입니다. 단순한 방법이지만 의외로 효율이 좋아서, 발견된 지 2000년이 훌쩍 넘은 현재까지도 작은 규모의 소수를 찾는데 제법 애용되는 방법이며, 컴퓨터 프로그래밍의 예제로 단골처럼 등장하고 있습니다.
✔ 페르마 소수 (Fermat Prime)
먼저 페르마는 왼쪽 형태의 모든 수는 소수일 것이라고 짐작했습니다. 그래서 우리는 이것을 페르마 수라고 부르고 왼쪽의 수가 소수일 때, 그것을 페르마 소수라고 부릅니다. 현재까지 밝혀진 페르마소수는 처음의 5개의 페르마 수 (3,5,17,357,65537) 입니다. 이로 볼 때 단지 유한개의 페르마 소수가 있는 것처럼 보입니다. 1732년에 오일러는 641이 65537을 나눈다는 것을 발견했습니다. 이것은 오일러가 2보다 큰 n을 가지는 Fn 의 모든 약수는 
따라서 이런 원리 때문에 페르마 수들은 상대적으로 분산되어 있는데, 마치 규칙적인 것처럼 보일 수도 있습니다.
페르마 수의 인수분해 방법은 
예를 들어, 
✔ 메르센 소수 (Mersenne Prime)
소수가 무한히 많다는 것이 증명되었지만 소수가 어떤 특별한 형태를 갖는지는 아직 발견되지 않았습니다. 따라서 큰 소수를 구하기 위해 특별한 경우를 살펴보아야 합니다. 수학에는 특별한 이름이 붙은 수가 많이 있습니다. 그 중에는 2의 거듭제곱에서 1만큼 모자라는 메르센 수라는 것이 있습니다. 즉, 지수 n에 대한 메르센 수를 2의 n거듭제곱에서 1만큼 부족한 수를 나타냅니다.
메르센 수는 프랑스 수학자 메르센(Marin Mersenne, 1588~1648) 의 이름을 딴 것입니다. 메르센 수에서 3, 7, 31 등과 같이 특히 소수인 것을 메르센 소수라고 하는데, 메르센 수가 메르센 소수가 되기 위해서는 2의 지수인 n이 소수라는 사실이 밝혀졌습니다. 메르센 소수는 몇 년에 하나씩 발견되다가 최근에는 거의 매년 하나씩 새로 발견되고 있습니다.
2003년 10월에 발견된 40번째 메르센 소수 M(20996011) 는 2GHz 의 펜티엄 4 컴퓨터를 19일동안 가동하여 찾았습니다. 2004년 6월에 발견된 41번째 메르센 소수 M(24036583) 는 무려 723만 5733 자리의 수로 손으로 쓰는데 6주가 걸리며, 수를 쓴 길이는 25km 에 달한다고 합니다. 2005년 2월에 발견된 42번째 메르센 소수 M(25964951) 는 2.4GHz 의 펜티엄 4 컴퓨터를 50일 동안 가동하여 찾았습니다. 2005년 12월에 쿠퍼 교수팀에 의해 발견된 43번째 메르센 소수 M(30402457) 는 915만 2052 자리의 수입니다. 그리고 쿠퍼 교수는 1년도 채 지나지 않은 2006년 9월에 44번째 메르센 소수 M(32582657) 을 또 찾았습니다.
사실 1000만 자리가 넘는 메르센 소수를 찾는 사람에게는 10만 달러의 상금이 걸려 있었지만, 아쉽게도 44번째 메르센 소수도 1000만 자리는 넘지 못했습니다. 12457 로 시작하여 967871 로 끝나는 이 소수는 손으로 쓰는데 꼬박 9주가 걸리고 수의 길이는 34km 정도나 된다고 합니다.
최근에 찾아진 메르센 소수는 2008년 8월 23일 미국의 한 대학 연구원인 한스와 마이클에 의해서 발견되었습니다. 그들이 찾은 소수는 약 1300만 자리의 수인 M(43112609) 로 이 수는 손으로 쓰려면 약 12주가 걸리고 그 길이만 해도 약 44km 정도가 된다고 하니 정말 어마어마하게 큰 소수입니다. 어쨌든 그들은 이 소수가 45번째 메르센 소수라고 생각했지만 같은 해 9월 6일에 미국 캘리포니아 버클리 대학의 연구팀에 의하여 45번째 메르센 소수 M(37156667) 이 발견되어 한스와 마이클이 발견한 소수는 46번째 메르센 소수로 기록되었습니다. 45번째 메르센 소수도 1000만 자리가 넘었지만 불과 며칠 사이로 10만 달러의 상금을 못 타게 되었으니 안타까운 일입니다. 그런데 중요한 것은 39번째 메르센 소수인 M(13466917) 과 46번째 메르센 소수인 M(43112609) 사이에 다른 메르센 소수가 더 있을지도 아직까지 확실하게 알려져 있지 않습니다. 그래서 만일 그 사이에 다른 메르센 소수가 발견된다면 번호가 바뀔 수 있습니다.
'Natural Science > Mathmatics' 카테고리의 다른 글
| 소수는 무엇인가? 제 1부 소수의 중요한 성질과 생활에의 적용 (1) | 2014.12.19 |
|---|
설정
트랙백
댓글
글
소수는 무엇인가? 제 1부 소수의 중요한 성질과 생활에의 적용
소수란 무엇인가?
제 1부. 소수의 중요한 성질과 생활에서의 적용
✔ 시작하기에 앞서서...
곧 2015년이 되겠지만 일단 올해는 2014년의 해입니다. 지금부터 말하고자 하는 소수는 1과 자기 자신 이외의 다른 양의 정수로 나누어지지 않는 1보다 큰 정수, 더 이상 분해 할 수 없는 수를 말합니다. 정의에 따르면 2014는 소수가 아니기에 올해는 소수의 해라고 말할 수 없게 됩니다. 다만 3년 전인 2011년은 소수의 해라고 말할 수 있게 되겠지요.
필자는 수학이야기 <소수는 무엇인가?> 를 3번 연재할 계획입니다. 제 1부에서는 “소수의 중요한 성질과 생활에의 적용”, 제 2부에서는 “소수의 종류는 얼마나 있는가?”, 제 3부에서는 “소수에 관련된 수학자와 리만 가설의 소개”를 끝으로 마무리를 할 계획입니다 1부는 대부분의 사람들이 쉽거나 자명한 내용들이 많아 흥미롭게 읽을 수 있으나 제 2부와 제 3부에서는 다소 생소하거나 정의 자체가 어렵게 소개되는 내용들이 많을 수도 있습니다. 그래도 인내와 흥미를 가지고 읽어본다면 비록 적은 내용일지라도 조그만 수학적 전문지식을 습듭했다는 자신감을 가질 수 있을 것입니다.
(개인적인 생각이므로 조금이나마 도움이 되었으면 하는 바램으로 시작해볼게요 ^^ )
소수라는 수학적 용어에 많은 사람들은 수학조차 흥미를 가지는 사람이 많지 않기 때문에 그런 사람들이 흥미를 가지게 하기 위해서 주변에서 자주 볼 수 있지만 잘 알지 못했던 사실을 소개하면서 시작하겠습니다. 제가 가장 좋아하는 계절은 이 글을 쓰는 시점인 겨울이지만 내년 피서를 기대하면서 여름으로 이야기를 옮겨봅시다. 여름 하면 떠오르는 곤충은 매미입니다. 매미는 한 여름에만 맴~맴~하고 우니까 짧게 사는 같이 보이지만 그렇지 않습니다. 매미는 상당히 오래 사는 곤충입니다. 매미는 식물의 조직 속에 알을 낳는데, 우리나라에서 서식하고 있는 유지매미와 참매미는 산란한 후 7년이 지나야 성충이 되고, 늦털매미는 5년이 되어야 성충이 된다고 합니다. 매미탑이라는 북아메리카에 사는 매미는 산란한 후 13년이 지나야 성충이 되는 것과 17년이 지나야 성충이 되는 것, 두 종이 있습니다. 이처럼 대부분의 매미는 산란에서 성충이 되기까지 삶의 주기가 보통 5년, 7년, 13년, 17년인데, 이것은 흥미롭게도 삶의 주기가 모두 소수가 된다는 흥미로운 사실을 알 수 있습니다. 따라서 필자는 왜 매미의 삶의 주기가 소수가 되는 이유에 대해 파헤쳐보고 소수에 대해서도 자세히 파헤쳐보도록 하겠습니다.
✔ 매미의 수명은 왜 소수일까?
그 이유를 설명하는 데에는 두 가지 학설이 있습니다. 첫 번째, 소수를 생의 주기로 삼으면 천적을 피하기 쉽다는 것입니다. 예를 들어 매미의 삶의 주기가 6년이고 천적의 삶의 주기가 2년 또는 3년이라면 매미와 천적은 6년마다 만나게 됩니다. 또한 삶의 주기가 4년인 천적과는 12년마다 만나게 됩니다. 그렇지만 매미의 삶의 주기가 7년이라면, 삶의 주기가 2년인 천적과는 매 14년마다 만나게 되고, 삶의 주기가 3년인 천적과는 21년마다 만나게 되며, 4년인 천적과는 28년마다 만나게 됩니다. 이렇게 되면 매미는 종족번식을 위한 보다 많은 시간과 기회를 얻게 되는 것입니다.
또 다른 학설은 동종간의 경쟁을 피하기 위해 스스로 삶의 주기를 조정한다는 것입니다. 모든 매미들의 삶의 주기가 같아서 겹치게 되면 그만큼 먹이를 둘러싼 생존경쟁이 치열해질 것입니다. 따라서 많은 종의 매미가 많은 자손을 퍼뜨리려면 동시에 출현하지 않는 것이 서로에게 유리하게 됩니다. 결국 주기를 소수로 하면 그 만큼 서로 만나서 경쟁하는 횟수가 줄어들게 됩니다. 예를 들어, 5년 주기인 매미와 7년 주기인 매미는 35년마다 만나게 되고, 13년 주기인 매미와 17년 주기인 매미는 221년마다 만나게 되므로 서로에게 그만큼 종족번식의 기회가 많아지게 됩니다. 이와 같이 매미는 천적으로부터 종족을 보존하기 위하여 또는 먹이를 둘러싼 동종간의 경쟁을 피하기 위하여 소수를 삶의 주기로 진화해왔다고 합니다.
✔ 소수, 쪼갤래야 더 이상 쪼갤 수 없는 아주 단단한 수
어떤 물질을 이루는 기본 단위인 ‘원자(atom)’는 ‘더 이상 나누거나 분해할 수 없는 물질’이라는 뜻입니다. (현재에는 원자보다 더 작은 입자가 있다는 사실이 알려져 있습니다). 물질에서 원자와 같은 개념을 수학에 적용한 것이 소수입니다. 즉, 어떤 수를 분해할 때 ‘더 이상 분해할 수 없는 수’를 소수라고 생각하면 됩니다. 소수(prime number)의 수학적 정의는 1과 자기 자신 이외의 다른 양의 정수로 나누어지지 않는 1보다 큰 정수(p)입니다. 한편 1보다 큰 정수 a가 소수가 아닐 때, a를 합성수(composite number)라고 합니다. 이와 같이 소수가 모든 정수의 기본이 되는 수라는 것을 설명해 주는 것이 ‘정수론의 기본정리’입니다.
*** 정수론의 기본정리 ***
위와 같이 1보다 큰 양의 정수 n을 유한개의 소수의 곱으로 쓸 수 있는데, p1, p2, 이것은 마치 어떤 화합물을 적당한 용도로 사용하기 위해 그 물질에 어떤 원자가 얼마만큼의 비율로 들어 있고, 그들의 결합 상태가 어떻게 되어 있는지를 알아내는 것과 같습니다.
✔ 소수는 무수히 많다 !
✔ 소수를 판별하는 방법은 무엇인가?
가장 먼저 판별하려는 자연수에 루트를 씌운 후에 그 수의 정수 값을 알아냅니다. 결국 그 정수 값을 찾게 되면 그 수보다 같거나 작은 소수로 원래의 수를 나누어 봅니다. 만약 하나의 수라도 나누어 떨어지면 그 수는 소수가 아닌 합성수가 되고, 끝까지 나누어 떨어지는 수가 없다면 소수가 됨을 알 수 있습니다.
✔ 소수가 암호에도 사용된다?
소수는 특히 첨단 정보화 사회가 된 오늘날에는 정보를 보호하는 암호에 사용되고 있다. 최근에 사용되는 암호는 대부분 소수를 이용한 공개 열쇠 암호 방식으로 만들어져 있다. 공개 열쇠 암호 방식은 암호를 만드는 방식은 공개되지만 그 암호를 원래의 문장으로 돌려놓는 열쇠를 알아내기가 거의 불가능한 방식이다. 이런 방식이 가능한 이유는 큰 정수를 소인수 분해 하는 것이 매우 어렵기 때문이다. 예를 들어 어떤 두 소수를 곱한 수 4067351을 이용하여 암호를 만들었다는 것을 공개한다. 그런데 암호를 원래의 문장으로 돌려놓기 위해서는 이 수가 어떤 두 소수의 곱으로 되어 있는지 알아야 한다. 사실 이 수는 두 소수 1733과 2347의 곱이다. 그런데 두 소수 1733과 2347을 주고 이들의 곱 4067351을 계산하는 문제는 아주 쉽지만, 거꾸로 4067351이 어떤 두 소수의 곱으로 되어 있는지를 찾는 소인수분해 문제는 매우 어렵다. 실제로 사용되는 공개 열쇠 암호 방식은 예를 든 방법보다 훨씬 복잡하고 정교하지만, 소인수분해가 어렵다는 암호의 근본 원리는 같다.
1977년에 공개열쇠 암호 방식이 처음 발표될 당시, 예로 들었던 두 소수를 곱한 수를 인수분해 하는데 약 4경 년이 걸릴 것으로 예상했습니다. 그러다가 1994년에 인수분해 알고리즘이 개발되며 인수분해를 좀 더 빨리 할 수 있게 되었는데, 다행스럽게도 인수분해를 알고리즘을 이용해도 100년 이상 걸립니다. 그래서 공개열쇠 암호방식은 오늘날 은행의 저금통장의 비밀번호에서부터 인터넷에서 사용되는 ID와 암호 등 다양하게 이용되고 있습니다. 그러나 인수분해 알고리즘이 계속해서 발전하고 있기 때문에 그에 대응하여 더 큰 소수가 필요하게 되었습니다. 그래서 소수를 연구하는 수학자들은 더 큰 소수를 찾기 위해서 지금도 노력하고 있습니다.
'Natural Science > Mathmatics' 카테고리의 다른 글
| 소수는 무엇인가? 제 2부 소수의 종류에는 무엇이 있을까? (2) | 2014.12.20 |
|---|
