| [ QuizWit ] in KIDS 글 쓴 이(By): Nyang (바하동생) 날 짜 (Date): 2003년 12월 30일 화요일 오후 01시 18분 04초 제 목(Title): Re: CMI문제 P vs NP To darkman: > 그런데 RSA는 원천적으로 factoring 에 근거한거 아닌가요? 맞기는한데 아직 RSA 깨는 문제가 factoring하고 equivalent한지 증명이 안됐다는 뜻입니다. > 요새는 다른 알고리즘도 쓰겠지만. > 그리고 Factoring은 P라는게 증명이 안됐죠? > 고로 NP라는건 중요한 정보같은데요. > 소수인지 판별하는게 P라고 증명됐고. 예, 아직 factoring이 P인지 증명이 안됐고, 어느 클래스에 있는 문제인지 알지 못합니다. 의미가 없다고 한 이유는, RSA가 NP에 기반한 것처럼 읽힐 수 있기때문이었구요. To cdpark: > > 물론 factoring이 NP-Complete이 아니라는건 뭐 잘 아실테고. > NP != P 인 게 증명되지 않는 이상 이런 말은 성립하지 않습니다. :) 잘못 썼군요. 변명을 하자면 귀차니즘 때문에.. ^^ 원래는 factoring이 NP-Complete인지 아닌지 증명이 되지 않았다는 얘기로 쓴건데.. ;) @LFo |