|
|
 |
|
광고, 욕설, 비속어, 아이디 도용, 인신공격 등 게시판에 적합치 않은 ID나 글은 사전통보없이 삭제됩니다.
또한 투고시 명예훼손, 무고 등으로 민ㆍ형사상 처벌을 받을 수도 있음을 유념해주십시오.
:: 삭제원칙 자세히 보기
|
|
|
| 작성자 : 이정구 작성자ID : jk0620 조회 : 30 추천 : 0 |
작성일 : 2003-12-09
|
|
메르센 소수의 모순과 마방진 소수의 비젼
메르센 공식에는 이미 모순이 발견되었다. 일부에서 오류가 발견된 것에 구애 받지 않고 진행하는 이유가 있다. 확률적으로 거대 소수를 찾을 가능성에 무게를 둔 것이다. 적어도 거대 소수찾기에 확률적 희망을 준 탓이다.
--------------------------------------
http://petit.new21.org/math/math16.htm
n이 소수일 때 2n-1은 소수일 것이라는 생각은 예전부터 있었다. 그러나 1500년 이후 n이 11, 23, 29,..37일 때는 소수가 아니라는 연구 결과가 나왔다. 1644년에 프랑스 수도사였던 메르센(Mersenne, 1588-1648)은 "n이 257보다 크지 않을 경우 n=2,3,5,7,13,17,19, 31,67,127,257(전부 소수) 일 때만 2n-1은 소수이다"라는 발표를 하였다. 그러나 이 가정은 틀린 것으로 판명되었지만 아직도 메르센의 이름은 다음과 같은 정리로 수학사에 남아있다.
"2n-1이 소수일 때 이를 메르센 소수라 한다"
메르센의 주장은 1947년에 와서야 모든 소수에 대하여 검증이 끝났는데 n=2, 3, 5, 7, 13, 17, 19, 31, 61, 69, 107, 127만이 메르센 수식을 만족한다. 메르센 소수는 계속 발표되었고 38번째 메르센 소수인 2의 6972593제곱 마이너스1이 발표 되었다. 이는 1999년에 찾은 것으로 2,098,960자리 소수이다. 1963년에 23번째의 메르센 소수가 일리노이대학에서 발견되었을 때 그 대학의 수학과는 이러한 발견이 매우 자랑스러운 나머지 편지 봉투에 "211213-1은 소수이다"라는 스탬프를 찍어 발송하였다.
1과 자신 이외의 약수를 갖지 않고 2의 거듭제곱 마이너스 1의 형태를 갖는 메르센 소수는 암호를 개발하는데 중요하게 쓰인다. 소수연구팀의 창립자인 조지 월트먼은 “2년 동안의 쉼없는 작업을 통해 얻은 이 소수의 발견은 우리의 가장 인상적인 업적”이라고 말했다. 김프스는 96년 메르센 소수 발견을 목적으로 창립됐으며 소수발견을 위한 프로그램을 무료로 나눠주고 있다.
Copyright ⓒ 2001~ ( Petit - Kim kee tae ). All rights reserved.
------------------------------------------------
http://www.donga.com/fbin/output?f=todaynews&code=k__&n=200312050004&main=1
http://www.mersenne.org/history.htm
<과학> 600만자리 사상 최대 소수 발견
미국의 한 대학원생이 600만자리가 넘는 사상 최대의 소수(素數)를 발견했다.
미시간주립대 화학공학과 대학원생인 마이클 셰이퍼가 발견한 이 소수는 ‘887595…’로 시작하는 632만430자리의 숫자. 보통 사람이 노트에 쓴다면 꼬박 5주가 걸릴 정도로 큰 숫자라고 BBC 방송이 4일 전했다.
컴퓨터 한 대가 이 정도 크기의 소수를 찾으려면 2만5000년 정도가 걸릴 것으로 추산된다. 하지만 셰이퍼씨는 수십만 대의 개인용 컴퓨터를 인터넷으로 병렬 연결해 만들어낸 이른바 ‘가상 슈퍼컴퓨터’를 이용해 2년 만에 찾아냈다. 이 슈퍼컴퓨터는 초당 9조번의 연산 속도를 자랑한다.
이번 발견은 개인 PC 소지자가 자발적으로 참여해 초대형 소수를 찾는 결실이기도 하다. 셰이퍼씨도 이 프로젝트에 참여한 6만명의 자원봉사자 중 한 사람이다. 1996년 처음 시작된 이 프로젝트를 통해 2000년에 100만자리 크기의 소수가 처음 발견됐다.
셰이퍼씨가 발견한 소수는 현대 수학의 가장 중요한 발견 가운데 하나인 ‘메르센 소수(Mer-senne Prime)’. 메르센 소수는 소수 가운데에서도 의 형태를 가지는 소수. 지금까지 메르센 소수는 3, 7, 31, 127을 포함해 40개밖에 발견되지 않았다.
김프스는 1000만자리 크기의 더욱 큰 새로운 소수를 발견하기 위한 작업을 이미 시작했다. 1000만자리 소수를 발견하는 사람에게는 10만달러의 상금이 주어진다.
김성규기자 kimsk@donga.com
========================================
거대 소수찾기 김프스는 96년 메르센 소수 발견을 목적으로 창립 되었다고 한다. 전세계적으로 이 프로젝트에 참여하는 사람이 수십만명은 된다고 한다.
2^11-1=2048-1=2047=23*89 이다. 즉 [2^ 소수-1=소수]이라는 메르센 소수는 합성수를 포함한 가설일 뿐이다. 그래도 거대 소수를 발견해줄 탐사법이였다. 마치 순금을 얻기위해 금이 포함된 광석을 얻은 것과 같다. 어떤 경우는 매우 희박하다.
메르센 공식에서 일부에서 모순이 발견된 것에 구애 받지 않고 진행하는 이유가 있다. 확률적으로 거대 소수를 찾을 가능성에 무게를 둔 것이다.
마찬가지로 마방진 소수는 마방진 소수판별2식.에 의하여 얻어질 수 있는 거대 소수를 예상한 것이다. 거대 임의 홀수가 소수인지 아닌지는 소인수분해가 불가능한 지경에 나올 수 있는 예상치이다. 마방진 소수 판별2식.은 필요조건n.에서 임의 홀수가 합성수일 가능성을 확인하는 작업이 포함된 까닭이다.
이에 반하여 메르센 소수는 극히 제한적이지만 마방진 소수는 거의 소인수분해능의 최대치에 비례하는 까닭에 세계 최첨단 슈퍼컴이 소인수분해을 할 수 있는 수준까지 끌어 올려서 거대소수를 추적할 수 있다는 가정이다.
최근에 발견한 거대 소수는 미국의 한 대학원생이 600만자리가 넘는 사상 최대의 소수(素數)이라 한다. 1000만 자리를 발견하는 사람에게는 10만달러의 상금이 걸려 있다고 한다. 여기서 얘기하는 1000만 자리는 1 뒤에 동그라미가 천만개 붙은 숫자 소수이다.
왜 이렇게 긴 자리수가 필요한지는 암호의 문자열에 숫자열의 도입의 필요성을 상상해보면 알 수 있다. 인터넷 문명사회에서 개인의 정보보안은 거의 암호화 되어야 한다는 것은 상식이다. 인터넷에서 모든 정보와 금융거래가 실시간화 되는 세상에서의 필요에 의한 요구이다.
그러면 그 1000만 자리를 어떻게 구현 되는가? 간단히 메르센 소수의 공식을 보면 감을 잡을 수 있다. [2^소수-1]에서 그 소수가 크면 클수록 결과 소수의 크기도 비례한다. 예를들어 2^3=8 이고 8*8=64, 2^6=64, 곧 10의 자리수이다. 그러하면 2^n=자리수???는 3n 에 따라 동그라미가 하나씩 붙는다. 3n=6 일때 0=1, 3n=9 일때 0=2 가 붙고 3n=9 일때는 동그라미 0=3 붙는 식이다. 여기에서 n=2일 때 동그라미 0=1, n=3 일때는 0=2...즉, n=100 이면 동그라미는 n-1 이다. 반대로 1 뒤에 동그라미 100 개 있으려면 n=99 이다. 즉, 3n=3*99=297. 2^279-1= 100자리수 홀수이다. 1 뒤에 동그라미가 100개가 있는 숫자이다.
만약에 어느 임의 홀수를 1 뒤에 동그라미가 1000만개 붙는 소수로 판명하려면 메르센 공식 [2^n-1]에서 n을 999만9999 로정하고 3배하면 2천999만9997. 2^299999997-1 이다. 문제는 29999997 이 소수인지 아닌지만 판단하면 되는 것이다. 만약에 2의 지수 29999997 이상의 숫자에서 소수판명만 나온다면 그 결과수는 메르센 거대소수임이 틀림이 없다. 그러면 10만 달러는 손에 쥐여진다.
-----------------------------------------------
여기서 마방진의 소수판별법이 드디어 등장해야 하는 것이다.
바로 소수판별2식.[임의 홀수=m+1,+2,+3...n-1 /n] 이다.
임의 홀수= 2999997은 소수인가 아닌가?
testing go.
29999997
29999998 /3 testing... no 나머지 생김.
29999999 /3 ...no,no,end
다른 숫자 도입해 보자.
임의 홀수=29999999.
29999999
-------------
30000000 /3...ok
30000001 /3...no
-------------------------
30000002 /4...ok.
여기서 ok-data는 30000000 /4 에서 나온 것이다. 물론 30000001 /4=no, 30000002 /4...no. 이였다. /4 는 맨앞에 숫자부터 /4 바로 앞까지 계산하여 (나머지가 없는 mod=0)를 필요조건4. 구간에서 찾는 것이다.
--------------
30000003 /5...ok
필요조건4. 구간과 마찬가지로 필요조건5. 구간은 맨앞에 숫자을 /5로 나뉘어 [30000000 /5= ...ok(mod=0)] 을 얻었다. 나머지 [20000001,20000002,20000003 /5=...no] 이였다.
---------------
30000004 /6
---------------
30000005 /7
---------------
등등 계속적으로 계산해 보아 하나의 구간(필요조건n. 구간)에서 나머지가 없는 mod=0 상태를 찾는 것이다. 물론 소인수분해을 통해 합성수로 판명되어도 ok는 존재한다. 그것은 단위 마방진이 성립하는 것일뿐 그 소인수에서는 반드시 ...no를 만나게 돼 있다. 만약에 임의 홀수=29999999.이 소인수분해 되어진다면 역시 합성수일테이지만 소인수분해가 불가능한 계산일 수 있는게 수학의 현실이다. 그래서 슈퍼컴이 그 보조역할을 할 수 있으리라 믿는 것이고 거대소수의 발견의 한계는 소인수분해의 한계에 시작된다고 보는 것이다. 다행히 어떤 자료에 의하면 1억까지의 소수를 정리한 사람이 있다고 들었다. 그 사람의 자료집에는 29999999 가 소수인지 아닌지는 금새 판단 되리라. 그런데 그 사람의 자료를 우리가 볼 수 없는 것이 탈이고 2^11-1=2048-1=2047=23*89 과 같이 2^소수(11)-1=메르센 소수 이여야 하는데 no,no, 소수가 아닌겨. 29999999이 분명한 소수이여도 2^29999999-1은 소수가 이닐 수 있다는 것이다. 이 얼마나 황당한 일인가는 메르센 소수 공식의 모순을 붙들고 탓할 순 없다. 우리는 첨부터 메르센 소수가 메르센 공식으로 부터 확률적인 성공을 기대한 것이지 확실한 소수를 공식에서 제공되리라 믿지 않았다. 결과는 1000만 자리 소수를 직접 검증하는 것이외는 달리 없다. 그일이 가능한가? 가능하기에 상금도 내걸었으니 믿어는 본다. 하지만 수십만 인터넷 pc가 연결된 분산 컴퓨팅의 낭비라고 생각들지가 않는가 말이다. 고로 메르센 소수 찾기는 그 공식의 모순을 안고도 낭비적인 이론임이 틀림이 없다. 인간은 그런 식으로 거대 소수를 찾는 것이 아니다. 경제적이고도 간단명료하고도 확실한 방법을 택한다.
바로 마방진 소수이다. 임의의 홀수=1억 자리수의 숫자열을 만들고 그것에 대해 소인수분해를 할 수 있는지 슈퍼컴에 의뢰하고 직접적으로 소수판별2식.[임의 홀수=m+1,+2,+3...n-1 /n]로 들어가는 것이다. 필요조건이 너무 많으면 샘플링를 작성하면 된다. 듬성듬성 난수표 사용하듯 확률적으로 진부를 가릴 수 있는 확률빈도가 높은 구역을 최대한 늘리는 것이다.
필요조건n.의 샘플링은 다음과 같다.
임의 홀수=m 이 있을 때,
필요조건 n.의 구간의 지표는 다음과 같은 수의 피젯수군이 형성된다.
17
18 /
19/3
20/4
21/5 필요조건5. 구간지표
.
.
.
47
48/
49/3
50/4
51/5
.
.
.
m+n-1 /n 필요조건n. 구간지표 이다. 바로 이것이 샘플링 필요조건n.의 검산 공식이다.
여기서 젯수 n은 피젯수 범위=p(m+1<p<m+n-1) 에서 mod=0 를 찾으면 된다.
거대 임의 홀수를 가지고 소수판별2식. 대로 한번 테스팅 해보자.
임의 홀수=m=29999999.
샘플링 테스트 start.
m+n-1 /n
29999999+256-1 /256= ;검산 범위는 29999999+1<p<29999999+256-1; 필요조건 256.DATA
|
|
|
|
|
|
|
