글 읽기 - pollard - rho 알고리즘 질문할께요

john6014 7년 전 0

로 알고리즘 원리는 얼추 이해했습니다만 난수 잡는게 너무 힘드네요... 위키를 바탕으로짯는데

시작 난수를 어떻게 잡아야할지모르겟습니다.. 함수는 x * x - 1 , x* x + 1 , x * x + 2 요 세개를 이용했구요

난수는 총 2개를 이용했는데 중간중간에 무한루프가 돌아서 계속 시간초과가뜹니다..

어떻게해야할까요??

아래는 제코드입니다. 코드가 좀 복잡하다만

x 와 fix 이 변수가 난수로 잡은 변수들이고 총 2번사용했습니다 , 첫번째는 둘다 2로 잡고 그 다음것은 둘다 3으로 잡은상태로..

// 4149 번 문제
#include <cstdio>
#include <algorithm>
#include <math.h>

using namespace std;

#pragma warning(disable:4996)

typedef struct _STACK
{
	long long int data;
	struct _STACK * link;
}STACK;;

long long int index = 0, arr[10000];
STACK * Top = NULL;

int Miller_Rabin(long long int N, long long int A);
long long int Mod(long long int A, long long int D, long long int N);
void Rho(long long int T);
long long int GCD(long long int a, long long int b);
int Test(long long int T);
int Prime(long long int T);
void Push(long long int D);
long long int Pop();

int main()
{

	long long int i, T;

	scanf("%lld", &T);

	if (Prime(T) == 1)
	{
		Rho(T);

		sort(arr, arr + index);

		for (i = 0; i < index; i++)
			printf("%lld\n", arr[i]);
	}
	return 0;
}

int Prime(long long int T)
{
	// 입력된 수가 소수인지 판별 
	if (T < 1373653)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 3) == 1)
		{
			printf("%lld", T);
			return 0;
		}
	}
	else if (T < 9080191)
	{
		if (Miller_Rabin(T, 31) == 1 && Miller_Rabin(T, 73) == 1)
		{
			printf("%lld", T);
			return 0;
		}
	}
	else if (T < 4759123141)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 7) == 1 && Miller_Rabin(T, 61) == 1)
		{
			printf("%lld", T);
			return 0;
		}
	}
	else if (T < 1122004669633)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 13) == 1 && Miller_Rabin(T, 23) == 1 && Miller_Rabin(T, 1662803) == 1)
		{
			printf("%lld", T);
			return 0;
		}
	}
	else if (T < 2152302898747)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 3) == 1 && Miller_Rabin(T, 5) == 1 && Miller_Rabin(T, 7) == 1 && Miller_Rabin(T, 11) == 1)
		{
			printf("%lld", T);
			return 0;
		}
	}
	else if (T < 3474749660383)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 3) == 1 && Miller_Rabin(T, 5) == 1 && Miller_Rabin(T, 7) == 1 && Miller_Rabin(T, 11) == 1 && Miller_Rabin(T, 13) == 1)
		{
			printf("%lld", T);
			return 0;
		}
	}
	else if (T < 341550071728321)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 3) == 1 && Miller_Rabin(T, 5) == 1 && Miller_Rabin(T, 7) == 1 && Miller_Rabin(T, 11) == 1 && Miller_Rabin(T, 13) == 1 && Miller_Rabin(T, 17) == 1)
		{
			printf("%lld", T);
			return 0;
		}
	}
	return 1;
}

int Test(long long int T)
{
	// 입력된 수가 소수인지 판별 
	if (T < 1373653)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 3) == 1)
			return 0;
	}
	else if (T < 9080191)
	{
		if (Miller_Rabin(T, 31) == 1 && Miller_Rabin(T, 73) == 1)
			return 0;
	}
	else if (T < 4759123141)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 7) == 1 && Miller_Rabin(T, 61) == 1)
			return 0;
	}
	else if (T < 1122004669633)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 13) == 1 && Miller_Rabin(T, 23) == 1 && Miller_Rabin(T, 1662803) == 1)
			return 0;
	}
	else if (T < 2152302898747)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 3) == 1 && Miller_Rabin(T, 5) == 1 && Miller_Rabin(T, 7) == 1 && Miller_Rabin(T, 11) == 1)
			return 0;
	}
	else if (T < 3474749660383)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 3) == 1 && Miller_Rabin(T, 5) == 1 && Miller_Rabin(T, 7) == 1 && Miller_Rabin(T, 11) == 1 && Miller_Rabin(T, 13) == 1)
			return 0;
	}
	else if (T < 341550071728321)
	{
		if (Miller_Rabin(T, 2) == 1 && Miller_Rabin(T, 3) == 1 && Miller_Rabin(T, 5) == 1 && Miller_Rabin(T, 7) == 1 && Miller_Rabin(T, 11) == 1 && Miller_Rabin(T, 13) == 1 && Miller_Rabin(T, 17) == 1)
			return 0;
	}

	return 1;
}

