| [ QuizWit ] in KIDS 글 쓴 이(By): Nyang (바하동생) 날 짜 (Date): 2003년 12월 29일 월요일 오후 11시 17분 18초 제 목(Title): Re: CMI문제 P vs NP 애매하게 쓴데: 1. > 수를 소수곱으로로 분해하는건 RSA암호키등 많은 수학쟁이들의 밥줄이니 > 아주 중요하죠. 아직까지는, RSA 깨는것 \neq 소인수 분해. ^^ 2. > RSA암호체계등이 소수분해가 자리수가 커짐에따라 기하급수적으로 > 시간이 걸린다른걸 이용하는거니까 정확히는 그냥 기하급수적은 아니고 sub-exponentially increasing.. :P 3. > 고로 소인수분해는 NP입니다. factoring이 NP인건 맞는데, 뭐 P인 아무 문제 가져다 놔도 NP니까 특별히 의미있는 얘기는 아닌 듯. NP-Complete이라면 모를까. 물론 factoring이 NP-Complete이 아니라는건 뭐 잘 아실테고. 사족: 누가 anony에 NP=P이면 암호시스템 못 쓴다는 글을 쓴걸 본거 같은데, 위의 이유로 틀린 얘기.. NP-Complete에 기반한 암호시스템은 초기에 나왔다가 지금은 다 깨져서 안쓰이고 있음. 최근에 Lattice의 Closest Vector Problem(NP-Hard)을 이용한 암호시스템이 나왔었는데, 하나는 안깨진 대신 별로 실용적이지 않고(Ajtai96), 한쪽은 실용적이었는데 깨져버렸고(GGH97)... @LFo |