소수 판별 다항식 알고리즘 발견
글쓴이: Zeronine_ / 작성시간: 토, 2002/08/10 - 10:22오전
소수 판별 다항식 알고리즘이 발견되었다고 합니다.
"Prof. Manindra Agarwal and two of his students, Nitin Saxena and Neeraj Kayal (both BTech from CSE/IITK who have just joined as Ph.D. students), have discovered a polynomial time deterministic algorithm to test if an input number is prime or not. Lots of people over (literally!) centuries have been looking for a polynomial time test for primality, and this result is a major breakthrough, likened by some to the P-time solution to Linear Programming announced in the 70s.
One of the main features of this result is that the proof is neither too complex nor too long (their preprint paper is only 9 pages long!), and relies on very innovative and insightful use of results from number...."
Forums:
열씨미 코딩을 해볼려 하는데 시간이 딸리네요..(능력도 딸리고..)
열씨미 코딩을 해볼려 하는데 시간이 딸리네요..
(능력도 딸리고..)
int를 이용하여 a-prp, a-sprp 까지는 해 봤는데
바쁘다 보니 영 진도가 안나가네요.
어느 분이 받아서 위의 알고리즘을 구현했으면
해서 올립니다.
저도 틈나는 대로 해 보겠지만...
http://www.futsalkorea.com/amul/04/int_prime.zip
음 프리셀 맞추는 알고리즘도 NP 문젠가여?안 풀리는 11982
음 프리셀 맞추는 알고리즘도 NP 문젠가여?
안 풀리는 11982 를 풀 수 없을까여?
아님 안풀린다는 증명이라도..
허걱.. 겄대문에 고생 많이 했었는데..며칠 밤 고생하셨나 보네요..
허걱.. 겄대문에 고생 많이 했었는데..
며칠 밤 고생하셨나 보네요..
누가 11982 풀어줘요.. ^^
11982는 안 풀린다고 증명이 되었습니다. 증명을 보니 한페이지
11982는 안 풀린다고 증명이 되었습니다.
증명을 보니 한페이지 정도 되던데, 한페이지라고 깔보면 안됩니다.
기반 지식(최소한 정수론 정도)이 있어야 제대로 이해할겁니다.
인터넷을 찾아 보면 찾을수 있을겁니다. 제가 2년에 봤었는데..
참고로 11982인지는 기억이 가물가물 하군요.
허나 안풀리는게 분명히 하나 이상 있습니다.
안풀리는 문제가 있다는 예가프리셀 프로그램 안에 있죠.-1, -2
안풀리는 문제가 있다는 예가
프리셀 프로그램 안에 있죠.
-1, -2번 게임입니다.
물론 치트(?)키 눌러서는 깰수 있겠죠.
안풀리는 문제 번호 리스트가 나와있습니다.오래되서 기억은 나질 않습니
안풀리는 문제 번호 리스트가 나와있습니다.
오래되서 기억은 나질 않습니다만 십여개가 훨씬
넘었던 것으로 기억됩니다. 물론 증명까지 되어 있으니
못푼다라고 말할수 있는거겠죠.
똑똑한 고딩님아내가 하도 심심해서 당신의 방식을 풀어봤소만p가 4
똑똑한 고딩님아
내가 하도 심심해서 당신의 방식을 풀어봤소만
p가 4일때도 당신의 방법대로 하면 성립합디다...
4가 언제부터 소수였던 것이요?
뭐 내 계산이 틀렸을지도 모르오
똑똑한 고딩님이 직접 4를 한번 넣어보시구려...
드디어 말이 통하는 분이 나타나셨군요 ^^;그렇군요. 저는 단지 성립
드디어 말이 통하는 분이 나타나셨군요 ^^;
그렇군요. 저는 단지 성립하는것 까지만 생각해보고, p가 소수가 아닐때도 성립할것이라는건 생각을 못했습니다.
전 이런 글에 화를 낼만큼 어리석지 않습니다.
제발.. 자기와 의견이 다르다고 상대방을 몰아붙이지 맙시다.
인신공격을 하는게 그렇게 즐겁습니까?
바람직한 토론 문화 정착 -_-;
드디어 라니 밑에 그놈이다.내가 얼마나 심심했으면 계산까지 해주겠냐
드디어 라니 밑에 그놈이다.
내가 얼마나 심심했으면 계산까지 해주겠냐 이놈아...
그런식의 글을 올려봤자 3자 입장에서 보기엔 님만 안좋게 보일 뿐입니다^
그런식의 글을 올려봤자 3자 입장에서 보기엔 님만 안좋게 보일 뿐입니다^^
간단한 계산인데.. 왜들 안해보시고 본문만 믿으시는지 -_-; 고등학
간단한 계산인데.. 왜들 안해보시고 본문만 믿으시는지 -_-;
고등학교 졸업한지 오래되서 다 잊어버리셨나요? -_-;
제가 무엇을 말하는건지 이해가 안되시는지? a=kp(k는 정수)가 무슨뜻입니까? a가 p의 배수라는거 아닙니까.
제가 바라던 답변이 그런거였습니다 ^^
이상 상당히 예의바른 고등학생이 보여준 좋은 태도의 표본이었습니다. >.<
고딩님아... '상당히 예의바른' 이란 말은 당신한테 어울리지 않는 말이
고딩님아... '상당히 예의바른' 이란 말은 당신한테 어울리지 않는 말이외다.
> 그니까요 -_-;
> 안그래도 된다는 말입니다.
맨 처음 문제가 된 글인데... 토론할때는 안그래도 된다고 우길려면 이유를 분명히 말해야 되는거 아니오? 다른사람이 왜 당신의 주장에 반론을 내세웠다고 생각하시오?
> 간단한 계산인데.. 왜들 안해보시고 본문만 믿으시는지 -_-;
> 고등학교 졸업한지 오래되서 다 잊어버리셨나요? -_-;
인신공격성 발언이었소. 토론할때 해서는 안되는 금기중 하나요.
> 제발.. 자기와 의견이 다르다고 상대방을 몰아붙이지 맙시다.
본인이 먼저 시발점을 제공하지 않았소? '고등학고 졸업한지 오래되서 다 잊어버리셨나요' 운운 하면서...
> 인신공격을 하는게 그렇게 즐겁습니까?
내가 당신에게 묻고 싶은 말이오
> 바람직한 토론 문화 정착 -_-;
당신이 할말이 절대로 아니오.
> 그런식의 글을 올려봤자 3자 입장에서 보기엔 님만 안좋게 보일 뿐입니다^^
자기 자신은 남들에게 어떻게 보인다고 생각하시오?
> 간단한 계산인데.. 왜들 안해보시고 본문만 믿으시는지 -_-;
> 고등학교 졸업한지 오래되서 다 잊어버리셨나요? -_-;
저거 연구한 사람들 학력이 당신보다 못하다고 생각하시오? 게다가 오류가 있었다면 화제거리가 될 수 있었다고 생각하시오?
> 이상 상당히 예의바른 고등학생이 보여준 좋은 태도의 표본이었습니다. >.<
다른나라나 외계에서 오신 거 같구려. 옛날부터 우리나라, 아니 동북아시아 문화권에서는 자화자찬을 상당히 꼴사나운 짓거리로 치부했소. 거기다가 >.<라니... 정말 꼴사납소. 그것도 일종의 ddr이라는거 아시오? ddr을 쌔우려면 남들이 안보는 곳에서 혼자 쌔우시오.
관리자는 저 고딩이 쓴 글과 이글에다가 가차없이 -1점을 매겨주시면 대단히 감사하겠소. 쓰레기는 태우거나 매장해야 하오.
오해가 있는거 같아서 리플 답니다.전 진짜 처음 글 올렸던 고등학생입
오해가 있는거 같아서 리플 답니다.
전 진짜 처음 글 올렸던 고등학생입니다.
이 위에 붙어져 있는 글은 제가 올린 글이 아닙니다.
IP... 가 안나오네요...
아무튼 제가 올린 글이 아닌데;
음..다시 읽어보니 아예 서로소라는 걸 부정하시는 것 같은데..제가
음..다시 읽어보니 아예 서로소라는 걸 부정하시는 것 같은데..
제가 보기엔 님이 계산한 경우들은 특수한 경우에만 성립하는 게 아닐까요..
a = kp라고 해서 다 성립하는게 아니란 거죠..
그 다항식을 만족하는 (a,p)쌍을 원소로 하는 집합이 있으면..그 속에 님이 말씀한 조건을 만족하는 것도 있게 마련이고..논문에서 제시한 조건을 만족하는 것도 있게 마련이지만..
a = kp이어도 다항식을 만족하지 않는 경우가 역시 있을 수 있다는 것이죠..
그런데 논문에서 제시한 a와 p가 서로소란 조건은 증명에 의해서 어느 경우에나 식을 만족 한다는 것입니다..
단순히 몇몇경우를 계산해보고, 이것으로 저 논문은 틀렸다..이렇게 말할 수는 없는 것이지요..
아직 고등학생이라고 하셨으니 공통 수학책을 보시고, 명제 부분의 필요 충분 조건 파트를 잘 읽어보시고 이해를 하시면 제 말이 무슨 말인지 이해가 되실 겁니다..
만약에 모든 경우에 다 성립한다..그런 것이라면 말로나마 증명을 한 번 해주십시오..
수학이란건, 증명이 생명입니다..
제대로 된 증명은 감히 반박조차 할 수 없는 위력을 가지죠..-_-;
수치대입법으로 해본게 아니라.. 문자로 해봤습니다만
수치대입법으로 해본게 아니라.. 문자로 해봤습니다만
저도 대강 풀어봤더니 맞긴 맞습니다..그런데..님이 제시하신 조건
저도 대강 풀어봤더니 맞긴 맞습니다..
그런데..
님이 제시하신 조건은 p가 소수일때만 성립하는게 아니라 모든 경우에 대해서 다 성립하는 경우이죠..
모든 항에 계수로 p가 들어가니 당연히 p로 나누면 나머지가 다 같을 수 밖에 없습니다..-_-;
즉, 저 식을 항등식으로 만들어버리는 조건이라는 소리입니다..
적절한 예가 될진 모르겠지만..부분 적분에서..
S(uv') = uv - S(u'v)
S(u'v) = uv - S(uv')
이런 식으로 풀어서 결국은 똑같은 식으로 되돌아오고 마는..
의미없는 조건을 만들어버린 것이지요..
님이 제시하신 그 조건으로는 소수 판정법을 사용할 수 없습니다..
그냥 보고만 있자니 어이가 없지만,나도 한때 저랬구나 생각하면서 머나
그냥 보고만 있자니 어이가 없지만,
나도 한때 저랬구나 생각하면서 머나먼 과거를 떠올려 봅니다.
본인도 고등학교때,
복소수를 이용하여 주기 수열을 해결하여 상당히 우쭐하였었던 적이 있었습니다. 물론 그것 말고도 고등학교 수준으로는 조금 감당하기 힘든 사이클로이드같은 운동형 곡선도 고찰하였고 기타 고등학교에서 배우는 것에서 조금 앞서가는걸 스스로 해결하고 거만을 떨었지요. 그러면서 스스로는 매우 겸손한듯 형식적 예의를 보이곤했답니다.
그런데 그 후 많은 것을 알게 되면서 느낀건 위대한 천재들이 한 것들이 왜 그들을 위대하게 만드는가하는 것이죠.
이 위대함들은 단지 재능에 의해서가 아닙니다. 재능 이면에 그들만의 심오한 사유가 있으며 그것을 알때 비로소 겸손해질 수가 있었습니다. 뭐 사실 늘 겸손해지는건 아니고 가끔 그 사유를 떠올리면 감탄과 깨달음을 얻는데 제가 그들의 사유를 따라가지 못하는터라 아직 많은 위대한 분들의 업적을 제대로 파악하지는 못합니다. 더 자세히 말하면 뭔가 깨달은 분은 몇분 안되지요.
피타고라스가 "모든건 숫자다"라는 도발적인 주장을 하였는데 이것 생각하면 할 수록 어떻게 이런 생각을 했는지 놀랍습니다. 요즘 세상이라면 이런 생각을 할 수도 있겠지만 당시에 겨우 피타고라스 정리 하나 발견하고 감동하신 분이 이런 사유를 했다는 것이 실로 놀랍지요. 이 분은 단지 피타고라스 정리뿐만아니라 자연계엔 그 무언가의 논리정연한 수학적 질서가 있다는 것을 간파하신 분입니다. 이 분의 통찰력! 정말 존경스럽습니다.
이런 식으로 머리를 쑥이고 한 수 배운다는 자세로 접근하며 보다 더 많은 것을 알 수 있겠다라는게 저의 경험에서 우러나는 말입니다.
님들 다 머하시는분들이세요?난 먼소린지 하나두 모르겟네 ㅜ,ㅜ
님들 다 머하시는분들이세요?
난 먼소린지 하나두 모르겟네 ㅜ,ㅜ
소수 판별 다항식 알고리즘? 이건 뭐에 쓰나?라고 생각할 수도 있습니다.
소수 판별 다항식 알고리즘? 이건 뭐에 쓰나?라고 생각할 수도 있습니다.
그러나, 이 알고리즘은 여러 분야에 적용이 가능하겠지만, 특히 보안(암호)분야에서는 뜨거운 이슈가 되기에 충분한것입니다.
1970년말에 만들어지고 국내에서도 최근 몇년간 빅이슈로 등장했던 공개키(PKI : public key infrastructure) 방식중, 특히, RSA의 공개키방식은 그 비밀키와 공개키의 안전성(보안에서 안전성은 매우 중요)을 "소수를 찾아내기 힘들다!"라는 것에 근거하고 있습니다.
1자리짜리 소수 즉, 2,3,5,7부터 2자리 수 정도는 매우 쉽게 소수를 찾아내지만, 다음과 같은 소수를 찾아내는것은 쉬운 일이 아닙니다.
약수 = { 1, 소수1, 소수2, 소수1 X 소수2 } 를 만족하는 소수로 10자리를 가지는 수는?
모 이런식이지요.
이런 수를 계산하는 것은 수퍼컴퓨터로도 천년이 걸리느니 모 이런 얘기랍니다. 즉, 풀리기는 하겠지만, 아주 오랜 세월이 지나야만 가능하기 때문에 현재로부터 당분간(?)은 안전하다라는 사실에 근거해서 만들어진 것입니다.
소수 판별하는 다항식 알고리즘이 기존 방식에 비해 느려서 아직은 위협적인 요소는 아니지만, 속도개선이 이뤄진다면, 현존하는 RSA방식의 공개키들은 전면 교체되어야 하겠지요?
(그럼 보안업체들 잠시 업그레이드하느라 먹고살기도 좋을듯 ^^)
* 하지만, 공개키에서는 소수를 사용한 방식말고도 많은 다른 방식들이 사용되고 있긴하지요.
어쨋거나, 신규 알고리즘의 발견은 박수를 보내야 할 일인것 같습니다. 짝짝짝~짝짝 .
RSA의 안정성은 소수임을 판별하느냐 문제가 아니라 두 소수의 곱으로 이
RSA의 안정성은 소수임을 판별하느냐 문제가 아니라 두 소수의 곱으로 이루어진 수를 소인수 분해하는 문제하고 연관이 있는 걸로 알고 있는데요.
그렇다면 여기서 논의되고 있는 새로 발견된 알고리즘은 RSA의 안정성과는 별개의 문제 아닌가요?
별개의 문제 맞씀다
별개의 문제 맞씀다
음.. 밑에 글 썼던 고등학생인데요...이상한게 있어서...밑
음.. 밑에 글 썼던 고등학생인데요...
이상한게 있어서...
밑에 어떤분이 한글로 올려주신 계산식에서
a=kp (단, k는 정수) 라는 조건이 붙으면 되는데 말이죠.a
Suppose that a is coprime to p. Then p i
Suppose that a is coprime to p. Then p is prime if and only if
(x - a)**p ≡(x**p - a)(mod p)
a와 p는 서로 소!!
그니까요 -_-;안그래도 된다는 말입니다.
그니까요 -_-;
안그래도 된다는 말입니다.
수학에는 "안그래도 된다는 말입니다."라는 말이 없죠.그걸 증명하면
수학에는 "안그래도 된다는 말입니다."라는 말이 없죠.
그걸 증명하면 됩니다.
여기서 수식을 써넣지 못해서 그럽니다.간단한 계산인데.. 왜들 안해보
여기서 수식을 써넣지 못해서 그럽니다.
간단한 계산인데.. 왜들 안해보시고 본문만 믿으시는지 -_-;
고등학교 졸업한지 오래되서 다 잊어버리셨나요? -_-;
a=kp(단, k는 정수)일때 성립하고, 저 밑에 a
혹시 decimal하고 prime number를 구별 못하는것 아닐까?
혹시 decimal하고 prime number를 구별 못하는것 아닐까?
a=kp(단, k는 정수)에서 k,p가 정수인데 a가 소수가 될 수 있나
a=kp(단, k는 정수)에서 k,p가 정수인데 a가 소수가 될 수 있나요?
두 정수 사이에 1이외의 공약수가 없을때, 이들 수는 "서로 소"라고 합
두 정수 사이에 1이외의 공약수가 없을때, 이들 수는 "서로 소"라고 합니다.
1.5는 정수가 아니죠. -_-"
그리고 밑에 a
이것도 뭔가 잘못읽은게 아닌가 추측합니다.논문을 요약하면 p는 소수이고, a는 p보다 작은 수 일때, 아래
논문을 요약하면
p는 소수이고, a는 p보다 작은 수 일때,
아래 항등식을 만족한다.
(x - a)^p = (x^p - a) (단 양항에 mod p 연산을 취할것)
a는 p보다 작은 수...
근데 서로소라는 말이 어디서 나왔나요. 제가 무엇을 말하는건지 이해가 안되시는지? a=kp(k는 정수)가 무슨뜻입니까? a가 p의 배수라는거 아닙니까. 물론 서로소가 아니죠. 성립합니다. 계산해보세요.
coprime이 "서로 소"라는 뜻이고...논문을 요약하면이라는 글
coprime이 "서로 소"라는 뜻이고...
논문을 요약하면이라는 글 자체가 잘못되어 있군요. ㅎㅎㅎ
아 그렇군요 ^^제가 바라던 답변이 그런거였습니다 ^^감사합니다
아 그렇군요 ^^
제가 바라던 답변이 그런거였습니다 ^^
감사합니다 ^^
저밑에서도 이미 서로소가 맞는거 같다고 수정해 주고 있는데요즘 고등학
저밑에서도 이미 서로소가 맞는거 같다고 수정해 주고 있는데
요즘 고등학생은 국어도 못읽나?
큰일이네...
뭘 원했단 얘기쥐... 재미나네
다시 원점으로 돌리는데다가 인신공격성 글이군요. 참 답답한 노릇입니다.
다시 원점으로 돌리는데다가 인신공격성 글이군요. 참 답답한 노릇입니다. 제가 원했던 대답은
논문을 요약하면이라는 글 자체가 잘못되어 있군요. ㅎㅎㅎ
이것이었습니다. 서로소라는건 틀립니다. 똑같은 내용을 위에 썼기에 반복하지 않습니다. 왜 자꾸 직접 계산도 안해보고 태클을 거는건지. 그렇게 인신공격할만큼 님은 대단한 사람입니까? 고등학생이라고 우습게 보이십니까? 기본적인 인격을 갖추지 못한 사람은 토론에 참여할 자격이 없습니다.
끼어드는 것 같지만..원문에 보면..Suppose that a i
끼어드는 것 같지만..
님은 논문도 안 읽어보고 아랫 분이 해석하신 것만 보고 이러시나 본데..원문에 보면..
Suppose that a is coprime to p
조건이 이렇습니다..
즉, a와 p가 서로 소란 이야기이지, a
(그 해석 올리신 분도 다시 수정해서 답글 다셨습니다..)
그러니 지금 이렇게 논쟁에 휩싸이게 되는거죠..-_-
서로소라는게 틀렸다는 얘기가 아니니 하는 소리잖아...a<p가 틀렸다
서로소라는게 틀렸다는 얘기가 아니니 하는 소리잖아...
a
계산에 사용했던 변수값들을 주면 계산해 보지요.참고로 난 다른 겁쟁이
계산에 사용했던 변수값들을 주면 계산해 보지요.
참고로 난 다른 겁쟁이요.
#include<stdlib.h>#include<stdio.h>#
#include
#include
#include
int main(void)
{
int i;
for(i = 2; i < 30; i++)
if((((long)pow(2, i))%i - 1) == 1)
printf("%d\n", i);
return EXIT_SUCCESS;
}
/* Edition... by 동일인 */#include<stdl
/* Edition... by 동일인 */
#include
#include
int main(void)
{
int i;
unsigned long power;
printf("%d\n", 2);
for(i = 3, power = 8; i < 40; i++, power *= 2)
if((power%i - 1) == 1)
printf("%d\n", i);
return EXIT_SUCCESS;
}
제 친구한테 저거 보여줬더니... (저 고2)"당연하지~"
제 친구한테 저거 보여줬더니... (저 고2)
"당연하지~"
그러면서 증명을.. - -;
사삭사삭... (이해 못하고 있음)
"페르마의 정리~"
우잉... @.@a
정말 몰라서 그러는데요...P NP문제가 뭐예요???
정말 몰라서 그러는데요...
P NP문제가 뭐예요???
20세기초엔가.. 학교 문턱에도 못 가본 어떤 인도 사람이 대학교수도 쩔
20세기초엔가.. 학교 문턱에도 못 가본 어떤 인도 사람이 대학교수도 쩔쩔매는 수학 문제를 풀어냈다는 얘기들이 있죠. 영화 "굿윌헌팅"하고 비슷하죠.
라마누잔을 말씀하시는 거군요.
라마누잔을 말씀하시는 거군요.
이에 대해 http://www.zdnet.co.kr에도 기사가 나왔네요.
이에 대해 http://www.zdnet.co.kr에도 기사가 나왔네요.
원문 출처: http://www.zdnet.co.kr/biztech/hwsw/techtrend/article.jsp?id=51346&forum=0
인도 과학자, 정확한 암호화 연산 방식 개발
인도의 컴퓨터 과학자들이 컴퓨터가 소수 여부를 신속하게 판별해낼 수 있는 방법을 고안해 냄으로써 오랜 숙원이던 수학 문제의 해결했다. 이는 암호해독에 있어서 중대한 발전을 의미한다.
Sandeep Junnarkar (Special to ZDNet News )
2002/08/12
원문보기
전자 상거래 보안에 사용되는 암호화 알고리즘인 RSA는 자신 스스로나 숫자 1로만 나뉘는 소수(素數)를 판정해 낼 때 소수점 이하 수가 충분히 클 때 이를 소수로 추정하는 방식을 쓴다. 이 수가 소수인지 여부를 확실하게 판별해내는 것은 거의 불가능하다.
RSA 방식을 사용해 암호 키를 생성해낼 때 훨씬 큰 소수를 만들기 위해 대단히 큰 소수와 그를 곱한 수 두 가지를 사용한다. 이같은 현행 연산 방식은 속도는 빠르지만 오답을 산출할 가능성이 약간 있는 소수 판정법(primality tests)이라는 방식을 사용한다.
그런데 캉푸에 있는 IIT(Indian Institute of Technology)의 마닌드라 아그라울과 그의 학생인 니래즈 카얄, 니틴 새시나가 공동 개발한 새로운 연산 방식을 사용하면 매번 정확한 답을 산출하는 것으로 알려졌다.
뉴저지 주립대학 컴퓨터 과학과 에릭 알렌더 교수는 "현행 암호 해독 소프트웨어에서 가장 두드러진 단점은 어떤 수가 소수인지를 판별해 낼 수 없다는 것"이라고 말했다. "이번에 새로 고안된 연산 방식은 몇 세기 동안 미해결 상태였으며 지난 몇 십년 동안 열정적으로 연구가 진행되고 있는 기본적인 의문에 답을 제공한다."
아직 '소수(素數)는 P에 있다(Primes is in P)'라는 아그라울의 논문은 아직 출간되지 않았지만 고대 중국과 그리스에서 오랫동안 수학자들을 사로잡았던 수학 문제를 처리하는 방법을 제시한다는 점에서 이 분야를 흥분 속으로 몰아넣었다. 뛰어난 컴퓨터 과학자들과 수학자들은 이 논문을 연구했다.
알렌더는 "이 논문 가운데 일부는 상당히 복잡했다. 이것은 정말 사랑스럽고, 산뜻하며 훌륭한 연산"이라고 평가했다.
컴퓨터 과학자들은 아직 이 연산이 실용화되려면 시간이 필요하다고 인정하고 있다.
아그라울은 "이번 연구에서 소개된 연산은 현재 가장 빠른 것으로 알려진 소수 판정법 알고리즘보다 느린 것이 흠이다. 우리가 연구한 연산법이 만족스러운 것은 아니지만 오류가 생길 수 있는 기존 방법과 달리 완벽한 답을 제시한다"고 말했다.
컴퓨터 과학자들은 많은 영역에서 사람들이 종종 오류 가능성을 기꺼이 견뎌왔다고 말했다. 하지만 은행이나 보안 통신같은 분야에서 암호화에 대한 신뢰성 문제가 증가함에 따라 암호화의 정확성에 대한 문제가 최우선시되고 있는 실정이다.
알렌더는 "이번에 새로 나온 연산 방식은 이론적인 결과이며 첫발을 내디뎠다는 점에 가장 큰 의미가 있다. 앞으로 이번 연산 방식을 시작으로 이를 실용화할 수 있도록 기술을 개선하고 향상시켜 나가게 될 것"이라고 말했다. @
--
WTFM :-)
RSA 방식을 사용해 암호 키를 생성해낼 때 훨씬 큰 소수를 만들기 위해
RSA 방식을 사용해 암호 키를 생성해낼 때 훨씬 큰 소수를 만들기 위해 대단히 큰 소수와 그를 곱한 수 두 가지를 사용한다.
----------------------------------
결정적으로 위의 문장이 잘못 되었죠. zdnet.com에서는 talkback에서 난리군요. 잘못된 말이죠.
4장 알고리즘에서 12번째 줄 if( (x-a)^n =/= (x^n-
4장 알고리즘에서 12번째 줄
if( (x-a)^n =/= (x^n-a) (mod x^r-1,n) )
여기서 (mod x^r-1,n) 은 어떤 의미인가요?
논문을 읽어보니(x-a)^p = (x^p-a) (mod x^r-1
논문을 읽어보니
(x-a)^p = (x^p-a) (mod x^r-1,p) (2)
이 의미는 x^r-1 로 나머지를 구하고 p로 다시 나머지를 구하는 의미이군요.
아마 mod연산을 연속해서 2번한다는 뜻일겁니다..즉 a==b (
아마 mod연산을 연속해서 2번한다는 뜻일겁니다..
즉 a==b (mod c,d) 이란 말은 곧 (a%c)%d==(b%c)%d 이런 뜻일겁니다.
아마도 (x^(r-1)) % n.... -- 늘...
아마도
(x^(r-1)) % n....
--
늘...
엇.. 메르센느 소수찾기 프로젝트의 방향은어디로 흘러가게 될것인가 -
엇.. 메르센느 소수찾기 프로젝트의 방향은
어디로 흘러가게 될것인가 -_-
새삼스럽게 "페르마의 마지막 정리(FLT)"를 증명한 와일즈 교수가 생각
새삼스럽게 "페르마의 마지막 정리(FLT)"를 증명한 와일즈 교수가 생각하는군요.
페르마에서 와일즈까지 350년간의 드라마!
알고나면 정말 감동하죠.
제가 강조하고 싶은 부분은 페르마와 와일즈를 이어주는 많은 고리가 있다라는 사실.
묘하게도 그리고 독특하게도, 이 대수학적 정리가 타원 곡선이라는 기하학적 이론의 매칭으로 해결되었죠.
시작점은 타원곡선과 "시무라-타미야마 예상"에서 출발하고, 프라이가 그것을 FLT에 연관시키고, 세르가 결정적인 두부분중 한 부분을 증명했죠.
그리고 그 나머지 하나인 "시무라-타미야마 예상"중 일부를 와일즈가 해결하므로서 막을 내리는데..
세계가 경악을 했죠. 저도 경악했습니다.
그런데 단지 놀라기만하거나 감동만 했다면 기분이 일회성이었겠죠.
중요한걸 놓치면 안되죠.
중요한건 이런겁니다.
"페르마의 마지막 정리"는 완전히 대수학적인 명제입니다. 그런데 대수학적인 접근으로는 해결책을 내지 못하고 기하학적인 접근을 통해 해결을 봤다라는 것입니다.
즉 어떤 문제를 해결하는데 있어서, 다른 관점에서 시도한 후 해당 문제와 연결 고리를 형성하고 이것을 해결하므로서 원래 문제를 해결할 수도 있다라는 것입니다.
카예가 모든 NP 문제는 서로 변환이 가능하다라는 것을 증명했지요. 그것도 우리에게 익숙한 "지뢰찾기"를 이용해서 말이지요.
그래서 NP 문제중 단 한개라도 P 문제로 만들수가 있다면 모든 NP는 P다라고 말할 수가 있게 되는겁니다. 이것이 유명한 P vs NP 문제이지요.
한때 저의 아둔한 머리로 지뢰찾기 알고리즘을 P로서 구현해볼려고 시도했으나 좌절을 맛보기도 전에 그냥 포기했었습니다.
혹시 님도 시간나면 지뢰찾기를 P 복잡도(다항시간 복잡도)로 해결하는 알고리즘을 만들어 보세요. 이 문제에 100만달러 걸려있습니다.
혹시라도 풀고나면 카예 교수에게 email로 알고리즘 보내면 될겁니다. 그럼 검증도 해줍니다. 카예 교수에게 많은 알고리즘이 보내졌다고 하는데 독특한 것은 꽤 있으나 아직 제대로된 해결책은 없었다고 합니다.
(x - a)^p = (x^p - a) p는 소수이고 a는 p보다
(x - a)^p = (x^p - a)
p는 소수이고 a는 p보다 작은수일때 대입해서 풀어봤는데, 이상하게도 x가 p보다 작을때만 공식이
성립합니다.
예를들면, p=23 ,a=1,x>=23 이면 서로 같지가
않다고 나오네요..
turbo C 에서,
(x - a)%p = (x%p - a)
로 풀어본건데, 이상하네요..
^는 mod를 의미하는게 아니라 지수승을 의미하는 것입니다.C에서
^는 mod를 의미하는게 아니라 지수승을 의미하는 것입니다.
C에서 지수승을 지원하는 함수는 pow입니다. 써본지가 오래되서 확실치는 않음.
근데 알고리즘 시간에 배운 바로는 NP 문제들은 서로 얽혀 있기 때문에
근데 알고리즘 시간에 배운 바로는 NP 문제들은 서로 얽혀 있기 때문에 한가지만 제대로 풀어도 NP 문제들을 한 꺼번에 풀수 있다고 그랬는데, 여기와는 상관이 없는 걸까요??
만약 이것이 힌트가 된다면, 정말 큰 사건 일수도 있죠...^_^ ( 문제는 아닐 확률이 더 높다는 거...)
최소한 비슷한 문제들을 다항시간으로 풀수만 있어도 말이죠...그럼~
소수 판멸이 P 문제라는 것이 밝혀졌다는 얘기 아닌가요?
소수 판멸이 P 문제라는 것이 밝혀졌다는 얘기 아닌가요?
수학에 대해선 거의 문외한이나 다름없지만..음.. 인도 사람들이 수학
수학에 대해선 거의 문외한이나 다름없지만..
음.. 인도 사람들이 수학을 잘 한다는 얘기가 실제로 입증이 되는군요. :)
하하.. Off-topic 입니다만 저같은 경우엔 인도하면 생각나
하하..
Off-topic 입니다만 저같은 경우엔 인도하면 생각나는 것은 카레와 홍차와 HAL 9000입니다.. 2001: A Space Odyssey의 HAL을 만든 일리노이 어바나 대학의 Dr. Chandra가 인도 출신이었죠..
전 코끼리도 생각납니다. 코브라하구. :-)
전 코끼리도 생각납니다. 코브라하구. :-)
(x - a)^p = (x^p - a) (단 양항에 mod p 연산을 취
(x - a)^p = (x^p - a) (단 양항에 mod p 연산을 취할것)
위에글에서, "mod p 연산을 취할것" 의 말뜻이
잘모르겠는데, 아시는분 답변 부탁드려요..^^
mod는 나머지 연산자입니다.파스칼 쪽에선 mod연산자를 사용하고
mod는 나머지 연산자입니다.
파스칼 쪽에선 mod연산자를 사용하고
c에서 %연산자를 사용하져
제 짧은 지식으로 위 뉴스를 요약하고 나름대로 설명을 덧 붙여 보겠습니다
제 짧은 지식으로 위 뉴스를 요약하고 나름대로 설명을 덧 붙여 보겠습니다.
고대부터 사람들은 다른 수로 나누어 지지 않는 수(물론 1과 그 자신 이외에), 소수를 다른 수에 비해 중요하다고 생각했습니다. 그런데 그 수의 일련적인 정수상에서 위치가 어떤 규칙이 있지 않을까 찾아 보았지만 알 수가 없었습니다. 소수인지 아닌지 판별하는 방법은 있었지만(중학교 때 배운 방법들) 소수를 생성해 내는 규칙은 이제껏 수수께끼 였던 것입니다.
논문을 요약하면
p는 소수이고, a는 p보다 작은 수 일때,
아래 항등식을 만족한다.
(x - a)^p = (x^p - a) (단 양항에 mod p 연산을 취할것)
논문의 나머지 부분은 앨거리듬의 속도개선과 수식의 증명입니다.
앞에서 언급하셨듯이 기존의 통계학적 방법(원의 면적을 구할때, 모래알을 하나씩 난수로 뿌리고 뿌린 모래의 갯수를 알고 있다고 할때, 도화지 상의 원 안과 밖의 모래알 수를 비교함으로써 원의 면적을 구하는 방법. 모래알이 많을 수록 더 정확해 집니다.)이 더 빠르기 때문에 기존 소수를 이용한 암호에 직접적인 해를 끼치진 않을 것 같습니다만 또 모르겠습니다.
f=ma 라는 간단한 곱셈으로 이루어진 식이 고전물리를 대표함을 볼때, 위 처럼 생긴 공식도 더 심오한 자연현상을 나타내지 않을 지 궁금하군요. (웜홀 :D)
pdf 받아서 받는데.. 역시 짧은 저의 수학실력을 여실이 들어내는군요
pdf 받아서 받는데.. 역시 짧은 저의 수학실력을 여실이 들어내는군요 ㅠ.ㅠ
그런데 항등식 조건에서 coprime 면 서로서 않인가 싶어서 질문 드립니다.
[이해 하는데 한달 걸리겟다. -.-;..]
그 pdf 저도 받아 볼 수 있을까요?평소에 수학에 관심이 있어서
그 pdf 저도 받아 볼 수 있을까요?
평소에 수학에 관심이 있어서 인터넷에서 찾았는데 결국 찾지 못했습니다.
구하는 방법을 좀 알려주세요.
찾았습니다.처음 글을 올리신 Zeronine 님의 글에서 관련링크를
찾았습니다.
처음 글을 올리신 Zeronine 님의 글에서 관련링크를 쫓아가서 얻었습니다.
난 정말 바본가봐... 쩝..
지적 감사합니다. coprime이 서로서 맞습니다.예를 들어 p가 5
지적 감사합니다. coprime이 서로서 맞습니다.
예를 들어 p가 5일 때, 1을 제외한 5와의 최대공약수가 없는 4, 6(5보다 큰).. 등등의 숫자가 a가 되는 것입니다.
f=ma도 3차원 상의 운동을 기술할 때는 vector표기를 해 주어야 하는데.. 에구
[전 수식 증명 부분은 이해하는 데 족히 2년은 걸릴 듯.]
저.. 나머지 연산에 개념이 약해서 그런데요.그렇다면 다음 수식이 되
저.. 나머지 연산에 개념이 약해서 그런데요.
그렇다면 다음 수식이 되는 건가요 ?
((x-a)^p) mod p = (x^p -a) mod p
맞는 지 답변 부탁드립니다..
결론 P=2일때는((x-1)^2이 짝수 이면,(x^2-1)은 언제
결론 P=2일때는
((x-1)^2이 짝수 이면,
(x^2-1)은 언제나 짝수이다.
입니까?
네, 맞습니다.
네, 맞습니다.
대충 보니 이 알고리즘 recursion인거 같은데...
대충 보니 이 알고리즘 recursion인거 같은데...
그럼 이제 웜홀 사이를 통과해서 우주여행 할 수 있는겁니까? ^^
그럼 이제 웜홀 사이를 통과해서 우주여행 할 수 있는겁니까? ^^
RSA알고리즘 푸는 시간이 많이 줄어 들겠네요.ㅋㅋㅋ...앞으로
RSA알고리즘 푸는 시간이 많이 줄어 들겠네요.
ㅋㅋㅋ...
앞으로 인간의 한계가 어떻게 될지..^^*
아무튼,,..기쁘네요..^^*
이렇게 풀릴 문제를 오랜세월두고 풀었다는 것이 인간의 한계 아닐까요? :
이렇게 풀릴 문제를 오랜세월두고 풀었다는 것이 인간의 한계 아닐까요? :-)
이번 학기 알고리즘 과목을 들으면교수님이 이것을 코딩해 오는 숙제
이번 학기 알고리즘 과목을 들으면
교수님이 이것을 코딩해 오는 숙제를
내실까 두렵네여..^^;;;
논문의 introduction을 얼핏 봤는데,기존에 제안된 방법보다
논문의 introduction을 얼핏 봤는데,
기존에 제안된 방법보다
실제로 더 빠른지는 모르겠네요.
이론적으로야
의미가 있겠지만...
최초로 polynomial 시간에
소수인지를 판별하니까요.
논문을 보면서 한번 코딩해볼까 했는데....귀찮은 생각이 들어서...
논문을 보면서 한번 코딩해볼까 했는데....
귀찮은 생각이 들어서... ^^*
귀찮음이 고양이를 죽이는군요(^^;;;)
아무튼... 슬슬 그동안 해결 못했던 것들이 해결되기 시작 하는군요...
그런데 알고리즘은 몇줄 않되지만... 코딩하면 쪼금 많이 나올것 같던데...
gcd구하는 것도 나와야 하고... 리커전으로 풀어야 할것 같은데....
진짜 복잡도가 그렇게 작다니.... 논문을 쫌더 열심히 봐야 겠군요...
누군가 먼저 코딩 해주면.... 좋겠다.... ^^*
--
늘...
허걱~~발견된 방법의 증명이 복잡하지도 길지도 않다고 까지.
허걱~~
발견된 방법의 증명이 복잡하지도 길지도 않다고 까지.
그나저나 RSA 암호화의 기본 조건중 하나가 "다항 시간내에 소수를 판별하는 알고리즘이 없다"라는 것인데.
내친김에 P vs NP 문제까지 풀리면 암호화는 그순간 끝장날듯.
너 바보지?소수판별알고리즘이 아니라 소인수분해 알고리즘이 rsa해
너 바보지?
소수판별알고리즘이 아니라 소인수분해 알고리즘이 rsa해독과
관련이있어 바붕아.
다항시간이 무슨 뜻인가요?? :-)
다항시간이 무슨 뜻인가요?? :-)
DTSTTCPW
문제의 크기를 n이라할때 이 문제를 해결하는데 드는 시간을 n에 대해표현
문제의 크기를 n이라할때 이 문제를 해결하는데 드는 시간을 n에 대해표현할
때 그 식이 다항함수로 표현될때를 말합니다. 여기서는 소수의 값이 n이라고
본다면 소수가 점점 커짐에 따라서 이 수가 소수인지 아닌지를 판별하기위한
계산 회수가 n에대해 다항함수로 표현될수 있는 정도라는 것이죠. (n^3과 같
이)
보통 문제의 규모가 커질수록 그 문제를 해결하는 데 오랜 시간이 걸립니다
보통 문제의 규모가 커질수록 그 문제를 해결하는 데 오랜 시간이 걸립니다.
이를 테면, 정렬되어 있지 않은 크기가 n인 배열에서 어떤 값을 찾고자 할때
처음 원소부터 끝원소까지 순차적으로 검색하면 평균적으로 (n+1)/2번 비교
해야하므로 배열이 2배, 3배, 4배 커짐에 따라 시간도 2배, 3배, 4배 커집니다.
그런데 어떤 문제는 아주 복잡해서, 그 문제를 해결하는 알고리즘 위처럼 시간이 선형적으로 증가하지 않고 2^n이나 n!처럼 폭발적으로 시간이 증가합니다.
반면, 현실적으로 사용할 수 있는 알고리즘은 n^3, n^2, n처럼 다항함수의
형태를 가지고 있습니다. 즉, 문제를 해결하는 알고리즘이 문제를 해결하는데
걸리는 시간이 다항함수이면 현실적으로 컴퓨터를 이용하여 계산해 낼 수
있고 적절히 사용가능하지만, 다항함수보다 큰 2^n, n!같이 다항함수보다
더 폭발적인 증가율을 보이는 알고리즘은 작은 크기의 문제나 협소한 범위
내에서만 사용가능합니다.
제가 아는 바에 의하면, 잘 알고 있는 소수 판별 알고리즘은 ( 일일히 나누어보는 것) 대체로 2^n 알고리즘입니다. 근데 저 알고리즘이 다항함수의 시간안에
수행된다면, 훨씬 작은 시간안에 해결할 수 있다는 거죠. :)
RSA암호화의 기본 조건은 "큰 수를 소인수 분해 하기가 어렵다" 입니다
RSA암호화의 기본 조건은 "큰 수를 소인수 분해 하기가 어렵다" 입니다.
어떤 수가 소수인지를 빠르게 판별하는 알고리즘은 이미 있었습니다.
다만 확률로 접근을 해서 틀릴 가능성이 아주 아주 조금 있어서 그렇죠.
어떤 수가 소수인지를 빨리 판별하는 것과 어떤 수를 빨리 소인수분해 하는
것은 다른 일입니다.
죄송한데요. 좀 더 자세히 설명 부탁드려도 될까요? 수학은 여엉 꽝이라.
죄송한데요. 좀 더 자세히 설명 부탁드려도 될까요? 수학은 여엉 꽝이라...
우와...암호학에는 어떤 영향을 주게 될까요..??
우와...
암호학에는 어떤 영향을 주게 될까요..??
이야..이거 대사건이군요..이제 중고등학교 수학교과서부터 싹 다 바뀌
이야..이거 대사건이군요..
이제 중고등학교 수학교과서부터 싹 다 바뀌겠네요..헐헐..
중고등학교 교육과정에 포함될정도로 쉬운거 같지는 않은데요.. -_-
중고등학교 교육과정에 포함될정도로 쉬운거 같지는 않은데요.. -_-
대단하네요..(뒷북)
7년이나 지난 걸 이제야 알다니.
아직 증명을 잘 이해못하겠지만
이해하도록 노력해야죠.^^
이전에도 소인수분해에서
타원곡선을 이용해 상당히 빠른(!)알고리즘이 있었고., 리만 가설이 참일때 다항식알고리즘이 되는 공식이 있었습니다. 소수판별은 페르마 소정리를 이용해 상당히빠른 방법도 있지만 카마이클수라는 문제가 있는데, 재수없게 걸릴 확률이 낮아서 그냥 쓰고 있는 겁니다,. 여기나온 방법이 그것보다 더빨라져야 하는데 가능할지 의문입니다.