void Push(long long int D)
{
	STACK * temp = (STACK*)malloc(sizeof(STACK));
	temp->data = D;
	temp->link = Top;
	Top = temp;
}

long long int Pop()
{
	long long int value = Top->data;
	STACK * garbage = Top;
	Top = Top->link;
	free(garbage);
	return value;
}

void Rho(long long int T)
{
	long long i, factor, x, fix, cycle;

	while (T != 1)
	{
		factor = 1;
		x = fix = 2;
		cycle = 3;

		while (factor == 1)
		{
			for (i = 1; i <= cycle && factor <= 1; i++)
			{
				x = (x * x - 1) % T;

				if (x - fix > T)
					factor = GCD(abs(x - fix), T);
				else
					factor = GCD(T, abs(x - fix));
			}

			for (i = 1; i <= cycle && factor <= 1; i++)
			{
				x = (x * x + 1) % T;

				if (x - fix > T)
					factor = GCD(abs(x - fix), T);
				else
					factor = GCD(T, abs(x - fix));
			}

			for (i = 1; i <= cycle && factor <= 1; i++)
			{
				x = (x * x + 2) % T;

				if (x - fix > T)
					factor = GCD(abs(x - fix), T);
				else
					factor = GCD(T, abs(x - fix));
			}










			cycle *= 2;
			fix = x;
		}

		T /= factor;

		if (factor == 25)
		{
			arr[index++] = 5;
			arr[index++] = 5;
		}
		else if (Test(factor) == 0)
			arr[index++] = factor;
		else
			Push(factor);

		if (Test(T) == 0)
		{
			Push(T);
			break;
		}
	}

	while (Top != NULL)
	{
		factor = 1;
		x = fix = 4;
		cycle = 5;

		T = Pop();
		while (factor == 1)
		{
			for (i = 1; i <= cycle && factor <= 1; i++)
			{
				x = (x * x - 1) % T;

				if (x - fix > T)
					factor = GCD(abs(x - fix), T);
				else
					factor = GCD(T, abs(x - fix));
			}

			for (i = 1; i <= cycle && factor <= 1; i++)
			{
				x = (x * x + 1) % T;

				if (x - fix > T)
					factor = GCD(abs(x - fix), T);
				else
					factor = GCD(T, abs(x - fix));
			}


			for (i = 1; i <= cycle && factor <= 1; i++)
			{
				x = (x * x + 2) % T;

				if (x - fix > T)
					factor = GCD(abs(x - fix), T);
				else
					factor = GCD(T, abs(x - fix));
			}

			cycle *= 2;
			fix = x;
		}

		T /= factor;

		if (factor == 25)
		{
			arr[index++] = 5;
			arr[index++] = 5;
		}
		else if (Test(factor) == 0)
		{
			arr[index++] = factor;
			if (T != 1)
				Push(T);
		}
		else
			Push(factor);
	}
}

long long int GCD(long long int a, long long int b)
{
	long long int temp;

	while (b != 0)
	{
		temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}

int Miller_Rabin(long long int N, long long int A)
{
	long long int D, P, S = 0, T;

	if (N == 2 || N == 3)	return 1;

	if (N == 1 || (N & 1) == 0)	return 0;

	D = N - 1;

	while ((D & 1) == 0)
	{
		S++;
		D >>= 1;
	}

	P = Mod(A, D, N);

	while (S > 0)
	{
		T = (P * P) % N;

		if (T == 1 && P != 1 && P != N - 1)
			return 0;

		P = T;
		S--;
	}

	if (P != 1)
		return 0;

	return 1;
}

long long int Mod(long long int A, long long int D, long long int N)
{
	long long int result = 1;

	while (D > 0)
	{
		if ((D & 1) == 1)
			result = (result * A) % N;

		A = (A * A) % N;
		D >>= 1;
	}

	return result;
}

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

문제

문제

출처

ICPC

pollard - rho 알고리즘 질문할께요

john6014 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말