tlwpdus   1년 전

Pollard-Rho 알고리즘으로 구현했는데요... (10억 7)의 제곱 같이 큰 소인수 두 개로 이루어진 수들은 시간 안에 안 나오네요 ㅠㅠ 어떻게 시간을 줄여야 하는지 힌트 좀 주세요..

tlwpdus   1년 전

소스 코드는 최대한 제 힘으로 풀어보다가 안 되면 올릴게요

pichulia   1년 전

pollard-rho 알고리즘의 f(x)를 x^2+1로 쓰셨다면

29*53 인가? 뭐 이런 특이한 녀석 하나를 소인수분해하지 못하고 무한루프를 돌게 되있습니다.. 숫자가 정확히 기억 안나네요...


이런 문제를 해결하기 위해 저는 f(x)를 3가지 함수로 만들어서 사용했습니다.

x^2+1

x^2-1

x^2+2

이 3개의 함수에 대해서 다 소인수분해가 안된다면 소수다! 라고만 해도 충분할듯...

tlwpdus   1년 전

감사합니다. 한 번 짜볼게요~

tlwpdus   1년 전

아 근데요... 저 함수 구현할 때 큰 수 구현해서 쓰나요 아님 그냥 오버플로 되게 놔두고 쓰는 거

pichulia   1년 전

일단... 2^62-1 정도의 숫자에 대해 (p*q)%m 을 오버플로우 없이 구하는 코드입니다.ㅋㅋㅋ

tlwpdus   1년 전

우와... 신기하다 감사합니다 ㅋㅋㅋ

john6014   4달 전

혹시 이문제 해결하셧다면 좀 도와주셧으면합니다. ㅠㅠ 로알고리즘을 이용했는데도 특정 수에서 계속 무한루프가 돌아서 그런데 난수를 어떻게 지정하셧는지요??

https://www.acmicpc.net/board/view/8236

요기가면 제가 적은 소스가 있습니다 부디 도와주셨으면 합니다...

댓글을 작성하려면 로그인해야 합니다.