[일반] 밀러라빈 소수검출 쓰는 문제 있냐?

[익명(116.38)]

정보보안 과제로 밀러라빈 소수검출로 소수 검출하라길래

뭐지 하면서 찾아보는데

시간복잡도가 최대 klog^2(N) 까지 줄어들던데

이게 루트N 보다 유의미한 시간차가 안나서

그런 문제가 없는거임? 아니면 내가 최대 플레까지밖에 안푼

줫밥샛기라 이런 문제를 못본거임?

int범위 넘어가도 k 8개만 돌려보면 15자리까진 가능하다는데?

- dc official App

[익명(220.85)]

내려면 많은데 잘 안 냄 그래서 그거 복붙해서 레이팅 빨아먹잖아

[익명(116.38)]

내가 아만보였던거네 보통 어느정도 수준까지 시간복잡도가 줄어들어? - dc App

[익명(220.85)]

밀러라빈은 브루트포스에 비해 엄청엄청 빠름. 로그제곱이잖아. 10^18까지 100만개 물어봐도 아무 문제 없음 다만 보통 소수인지만 보는 게 필요한 일이 많지 않고 소인수분해 자체를 요구하기 때문에, 이 경우 비교대상이 폴라드로(n^0.25) vs 체로 sqrt까지 소수 전처리 후 소수들로 나누기(n^0.5/log(n^0.5))가 됨.

[익명(116.38)]

log제곱이 n의 몇제곱과 비슷하다고 봐야하는가 이런느낌이었음 ㅇㅇ ㄱㅅㄱㅅ - dc App

[익명(apg2fwpfgsz5)]

뭔가 굉장히 혼란스러워하는거 같은데, 진정하고 정리부터 해봐야 할듯 루트N보다 유의미한 차이가 없다는데 루트N이 어디서 나온거임?

[익명(116.38)]

루트 N이랑 log세제곱이랑 대략적으로 어느정도 수준에서 유의미한 차이가나는지 헷갈렸던 상황이라 그런거냐? 질문한거고 루트N은 소수판별할때 제일 많이쓰는거잖아 루트N까지 브루스포스 - dc App

[익명(116.38)]

브루트포스 - dc App

[익명(apg2fwpfgsz5)]

소수판별할때 제곱근까지 보는건, 로그N이아니라 루트N임. 여기부터 모든 혼란이 시작됐나보네

[익명(116.38)]

아니 k로그제곱N까지 줄일수 있는게 밀러라빈이라고 위키피디아에적혀잇다니깐;; - dc App

[익명(apg2fwpfgsz5)]

브루트포스로 하는게 루트N이고, 밀러라빈은 base의 개수를 k라고 했을 때 k log^2 N임 다시 제대로 확인해봐

[익명(116.38)]

아니 제곱근까지로 한정하면 브루트포스 맞잖아 왜 내가 혼란가진사람으로 생각하는거임자꾸 - dc App

[익명(116.38)]

내가 쓴 글 어디에도 일반적인 소수판별이 로그라는 말이 없는데 일반적인걸 루트라했고 - dc App

[익명(apg2fwpfgsz5)]

아니면 내가 본문 뉘앙스를 잘못 잡았나봄. 잘못말함 ㅈㅅㅈㅅ 유의미하게 차이나는거 맞고 문제도 따로 있음

[익명(apg2fwpfgsz5)]

그, 내가 원래 말하려는게 밀러라빈이 비결정론적인 접근이여서 마냥 임의의 큰 수에는 적용을 못하고
특정 범위 내에서 모든 소수를 검출할 수 있는 base들을 연구한게 있는데, 그게
https://miller-rabin.appspot.com/
여기에있음

[익명(apg2fwpfgsz5)]

2^62이하일때 base를 2, 3, 5, 7, 11, 13, 31, 61, 73 이렇게 쓰는데 문제 입출력 범위가 이 중간에 있는 문제들이 많이 있고, 실제로 백준에 꿀 빨수있는 수학문제들중에 이게 많음

[익명(116.38)]

ㅇㅇ.. 대충 위키 보니까 15자리 밑으로는 2 3 5 7 11 13 17까지 때리면 결정론적이라길래 백준에도 그정도 범위내의 문제가 나오지 않을까 싶어서 물어본 본문이었음 - dc App

[익명(apg2fwpfgsz5)]

에휴 시발 난 왜이리 글자를 물리적으로 잘못보냐..

[익명(112.187)]

폴라드로할때 씀

[익명(106.102)]

플레1에 있음 - dc App

[익명(117.111)]

tag: 밀러라빈인 문제 암거나 찾아봐

[익명(14.32)]

백준에 문제가 있냐 없냐랑 별개로 sqrt(N)보다 빨라지기 시작하는 N이 어디쯤이냐 라고 하면 10^6 ~ 10^7 정도일 거 같음.

[익명(14.32)]

물론 최적화를 어디까지 하냐에 따라 다름. 언어 이슈도 있고 쿼리냐 아니냐에 따라 이 시간 차이가 유의미하지 않을 수도 있지. 그러니까 10^8~10^9 정도부터 Miller-Rabin을 쓰는게 편하다라고 퉁치고 넘어가도 됨.

[익명(14.32)]

내가 쓰는 구현체를 기준으로 했을 땐, 내 노트북에서 10^6 ~ 2 * 10^6 을 전부 소수 판정하는 걸 기준으로 했을 때 sqrt(N)이 빨랐고, 10^7 ~ 2*10^7 을 소수판정했을 땐 Miller-Rabin 이 빨랐음