면접에서 소수구하는 알고리즘을 짜라 하면 짤수있음?

[dijkstr..(168.115)]

난 10분안엔 못할꺼같은데..

정보처리기사 책 펴서 다시 찾아봐야될거같음.

정보처리기사처럼 빈칸넣기라면 모를까..

차라리 최단경로 알고리즘 슈도코드로 적어라면

당황은 덜 할겠네여 ㄷㄷㄷ

[어머나.(115.23)]

소수가 난리네. 정보처리 기사 따위에 있을 만한 알고리즘이 아니고, 적어도 위키 정도 가야됨.
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

[-_-)(218.48)]

저 밀러-라빈 소수판별 알고리즘도 정확하게 소수를 판별해주진 못함. 여러번 돌리면 가능성이 높긴 하지만..

[-_-)(218.48)]

RSA 만들때 해보긴 했는데 제대로 하려면 결론은 에라스토테네스 체 같은걸로 미리 계산해 놓은 소수 테이블 뿐이었음... 넵 스페이스의 압박....

[물론(115.23)]

ㄴ소수도 엄연히 NP 문젠데 어찌 정답을 구하는 알고리즘이 있겠는가. 글고 알골 교수 말로는 대강 50번 정도 돌리면 하나는 나온다던디.

[-_-)(218.48)]

ㄴ넵 존니 돌려야 나옵니다. 문제는 그 돌려서 나온것도 컴퓨터로 이게 소수인지 정확히 판별하기 거진 불가능하다는게 문제였져... 소수가 아니면 RSA의 핵심인 오일러의 정리가 성립이 안되는데.

[-_-)(218.48)]

여튼 학부때 정보보호 플젝이 RSA구현이었는데, 밀러-라빈으로 RSA 알고리즘의 prime number p,q를 제네레이션하려다 문제가 존니 발생해서 그냥 테이블 쓴 경험이 있었음....-_-;;;

[1(143.248)]

소수판별 P인데? 물론 P가 NP에 속하지만

[-_-(115.23)]

ㄴ2~(N / 2)까지 나눠보지 않으면 풀리지 않는 문제이고, NP 중에 그나마 O(n)의 형태로 착각할 수 있겠지만, 비트를 n으로 보면, O(2^n) 문제가 맞습니다요. 대개 n비트 소수를 구하라고 하니까요.

[-_-)(218.48)]

게다가 RSA에서 요구하는 소수 비트수는 대개 1워드를 훌쩍 넘어서는 경우가 대부분이라..

[-_-)(218.48)]

long long따위도 안됨. 몇비트인지는 까먹었는데 빅인티저를 하나 썼어야 했음..

[1(143.248)]

2~(N/2)까지 나눠보지 않으면 풀리지 않는 문제라는 것은 너의 생각이고요, 주어진 숫자가 n이면 poly(log(n))에 풀 수 있어서 P에 속한다고한건데 뭔소리함요?

[1(143.248)]

그리고 N/2가 아니고 루트N입니다 고갱님

[-_-)(218.48)]

소수 판별이 아니라 n비트 소수 구하는게 어렵다는 이야기였는듯여.. 정보보호 들은지 오래되서 -_-

[-_-)(218.48)]

그럴려면 사실상 N비트 홀수 랜덤으로 찍어서 판별 알고리즘 돌리고 틀리면 디스카드하는거밖에 없지 않음?

[-_-)(218.48)]

위키백과 보니까 The existence of the AKS primality test finally settled this long-standing question and placed PRIMES in P..라고 나와있네. P Complete인진 알려져 있지 않다고 했지만.

[dijkstra(168.115)]

면접에서 물어본게 특정범위안에서 소수구하라는 문제 아니었어여?

[1(143.248)]

n비트 소수를 암거나 찾는거라면 모름ㅋ