|
|
 |
|
광고, 욕설, 비속어, 아이디 도용, 인신공격 등 게시판에 적합치 않은 ID나 글은 사전통보없이 삭제됩니다.
또한 투고시 명예훼손, 무고 등으로 민ㆍ형사상 처벌을 받을 수도 있음을 유념해주십시오.
:: 삭제원칙 자세히 보기
|
|
|
| 작성자 : 이정구 작성자ID : jk0620 조회 : 31 추천 : 0 |
작성일 : 2003-12-10
|
|
소수의 발견보다도 더 골치가 아픈 것이 있다. 굉장히 큰 합성수가 소수가 아니라는 즉 소인수분해의 문제도 여간 어려운 일이 아니다. 소인수분해를 통하지 않고 소인수 (prime factor)를 찾아내는 간단한 방법이 있다. 바로 본인(jk0620)이 제시하는 마방진 소수판별2식. 이다. 가칭' jk0620 소수판별2식.' 이다.
-----------------------------------------
http://www.mathtaegu.com/history/history2-4.htm
비의도적 전송(oblivious transfer)이라는 것이 있다. 이것은 하버드 대학의 라빈(Michael Rabin)이 고안 한 것이다. 두 개의 서로 다른 열쇠가 있어야 열리는 상자가 있는 데 잠긴 상자를 보낸다. 받는 사람은 둘 중의 어느 하나의 열쇠를 가지고 있으며 보내는 사람은 받는 사람이 어떤 열쇠를 가지고 있는 지 모르는 상태에서 두 열쇠 중 하나의 열쇠를 보내는 것이다.
여기서 두 열쇠는 어마어마하게 큰 합성수이고 열쇠의 각각은 크기-자리수-가 비슷한 두 소인수들이라고 하면 합성수를 인수분해하는 일이 중요하고 비밀스러운 그러면서 생명만큼이나 가치로운 상자를 열 수 있을 것이다.
2^193-1 와 같은 수이면 인수분해하기가 쉽겠는가? 산술적인 계산을 성능 좋은 컴퓨터(매초 10억 회의 나눗셈을 수행하는)로도 두 번째 큰 소인수를 찾기 위해서는 약 35,000년 이상이 걸린다. 어쩌지. 실제로 2^193-1 를 소인수분해한 결과는 다음과 같다.
2^193-1=13,821,503*61,654,440,233,480,340,616,559*14,732,265,321,317,331,353,282,383
자 그럼 컴퓨터 하기 어려운 이런 소수를 어떻게 찾아낼 수 있을까.
처음 소수에 대한 연구는 전통적으로 이론 그 자체와 그 결과의 아름다움에 빠져 순수한 부분으로 여겨졌다. 그러다가 현재에는 현대 암호 체계의 안정성문제에 소수의 문제가 대두된다. '얼마나 쉽게 소수를 판별하는가, 큰 수의 인수분해를 쉽게 할 수 있겠는가'로 소수의 활용 범위가 넓어졌다.
유클리드에 의해 소수가 무한하다는 것이 증명되고 난 뒤 많은 수학자들은 소수의 연구에 골몰하게되고 그 결과로 지금의 활용에까지 이르렀다. 유클리드의 증명법에서 사용된 어떤 특정한 값까지의 소수들을 곱해서 1을 더하면 항상 소수가 될 것인가. 2+1=3, 2×3+1=7, 2×3×5+1=31, 2×3×5×7+1=211, 2×3×5×7×11+1=2311로 가능할 것 같이 보이지만 2×3×5×7×11×13+1=30031=59×509가 된다. 또 3과 5, 41과 43같이 쌍둥이소수(twin primes)가 무한히 많이 존재할까? 쉽게 소수를 발견할 수 있는 방법에 대한 연구도 지속적으로 이어졌다. 가장 쉽게 아는 방법이 에라토스테네스의 체이다. 처음 몇 개의 소수를 찾고 그의 배수를 차례로 지워나가는 방법인데 지루하고 시간이 많이 걸리는 과정이다. 이 방법은 약간씩 변형한 방법들이 생겨나기도 했다. 그 외 다른 수학자들은 얼마의 빈도로 나타나는지 어떤 패턴은 없는 지의 연구도 있었는데 3, 37, 337, 3337, 33337, 333337은 모두 소수이지만, 3333337은 7과 31과 15361로 소인수분해된다.
오일러에 의해서 x^2+x+17 도 x=0에서 x=15 까지의 수에 대해서 소수가 됨을 알게 되었고, 또, 골드바흐는 4보다 큰 짝수는 소수인 두 홀수의 합으로 표현 될 수 있다고 추측하였고, 페르마는 "만약 p가 소수이면 임의의 정수b 에 대하여 b^p-b는 의 배수이다"는 정리를 이용해 소수인지 아닌지를 쉽게 테스트하는 법을 고안 해 냈으나 소수가 아닌 경우에도 이런 사실이 성립하는 의사소수(pseudo prime number)가 간간히 들어있어 의사소수를 추려내는 어려움이 있기도 했다. 메르센느에 의해서 메르센느 수(Mersenne number)라는 소수가 생겨났다. 이는 p가 솟수일 때,Mp=2^p-1 이 소수이면 메르센느 소수라고 한다. p=2,3,5,7,13,17,19...인 경우 소수인데 p^11이면 소수가 아니다. M11=2^11-1=2047=23*89로 인수분해된다.
하지만 소수의 발견보다도 굉장히 큰 합성수가 소수가 아니라는 즉 소인수분해의 문제도 여간 어려운 일이 아니다. 지금도 많은 수학자들과 컴퓨터는 보다 나은 알고리즘을 개발 쉽게 소인수분해하는 법을 연구 중에 있다. 이 거대한 합성수의 소인수분해는 암호문 해독에 응용되었다. 기존의 암호문 전달 체계와 다른 암호학에 공공열쇠 개념을 도입하여 리베스트(Ron Rivest)와, 샤미르(Adi shamir), 아들만(Len Adleman)의 이름을 딴 RSA방식이라는 암호이론이 개발되기도 했다.
====================================
A.
소인수분해를 통하지 않고 소인수 (prime factor)를 찾아내는 방법이 있다. 바로 마방진 소수판별2식. 이다. 조건식은 [임의 홀수=m+1,+2,+3,...n-1 ≡b(mod n);not b=0 ]이다.
거대 임의 홀수를 택하여 마방진 소수판별2식.을 적용하더라도 거대 홀수에 대하여 소수인지, 합성수인지 불분명한 상황이 존재 한다.
여기서 소인수분해의 문제도 대단히 중요한 사안이다. 두개의 소수을 조합하여 곱으로 나타낸 합성수 구구단 표와 같은 것이라도 만들어 봐야 할 판이다.
우리의 과제는 1000만자리수 소수의 발견에 최소한의 상금 10만달러 이상를 거머쥐기 위해 거대 소수를 찾는 것이고 그 소수는 자연수 홀수계에 포함돼 있고 합성수들과 뒤석여 있어서 거대 홀수가 합성수인지, 아닌지를 판단하면 곧 소수가 판명 나기도 한다.
그 홀수의 합성수는 소수판별 필요조건n식. [임의 홀수=m+1,+2,+3,...n-1 /n]에 의하여 'not mod=0' 합동식合同式 (congruent expression) a≡b(mod p)으로 표현하면 [임의 홀수=m+1,+2,+3,...n-1 ≡b(mod n)].
여기서 b는 '나머지'를 의미하며 '0' 나와서는 안된다. 참고로 두 정수(整數) a,b의 차가 정수p의 배수일 때a와 b는 p를 '法(법:modulus)'으로 하여 합동이라 한다. 예를 들면 a≡b(mod p),10≡1(mod 3) 에서 a=10에서 b=1를 빼면 p=3의 배수 9 이다.
이제 마방진 소수 판별식을 수학적인 정확한 용어로 제시할 필요가 있다.
임의 홀수가 만약에 소수이면 소수판별 필요충분조건n식.[임의 홀수=m+1,+2,+3,...n-1 ≡0(mod n)] 이고 아니면 [임의 홀수=m+1,+2,+3,...n-1 ≡b(mod n)], b는 0 이 아니다..즉 합성수이다.
예를 들어, 25, 35 등과 같은 합성수는 어느 정도 필요충분조건n식.[임의 홀수=m+1,+2,+3,...n-1 ≡0(mod n)]을 만족하나 바로 소인수 35=5*7, '소인수=5,7' 인 필요조건5식.7식. 구간에서 [임의 홀수=m+1,+2,+3,...n-1 ≡b(mod n);not b=0 ]인 상태로 변한다.
보기1.
35+1 /4=36 /4=...0
35+2 /4=37 /4=...1
35+3 /4=38 /4=...2
고로 [나머지=0, 하나]가 나타나는 것에 만족한다.
마찬가지로 젯수 5 에 대하여서도
보기2.
35+1 /5=36 /5=...1
35+2 /5=37 /5=...2
35+3 /5=38 /5=...3
35+4 /5=39 /5=...4
-----------------
보기3.을 주목해 주기 바란다.
보기3.
필요조건7식. 구간 [임의 홀수=m+7≡b(mod n)],
36≡1(mod 7)
37≡2(mod 7)
38≡3(mod 7)
39≡4(mod 7)
40≡5(mod 7)
참고로 보기3.은 수학적인 일반용어로 소수판별 필요조건7식. 을 표현한 것이다.
여기서 합성수는 거의 모두가 소인수분해를 통해 소인수 구간의 소수판별 필요조건이 언제나 나머지가 있는 상태로 나타난다.
+++++++++++++++++++++++++++++++++++
우리는 이제 거대 임의홀수(1억자리수 이상의 자연수)가 합성수인 것을 판단하는 기준을 찾았다.
바로 [임의 홀수=m+1,+2,+3,...n-1 ≡b(mod n);not b=0 ]인 상태이다.
소수판별 필요조건 한 구간에서 [나머지가 전부 생기는 현상]을 찾아내면 바로 그 수가 임의 거대홀수=m의 소인수(prime factor) 이다. 즉 소인수분해를 통하지 않고 소인수 (prime factor)를 찾아내는 방법을 제시함이다.
이제 임의 홀수에 대해 전통적인 소인수분해 식를 하지 않고 소인수를 찾는 방법을 통하면 거대 소수를 찾는 일이 더한층 간편해질 것이다.
+++++++++++++++++++++++++++++++++++
B.소인수분해를 통하지 않고 소인수 (prime factor)를 찾아내는 간단한 방법
테스팅...
m+n-1 /n 필요조건n. 구간지표 이다. 바로 이것이 샘플링 필요조건n.의 검산 공식이다.
여기서 젯수 n은 피젯수 범위=p(m+1<p<m+n-1) 에서 [임의 홀수=m+1,+2,+3,...n-1 ≡b(mod n);not b=0 ]를 찾으면 된다.
거대 임의 홀수를 가지고 소수판별2식. 대로 한번 테스팅 해보자.
임의 홀수=m=29999999.
샘플링 테스트 start.
m+n-1 /n
29999999+256-1 /256= ;검산 범위는 29999999+1<p<29999999+256-1; 필요조건 256.DATA
-------------------------------------
참고1.
나머지가 안생기면 ok=o로 표시 하자.
나머지가 생기면 no=n으로 표시하자.
[소수판별 필요조건合同式 ; o,n 생성된 위치]
start
m=29999999
30000000
[30000001≡o(mod 3);30000000≡o(mod 3)];
[30000002≡o(mod 4);30000000≡o(mod 4)];
[30000003≡o(mod 5);30000000≡o(mod 5)];
[30000004≡o(mod 6);30000000≡o(mod 6)];
[30000005≡o(mod 7);30000005≡o(mod 7)];
[30000006≡o(mod 8);30000000≡o(mod 8)];
[30000007≡o(mod 9);30000006≡o(mod 9)];
[30000008≡o(mod 10);30000000≡o(mod 10)];
[30000009≡o(mod 11);30000003≡o(mod 11)];
[30000010≡o(mod 12);30000000≡o(mod 12)];
.
.
[m+n-1≡o(mod n);a≡b(mod c)];
[29999999+123-1≡?(mod 123);a≡b(mod c)]
=[30000121≡o(mod 123);30000069≡o(mod 123]
.
.
[30000553≡o(mod 555);30000525≡o(mod 555]
.
.
이런 식으로 계속 나아가,
[임의 홀수=m+1,+2,+3,...n-1 ≡0(mod n)] 이면
m=29999999는 소수이고
어느 정도 나가서 어느 구간에,
[임의 홀수=m+1,+2,+3,...n-1 ≡b(mod n);not b=0 ]이고
다시[m ≡o(mod n)] 로 되돌아 오면
바로 그 구간에 필요조건n.에 n이 바로 m=29999999 의 소인수 (prime factor)가 된다.
#1.소수의 발견보다도 굉장히 큰 합성수가 소수가 아니라는 즉 소인수분해의 문제도 여간 어려운 일이 아니다. 지금도 많은 수학자들과 컴퓨터는 보다 나은 알고리즘을 개발 쉽게 소인수분해하는 법을 연구 중에 있다. 이 거대한 합성수의 소인수분해는 암호문 해독에 응용되었다.
임의 거대홀수가 합성수인 경우는 다수의 소인수의 조합으로된 곱일 수 있기에
또다른 구간에서 [임의 홀수=m+1,+2,+3,...n-1 ≡b(mod n);not b=0 ]와 같은 상황이 벌어지고 모든 계산이 끝날 때, 임의 홀수 m=29999999는 소인수들을 전통적인 [인수분해 없이 소수판별 필요조건n식.]으로 제공하게 된다. 이는 기존 방식의 알고리즘 인수분해로는 슈퍼컴으로도 불가능한 거대 홀수에 대해 마방진 소수판별2식.이 효과적으로 돌파구를 제시함을 의미한다.
|
|
|
|
|
|
|
